Math Puzzle [num 20] - Page 6

Use red/blue parity - even or odd number of red/blue. Only the last one is at risk of being killed for announcing the initial parity of the 19 ahead of him.
The everyone else announces based on parity changes or non-change which will be the color of the hat that he is wearing.

The monster follows Day9's movements inside the circle of safety and will try to be at the edge of the circle closest to Day9. The monsters covers the arc of the circle at 4s/r. If Day9 can cover arc faster, then he can leave the monster behind on the circle. Day9 can do this by running a smaller circle at less than radius r/4 (covering arc at faster than s/(r/4)). Via this method, Day9 can never beat the monster by more than pi arcs or the monster turns around.

Naively, we can say that Day9 can touch the water safely. Day9 is 3/4r away from the edge of the island. The monster is pi*r from that point and can only cover 3r in the time that Day9 needs to reach that point and get in the water. Here Day9 is making a break perpendicularly from the r/4 circle.

Optimally, Day9 should make his break on a tangent to the r/4 circle in a direct line for the gate. This causes the monster to swim more of arcs of the circle in pursuit (the monster is assumed to be pursuing the long way) while Day9 makes progress in getting off the island.

The math gets complicated from there and there's some pursuit diff. eqs. I'll add more later.

The correct answer to this problem is a computer algorithm called binary search. http://en.wikipedia.org/wiki/Binary_search_algorithm
If there are n floors, you will find the correct floor after checking log(n) floors

First of all, let's start by agreeing that Day9 is really fucking smart, and all we're trying to figure out is What Would Day9 Do. WWDD? That's right.
He's already miles ahead of us by running full speed as soon as he starts the strategy because he knows that it doesn't make sense to run any slower. Plus he's boss because of his ungodly stamina. Look at those legs go.
He's worked through the strategy in part 1: http://www.teamliquid.net/blogs/viewblog.php?topic_id=285063&currentpage=6#102 to get ahead of the monster by running around in circles inside the 1/4r circle and if he messed up he could always come back and try again. Day9's thought ahead, but how did he know when to make a dash for the gate?

First he busted out the polar coordinates and simplified the problem. Radius of the island becomes 1. His own speed becomes C. The speed of the monster becomes 4C. (To be honest, Day9 doesn't care how fast he's running and needed r & s for more important things.) As long as Day9 was inside the circle and the monster was chasing him, the monster's position was bounded by


Day9 then imagined that he took the plunge and was out in no man's land beyond the safe circle of 1/4 and making a break for the shore. What was the optimum way to run for the shore? He knew he was bound by a parametric equation and the pythagorean theorem of the angular and radial differentials:


Then he had to optimize outward movement over monster's angular gain. He wanted a path that gets him as close to the shore as possible while minimizing the angular catchup that the monster would achieve. The sign in the denominator has to be a minus, otherwise Day9 is going towards the monsters and should retry!


Then subbed in the radial differential from the pythagorean theorem:

Sanity check here. If Day9 chooses angular motion of 0, he should get a ratio of 1/4. He moves C out, the monster moves 4C around an arc. And it's true! I'm still sane.

At this point, Day9 probably subbed in for angular movement, but frankly the following equation was beyond me. Day9 is hardcore:


Then take the derivative with respect to the angular differential using chain rule and solve for zero. Some stuff fell out and the derivative looks like: (the denominator of the derivative doesn't matter as much but again good for sanity checks)


plug that back into the pythagorean theorem and solve for radial differential and integrate to get the parametrized equation for radius.


You know what that looks like? Day9 took one look and recognized it as the pythagorean theorem equation. What a smart guy. Reorganize and boom (pretend C0 is 0 for a bit)!!!

He also knows that he's running Ct for distance so his parametric equation for path looks very much like a straight line. Day9 would make a beeline break for at his target point on the shore when it is tangent to the 1/4 circle that he was already running, checking once to see that monster was chasing the long way around.

Solve for theta to prove that it is indeed a line, and it looks like a proper inverse tangent function for the line:


Are we done yet? Nope! We still have to figure out how Day9 chose where on the shore to run for and how he decided to run after reaching the water. Dammit Day9. Why are you so smart.

I would say to drop on floor 100, then 50. If it broke on 100, but not 50, try 75, otherwise 25.
Basically this would be the interval halving method, and you would use the minimum amount of drops to find out where it breaks.

Alternatively, pick a floor, drop the egg, and hope you've got it right

Drop from 14. Assuming no breaks, drop form these floors until first break: 27 39 50 60 69 77 84 90 95 99

After first break, start at last known successful floor +1 then go by 1's up. This algorithm yields worst-case-scenario of 14 drops

Not sure if someone has mentioned yet, but for completeness, a way to show that 13 definitely doesn't work is:

Possible outcomes of the 13 drops
If two breaks occur: 13C2 = 78
Only one break: 13
No breaks: 1

That's a total of 92 outcomes, which is not sufficient to differentiate the 101 possible outcomes of a 100 level building.

But I think it's easier to omit no breaks and think in number of levels rather than number of breakage results. It is only adding 1 to each side of the equation.

Generalized for any number of eggs:

Day9's lead in arcs at point of entry into the water is about .58 (compare this to .14 when doing the native perpendicular way) and that means that he's got an upper bound on the gate's distance from his point of entry into the water at about .19. If the gate is pictured according to scale at C, Day9 knows he's doomed.


It's easier to prove that aiming for F is better than aiming for B.

Another counting problem.
You do this by feeding each bottle to a unique combinations of rats. When that combination of rats die you know you'll which bottle was the culprit (no rats is a possibility). For 4 rats there is 2^4 or 16 possible combinations and more than enough for the 13 bottles.

First we'll consider the cube along 3 axis (x for the 2000 thick, y for the 85 thick, z for the 95 thick).
We'll partition the outcome into 3 equally possible subcategories. The cube's top face could be aligned along the x axis, the y axis, or the z axis.

For each of the of these axis subcategories, the probability that the side is painted 1/n where n is the thickness of the cube along that axis. There are 2 painted sides and 2 * n total sides.

The probability of rolling a painted side is 1/3(1/85+1/95+1/2000)