[Guest]

a group of 16 men each have a hat numbered 1-8, repeats allowed. the need to communicate their hat number by way of shaking hands. if a hand shake is accepted, it is counted against both players. if rejected, it doesn't hurt either of them. what's the fewest number of accepted hand shakes you would need for everyone to determine their hat number? which player has the best chance of winning?

Edited August 1, 2010 by phillip1882

[bonanova]

What do players learn from an accepted or rejected handshake?

Is there a strategy agreed upon before this process starts?

Or is that all part of the puzzle?

[Guest]

I think they should agree on a strategy first, here's my attempt:

You didn't say that each number is repeated exactly once so I take it that any number can appear from 0 to 16 times?

Since it's 1 to 8 they should agree to represent their numbers as 3 binary digits, with 0000 being 8, now they split into two groups of 8, each one from the first group offers his hand to another from the second group, if they other accepted his shake then that means that his first digit is 1, if he rejected then 0, now the second group does it then they do it a second and third round and by then everyone will know their number...

[Guest]

a group of 16 men each have a hat numbered 1-8, repeats allowed. the need to communicate their hat number by way of shaking hands. if a hand shake is accepted, it is counted against both players. if rejected, it doesn't hurt either of them. what's the fewest number of accepted hand shakes you would need for everyone to determine their hat number? which player has the best chance of winning?

The puzzle is not clearly defined. Whose hat number does each man need to communicate --

their own or each of the other 15 men?

Do the 16 men know their own hat numbers?

Can they see the other men's hat numbers but not their own?

[Guest]

a group of 16 men each have a hat numbered 1-8, repeats allowed. the need to communicate their hat number by way of shaking hands. if a hand shake is accepted, it is counted against both players. if rejected, it doesn't hurt either of them. what's the fewest number of accepted hand shakes you would need for everyone to determine their hat number? which player has the best chance of winning?

The men get into groups of two. In each group man A offers a handshake, if man B accepts, it means that your hat number is 1. If man B rejects the first time and accepts the second time, it means your hat # is 2. If man B accepts on the 3rd try, your number is 3, etc. One man B accepts a hand shake, man A shakes man B's hand the same number of times as his hat number. One shake would be the same as taking the hand up and going down. When you go down the first time it is one, the second 2, etc.

[Guest]

Assuming they can decide on a strategy before the game, and assuming each one can see the others' hats but not his own:

They can "assign" to each one a number between 1-8 before the game. Each number given to two people. Then, once the game begins, each person extends his hand to the man wearing "his own" number. The man rejects the handshake, but already knows the number on his hat! Because each number "has" two people, it's gonna work even if you got your own number - someone else will offer you a handshake. No accepted handshakes needed, everyone wins!

[Guest]

yes they can form a strategy before hand and yes they can see everyone else's hat number but not their own.

[Guest]

I can get it in zero handshakes, assuming everyone can observe other people's handshakes.

Some special person will be designated before the game as the starter.

The starter will go up to a person who the starter thinks has the lowest number in the room who we will call the first selected person (if there are several such people, the starter will just pick one) and offer N handshakes which are all declined. Here, N is the number on the first-selected person's hat. After N handshakes, the starter will request a handshake with someone else. It doesn't matter who, it will be declined.

The first selected person now knows his own number.

Here is the code he will use to tell everyone their number. All requests will be declined.

M+1 handshake requests means your number is M, and to everyone observing, it means that the first selected person is handling all people with the number M on their heads.

A single handshake request means that you have the same number on your hat as the current group that the first selected person is processing.

After your own number is figured out, go stand in a corner so as not to interfere with the rest of the game.

After the first selected person has requested as many handshakes from the last remaining person that he/she intends to, the first-selected person will randomly pick someone from the solved corner to request a handshake, signifying the end of the game. At this point everyone will know their own number. And nobody has shaken anyone else's hand.

The only complication is if the starter has a lower number than the first selected person.

But using the same code I showed above, the first selected person can inform the starter of his number, hence this is not a problem.

Edited August 1, 2010 by mmiguel1

[Guest]

I can get it in zero handshakes, assuming everyone can observe other people's handshakes.

Some special person will be designated before the game as the starter.

The starter will go up to a person who the starter thinks has the lowest number in the room who we will call the first selected person (if there are several such people, the starter will just pick one) and offer N handshakes which are all declined. Here, N is the number on the first-selected person's hat. After N handshakes, the starter will request a handshake with someone else. It doesn't matter who, it will be declined.

The first selected person now knows his own number.

Here is the code he will use to tell everyone their number. All requests will be declined.

M+1 handshake requests means your number is M, and to everyone observing, it means that the first selected person is handling all people with the number M on their heads.

A single handshake request means that you have the same number on your hat as the current group that the first selected person is processing.

After your own number is figured out, go stand in a corner so as not to interfere with the rest of the game.

After the first selected person has requested as many handshakes from the last remaining person that he/she intends to, the first-selected person will randomly pick someone from the solved corner to request a handshake, signifying the end of the game. At this point everyone will know their own number. And nobody has shaken anyone else's hand.

The only complication is if the starter has a lower number than the first selected person.

But using the same code I showed above, the first selected person can inform the starter of his number, hence this is not a problem.

I just read Arbelle's which is much more elegant than mine. I like that way better.

Edited August 1, 2010 by mmiguel1

[Guest]

If the men can plan a strategy:

This process doesn't require the visual occurance of others' handshakes, but does require a little sequence of order. In the strategic planning phase, one man is chosen as the "sorter". After everyone is assigned their numbered hats, the sorter approaches the man, or one of the men, with the lowest numbered hat and offers a handshake. It is refused and that man then moves to a position in which others might stand behind him. The sorter then approaches the man with the next lowest numbered hat and offers a handshake. It is refused, and the man goes to the queue - but before falling behind the man leading the queue, if the queue leader has hat numbered 1, the man offers a handshake to the queue leader. It is refused. But now the queue leader has now deduced his own hat number. The leader of the queue knows the last man joining the queue has an equal or greater number to his. As each number 1-8 is represented at least once, he knows his own is 1 if he were offered a handshake by the man behind him, else, unoffered, he must be wearing a 2. If the man behind him is a 3, he knows the sorter has already deduced his own to be 1 or 2, as any man could deduce their own if then did not see the number among the other hats. To prevent a break in the sequence, if the sorter's hat number is unique and greater than 2, the queue leader offers a handshake to the sorter, it is refused. And the queue leader becomes the sorter. As the former sorter has deduced his number, he simply falls in line in the proper sequence permitting the deduction by all to their own hat numbers. If it is not unique, the first man in the queue that has the same hat number as the former sorter offers a handshake to the former sorter. It is, of course, refused. All numbers deduced.

[Guest]

Use others' eyes as mirrors, therefore seeing your own number.