Brain teasers and puzzles

Oh, I wasn't saying you have an error - I'm saying it conflicts with my logic so I'm going to try to model it in a way that works for me :).

 

I did misread your big explanation and see you did include the cases of different white hats in your odds.

 

That also changes my algorithm - instead of just comparing all cases, the top-down strategy needs to be favored. Hm. I really need to consider this during work hours when my brain is working in this mode. :D

 

I has figured it out! Not all cases come into consideration because they have been "won" before getting to them!

Edit: I think - I forgot that pA is pointing at pA's hat - NOT pB's, and so might still be pointing at the wrong color. Hm.

 

@Exohedron, I've been trying to improve my solution, or prove that it's the best possible, and I can't do either. But I've poked it around enough to convince myself it's probably solid. (Then again, the claim that "no strategy will do better than 1/4" looks solid too, until it doesn't.) Feedback?

 

Spoiler: Stacks of Hats

There are strategies that yields 22/64, but that's the best you can do. These strategies generally look pretty weird. It would be a bit surprising if you found one, and even more surprising if you could prove that it's the best.

A little manipulation of your strategy gives a good (not best but good) strategy for the infinite hat case, if you count from the bottom hat rather than the top. The probability of winning using the "first white hat from the bottom" strategy in the infinite case is 1/3.

 

Spoiler

I'd extended my solution to infinity and gotten 1/3, yeah.

Twenty two out of sixty-four? That's bizarre. Those strategies must be weird.

 

Each person's chance of pointing to a white hat is still 1/2. The thing is, under this strategy those chances are not independent. Since each player is choosing a hat in response to the other player's hat arrangement, player A is a bit more likely to pick a white hat when player B is also picking white (and is more likely to pick a black hat when player B is also picking black, so the total chance of pointing to a white hat remains 1/2.) So the probability of a win is better than (1/2) * (1/2) = 1/4.

In symbols, P(A) = .5, and P(B) = .5, but P(A|B) > .5, so P(A&B) > .25.

 

Picking a hat in response to the other player's arrangement, instead of guessing, means that whether you pick a white hat depends on your arrangement and theirs, rather than your arrangement and chance (if you guess) or your arrangement alone (if, say, you always point to your top hat). Since each person's color chosen depends on both arrangements, the colors chosen are correlated.

 

That's essentially it. You're correlating which color you point at by having that be dependent on both stacks. The intuition block is that you think that the hat each of you point at is the factor that needs to be influenced, and then separately you consider the probability of each pointing to a white hat once the choices of hats to point to have been made. But probability problems don't split that way!
Alternatively, you can think of it as you getting information, not about what color hats are on your head, but on what colors your partner might end up pointing at depending on what she sees on your head. Information about the two-person, 6-hat system as a whole. And that's enough for a correlation.

I had a lot of fun when this puzzle was first floated around the math department, because most of the people were not probabilists, and while some of them figured out the asymptotically 1/3 solution, understanding why it worked (and more importantly, why it didn't fail) took quite a bit of heated discussion and argumentation.

 

Pirates and Voting

Here's a puzzle that you may have already heard of in some form.
A bunch of pirates, let's say 100, have stumbled across a treasure. Each of the pirates is greedy, of course, but they're also cunning and smart and are good at logic, which is why they're pirates.
These pirates like rules and order, at least within themselves. They all have a rank, with no two pirates of equal rank, from captain on downward. They also follow a protocol for splitting up treasure:
The captain declares how the treasure is to be split, and a vote is taken; if at least half of the pirates are happy, the captain's plan is followed. If more than 50% of the pirates are unhappy, the captain gets tossed overboard to the sharks and everyone still alive gets promoted a rank. The new captain then declares how the treasure is to be split, and the process repeats until someone's plan is accepted.

There are a few variations of the problem that we can make here, based on how much treasure there is. Suppose that it comes in gold doubloons that cannot be broken into smaller pieces, and each has the same value.
1: What should the (original) captain do if there are 200 doubloons?
2: What should the captain do if there are 100 doubloons?
3: What should the captain do if there are only 40 doubloons?

And just to be sure: assume that each pirate would rather be alive than rich if those are the only choices presented, but, if it doesn't harm them in the long run, will vote to kill rather than let live. Also rank doesn't effect how much a pirate's vote is worth, only how many people have to get tossed overboard for that pirate to become captain.

 

Runaway robot

A robot has escaped and is running around in the dark along an infinite tiled path. You know that the robot, being rather stupid, moves at a constant speed, some integer number of tiles per second, but you don't know where on the path it started running from.
Unfortunately, your equipment for locating the robot in the dark only allows for you, once per second, to pick an integer p and ask "is the robot at position p?"
Do you have a strategy to find the robot?

More formally, at integer time t the robot is at position q + tv for integers q and v, and at integer time s you are allowed the single question "does q + sv equal p?". Find the robot.

 

I mean, Z^2 is countable, so yes, I have a strategy. How good does it have to be?

 

Well, in particular, I'd ask for an algorithm.
Also the followup variants:
V2: Robot is moving according to some polynomial, degree not known
V3: Robot is moving according to some (Turing computable) algorithm that always outputs an integer at integer time

 

So, for the bad solution, imagine a Cartesian plane in q and v. (Do you still call it a plane when it's not continuous? Cartesian grid, maybe.) At time 0, start at (0,0); that is, assume the robot's position function is 0+0t and guess accordingly - i.e., position 0. Then, spiral out in the q-v plane: at time 1, my guess in solution space is (q,v) = (1,0), so I suppose the robot is following 1+0t and guess position 1. Then I go to (q,v)=(1,1), then (0,1), (-1,1), (-1,0), (-1,-1), (0,-1) and (1,-1), finishing that 3x3 grid centered on the origin. Then I move on to (2,-1) and start the 5x5 grid, and so on. For any finite q and v, I will find the robot in finite time.

The reason I think this is bad is that I didn't bother with the other (q,v) combinations that were ruled out by each guess. For example, guessing 0 at t=0 actually rules out all q=0 solutions, and guessing 1 at t=1 rules out all solutions of the form (1-v)+vt, but I was solving like I'd only ruled out (0,0) and (1,0) respectively. So there ought to be a much faster solution.

In general, guessing position p at time t is assuming the constraint q = p-tv. Since these constraints would be drawn on the q-v plane as lines of all different slopes, there's not an obvious way to efficiently hit every point on the grid.

I suppose you could keep a list of all the constraints you've eliminated, and check each point in the spiral against each constraint in the list before actually scanning for the robot. If that point is already ruled out, you can skip it. But that's inelegant: no matter how fast your computer is, eventually it won't be able to check every constraint in the one second you have between guesses.

Edited to fix a formula I got wrong.

 

Eh, assume the computer can compute as fast as you want it to, but there's just some mechanical constraint on trying to detect the robot.

 

Then my V1 solution with skipping is fine, I suppose.

As for the others... ugh. I can't think of a good way to count Z^N. (I'm not sure I even want to think about Z^N.) And version 3 seems easier - just use the set of all natural numbers in base-2, run them all through a Turing machine with the then-current time, and you'd have to hit it eventually - but that runs into the halting problem.

Hmmm, for version 2 - I can't actually visualize this, but we can extend the spiraling-out idea:
First, try {f(t) = 0}, the set of all polynomials of degree 0 and coefficient 0.
Then try {f(t) = 1, -1, t+1, t, t-1, -t+1, -t, -t-1}, the set of all polynomials of degree no greater than 1, and integer coefficients with absolute value no greater than one, but at least one of those things equals 1.
Then, the set of all polynomials of degree no greater than 2, with integer coefficients of absolute value no greater than 2, but at least one of those things equals 2.
And so on. Each of those subsets (loops in the spiral, to continue the spatial metaphor) is finite and every integer-coefficient polynomial is in one of those subsets, so you'd reach any polynomial in finite time. I suppose I'd need a lemma that a polynomial function which is closed over the integers must have integer coefficients.

 

Unfortunately, that's not true! n(n+1)/2 has noninteger coefficients, but it always spits out an integer on integer input.