12 replies to this topic

[howardl1963]

Ten friends walk into a room where each one of them receives a hat. On each hat is written a real number; no two hats have the same number. Each person can see the numbers written on his friends' hats, but cannot see his own. They are given some time to ponder the numbers on the other 9 hats. The friends then go into individual rooms where they are each given the choice between a white T-shirt and a black T-shirt. Wearing the respective T-shirts they selected, the friends gather again and are lined up in the ascending order of their hat numbers. The desired property is that the T-shirts colors now alternate.

The friends are allowed to decide on a strategy before walking into the room with the hats, but they are not allowed to communicate in any way with each other once the game starts. Design a strategy that lets the friends ALWAYS end up with alternating T-shirt colors.


This is a cool problem and I'm fairly certain I've solved it. The website, where I found it, does not offer solutions of any kind, so I'm hoping someone solves it with an explanation simpler than the one I've found. Enjoy!

[csv]

Ten friends walk into a room where each one of them receives a hat. On each hat is written a real number; no two hats have the same number. Each person can see the numbers written on his friends' hats, but cannot see his own. They are given some time to ponder the numbers on the other 9 hats. The friends then go into individual rooms where they are each given the choice between a white T-shirt and a black T-shirt. Wearing the respective T-shirts they selected, the friends gather again and are lined up in the ascending order of their hat numbers. The desired property is that the T-shirts colors now alternate.

The friends are allowed to decide on a strategy before walking into the room with the hats, but they are not allowed to communicate in any way with each other once the game starts. Design a strategy that lets the friends ALWAYS end up with alternating T-shirt colors.


This is a cool problem and I'm fairly certain I've solved it. The website, where I found it, does not offer solutions of any kind, so I'm hoping someone solves it with an explanation simpler than the one I've found. Enjoy!

Spoiler for solution with communication defined as: Not letting others know the exact number by any way

1 person goes stand next to the lowest he can see, a third person does the same (validating that the first person isnt the lowest himself. The lowest can now stand next to his friends in order from low to high

[wolfgang]

Spoiler for I have a long strategy

If these 10 persons have the time to re-arrenge them selves,so:
they should stand in a line,the 1st. one to the right will see which one has the highest number(X) ,and he should stand to his right side.and both of them should step foreword( 1,X).
The 2nd. one should stand right to the 1st.one(2,1,X).
the 3rd.can see now the three numbers:
If they are ascending,,,he should stand to the right.
If not,he should stand between 2 and 1,and both of them(3 and 1)should move right to 2.(3,1,2,X).
The 4th. will see the new arrengement,
If they are right arrenged,he should stand right to them,
If not he should stand,inbetween,and shift the wrong number to the right,then he should see again the new arrengement,,,,,and so on.until the last person ,who should stand right to them,and the (X) must control the final arrengement as before,then get back to his place.
The last step is take the T-shirts white and black respectively.

[phillip1882]

hmm...

Spoiler for assuming no communication, period

assuming they have alot of time...
each person takes the average and the standard diviation of the numbers he sees.
then he calculates likelyhood of his position. if odd, black, if even white.
exe. let's say there are 5 instead of 10.
num 1.25, 2.34, 4.67, 5.88, 9.22.
avg 5.53, 5.26, 4.67, 4.37, 3.54
std 2.87, 3.29, 3.62, 3.53, 2.12
odd 40%, 36%, 64%, 52%, 68%
white white black black black
as you can see, a poor method, but i honestly can't think of better one.

[bushindo]

Ten friends walk into a room where each one of them receives a hat. On each hat is written a real number; no two hats have the same number. Each person can see the numbers written on his friends' hats, but cannot see his own. They are given some time to ponder the numbers on the other 9 hats. The friends then go into individual rooms where they are each given the choice between a white T-shirt and a black T-shirt. Wearing the respective T-shirts they selected, the friends gather again and are lined up in the ascending order of their hat numbers. The desired property is that the T-shirts colors now alternate.

The friends are allowed to decide on a strategy before walking into the room with the hats, but they are not allowed to communicate in any way with each other once the game starts. Design a strategy that lets the friends ALWAYS end up with alternating T-shirt colors.


This is a cool problem and I'm fairly certain I've solved it. The website, where I found it, does not offer solutions of any kind, so I'm hoping someone solves it with an explanation simpler than the one I've found. Enjoy!

This is indeed a cool problem

Spoiler for strategy

The key of this strategy is that each participant can not tell what is the rank of his hat number in the set of 10 real numbers. He can, however, guess whether he is an odd/even number of positions from the smallest number. Combine that with a special tool that lets everybody make dependent guesses, and we got a solution.

Some general concepts are as follows. We make use of inversion numbers, which essentially tells us how out-of-order a permutation is. Each random permutation has a inversion number, which can either be odd or even. Let's label the participant from 1 to 10, the assignment of hats essentially is a random permutation of the participant's labels with respect to the hat numerical order. This random permutation has an inversion number.

The strategy is as follows,

1) Let each participant assume that the inversion number of their label permutation is even.

2) Let each participant look at the other 9 people, and construct the 10 possible permutations by inserting his position into the appropriate places (essentially by guessing that his number is the smallest, second smallest, and so on). Five of those possible permutations are even and five are odd. All the even permutation will consistently say that he is either an odd or even number of positions from the smallest hat number. If all participants follow this strategy, either they will ALL be correct about the odd/even guesses, or they'll ALL be incorrect.

3) If the result of part 2) says that a participant is an odd number of positions from the smallest number, let that participant choose a black shirt. Otherwise, choose a white shirt.



Example: Let the participants be labelled 1 to 10. Suppose that the host arrange the hat numbers so that they go from smallest to largest

( 2 , 4 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3)

Participant 2 looks at the remaining people, he sees in order from smallest to largest: (4 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3). Assuming that the permutation of 10 labels is even, there are 5 possible choices
( 4 , 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3)
( 4 , 1 , 6 , 2 , 8 ,10 , 7 , 9 , 5, 3)
( 4 , 1 , 6 , 8 ,10 , 2 , 7 , 9 , 5, 3)
( 4 , 1 , 6 , 8 ,10 , 7 , 9 , 2 , 5, 3)
( 4 , 1 , 6 , 8 ,10 , 7 , 9 , 5 , 3, 2)

Notice that all of these choices implies that participant 2 is an ODD number of positions from the smallest number (participant 4). Participant 2 would then choose a black shirt. If we apply the same logic to participants 1, 8, 7, and 5, we'll see that they'll get ODD positions and will choose all black shirts.

Let's look at participant 4 then, he would see in order from smallest to largest: ( 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3). So the five possible even permutations are
( 4 , 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3)
( 2 , 1 , 4 , 6 , 8 ,10 , 7 , 9 , 5, 3)
( 2 , 1 , 6 , 8 , 4 ,10 , 7 , 9 , 5, 3)
( 2 , 1 , 6 , 8 ,10 , 7 , 4 , 9 , 5, 3)
( 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5 , 4, 3)
Notice that these possible permutations all state that participant 4 is an EVEN number of position from the smallest hat number. He would then choose a white shirt, as does participants 6, 10, 9, and 3. Notice that contrary to everybody's guess, the true permutation ( 2 , 4 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3) is actually ODD, however, that does not affect the fact that we get an alternating pattern anyways.

Edited by bushindo, 27 December 2010 - 08:10 PM.

[Callegreif]

Uh, everything seems so complicated to my solution o_o
The way i understood it, the hats have numbers 1-10.
So if you look at friends hats and see the number missing, its yours.
And all people with even numbers could take black shirts and uneven ones whites.
Just a quick idea tho

[howardl1963]

Uh, everything seems so complicated to my solution o_o
The way i understood it, the hats have numbers 1-10.
So if you look at friends hats and see the number missing, its yours.
And all people with even numbers could take black shirts and uneven ones whites.
Just a quick idea tho

The numbers are real numbers. So no matter what numbers you see, your number could be in any of the 10 positions. The 9 hats you see won't tell you anything about your postion.

[howardl1963]

Spoiler for I have a long strategy

If these 10 persons have the time to re-arrenge them selves,so:
they should stand in a line,the 1st. one to the right will see which one has the highest number(X) ,and he should stand to his right side.and both of them should step foreword( 1,X).
The 2nd. one should stand right to the 1st.one(2,1,X).
the 3rd.can see now the three numbers:
If they are ascending,,,he should stand to the right.
If not,he should stand between 2 and 1,and both of them(3 and 1)should move right to 2.(3,1,2,X).
The 4th. will see the new arrengement,
If they are right arrenged,he should stand right to them,
If not he should stand,inbetween,and shift the wrong number to the right,then he should see again the new arrengement,,,,,and so on.until the last person ,who should stand right to them,and the (X) must control the final arrengement as before,then get back to his place.
The last step is take the T-shirts white and black respectively.

This would definitely be extra communication. Imagine, instead of going into the room and receiving your hat, you get your hat in an isolated room, and you are then informed of the numbers on the hats of your friends (and which friends received which hats) and then you have decide your T-shirt color before the host assembles you all in the room by ascending order.

[howardl1963]

This is indeed a cool problem

Spoiler for strategy

The key of this strategy is that each participant can not tell what is the rank of his hat number in the set of 10 real numbers. He can, however, guess whether he is an odd/even number of positions from the smallest number. Combine that with a special tool that lets everybody make dependent guesses, and we got a solution.

Some general concepts are as follows. We make use of inversion numbers, which essentially tells us how out-of-order a permutation is. Each random permutation has a inversion number, which can either be odd or even. Let's label the participant from 1 to 10, the assignment of hats essentially is a random permutation of the participant's labels with respect to the hat numerical order. This random permutation has an inversion number.

The strategy is as follows,

1) Let each participant assume that the inversion number of their label permutation is even.

2) Let each participant look at the other 9 people, and construct the 10 possible permutations by inserting his position into the appropriate places (essentially by guessing that his number is the smallest, second smallest, and so on). Five of those possible permutations are even and five are odd. All the even permutation will consistently say that he is either an odd or even number of positions from the smallest hat number. If all participants follow this strategy, either they will ALL be correct about the odd/even guesses, or they'll ALL be incorrect.

3) If the result of part 2) says that a participant is an odd number of positions from the smallest number, let that participant choose a black shirt. Otherwise, choose a white shirt.



Example: Let the participants be labelled 1 to 10. Suppose that the host arrange the hat numbers so that they go from smallest to largest

( 2 , 4 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3)

Participant 2 looks at the remaining people, he sees in order from smallest to largest: (4 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3). Assuming that the permutation of 10 labels is even, there are 5 possible choices
( 4 , 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3)
( 4 , 1 , 6 , 2 , 8 ,10 , 7 , 9 , 5, 3)
( 4 , 1 , 6 , 8 ,10 , 2 , 7 , 9 , 5, 3)
( 4 , 1 , 6 , 8 ,10 , 7 , 9 , 2 , 5, 3)
( 4 , 1 , 6 , 8 ,10 , 7 , 9 , 5 , 3, 2)

Notice that all of these choices implies that participant 2 is an ODD number of positions from the smallest number (participant 4). Participant 2 would then choose a black shirt. If we apply the same logic to participants 1, 8, 7, and 5, we'll see that they'll get ODD positions and will choose all black shirts.

Let's look at participant 4 then, he would see in order from smallest to largest: ( 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3). So the five possible even permutations are
( 4 , 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3)
( 2 , 1 , 4 , 6 , 8 ,10 , 7 , 9 , 5, 3)
( 2 , 1 , 6 , 8 , 4 ,10 , 7 , 9 , 5, 3)
( 2 , 1 , 6 , 8 ,10 , 7 , 4 , 9 , 5, 3)
( 2 , 1 , 6 , 8 ,10 , 7 , 9 , 5 , 4, 3)
Notice that these possible permutations all state that participant 4 is an EVEN number of position from the smallest hat number. He would then choose a white shirt, as does participants 6, 10, 9, and 3. Notice that contrary to everybody's guess, the true permutation ( 2 , 4 , 1 , 6 , 8 ,10 , 7 , 9 , 5, 3) is actually ODD, however, that does not affect the fact that we get an alternating pattern anyways.

Very well done bushindo. As I suspected, I had used a more brute force method for determining how out of order the hats were to do essentially the same thing. I'll elaborate in the spoiler.

Spoiler for My Method

I spoke to some of my better trained math friends to better understand permutations of a list.

Their layman's explanation is to think of how many "flips" you'd have to do to get the list in order. It might be simpler to consider a list of 4 numbers such as: 4 3 2 1. To restore this list to 1 2 3 4, you can flip 1 and the 4, and then the 2 and 3. This is the most efficient way to do it, but that's not important for this problem. It's whether it takes an odd or even number of flips to restore order. You could instead flip the 1 and the 2, then the 1 and the 4, then the 2 and the 4, then the 2 and the 3 to restore order. This would be much less efficient, but still yield order in an even number of flips. There is no way to restore this particular list without using an even number of flips. On the other hand, if the list were 4 2 3 1, it would always take an odd number of flips to restore order.

I was not aware of permutations, so I came up with a different way to determine how out of order a list is. Again take 4 3 2 1 for example. My method was to first look at the 1, and see that is was placed higher than 3 numbers it wasn't supposed to be higher then. Then I looked at the 2, and saw it was higher than 2 numbers is wasn't supposed to be higher than. And the 3 is out of order by 1. You add 3+2+1 and you get an even number. Using this method will always yield the same odd/even result that simple permutations will yield, though with much more work.

So with that long-winded take on permutations out of the way, I'll move on to my solution. To keep it simple, I'll only deal with a game with 4 friends. The exact same method will work for N friends. Before the game starts, the 4 friends will assign a number from 1 to 4 to each friend and will also assign themselves with a white or black default t-shirt that alternates given their pre-game order. So friend 1 will be W, friend 2 will be B, 3 will be W and 4 will be B.

After they go into the room, they will then look at the order of the other three hats as is applies to their predetermined assignation. Let's assume the ascending order of the 4 friends' make friend 3 the low number, friend 2 the second low number, friend 4 the third low number and friend 1 the high number. Their order is 3 2 4 1. Friend 1 see's 3 2 4, and to restore order he only needs to do 1 flip (switch 3 and 2) which is odd. So friend 1 would switch from the pre-determined W to B. Friend 2 sees 3 4 1. To restore order to this list it takes 2 flips, which is even, so friend 2 would retain his B t-shirt. Friend 3 sees, 2 4 1, which takes 2 flips to restore order, so friend 3 will retain his W t-shirt. Friend 4 sees 3 2 1, which takes 1 flip to restore order, so he would switch to W. When they are reassembled in the room, 3 wears W, 2 wears B, 4 wears W and 1 wears B, which is the desired alternating outcome.

This strategy will work for any number of friends.

My method is definitely less elegant than bushindo's, and lacked the thorough understanding of the underlying mathematical concepts, but it works nonetheless.

[Mesmer]

Spoiler for Simple Solution?

Try this.

The strategy that the group agrees to ahead of getting their hats is the following:
1. the select someone in advance (Andy)
2. Andy's job is to line up the other 9 people in order of ascending numbers left to right
3. when Andy is done, the leftmost person (the one with the smallest number on his hat) then positions Andy
4. if Andy is placed in any position other than first, the individual resumes his place in line and we have everyone lined up.
5. if Andy is placed first, the person resumes his place as first
6. the rightmost person then properly places Andy