12
$\begingroup$

A group of $N$ dwarves are caught by an evil Troll. As usual the Troll gives the dwarves a chance to escape if they solve a puzzle he created just for the occasion.

Tomorrow morning each dwarf will receive a glove and an hat with a different non-negative integer number. The numbers are chosen by the Troll with an unknown distribution. The dwarves will be able to see each other (they all look different thus they can recognise who is wearing which hat). They can look at the numbers on all the other dwarves' hat but they won't be able to see their own number nor to communicate in any way.

After a few minutes the dwarves are called one by one in the hall and they will have to decide to wear the glove either on their left hand or in their right hand. They cannot see the choices made by the other dwarves.

As soon as everyone has worn the glove the dwarves are lined up in ascending order by the numbers on their hats (all facing the same direction) and forced to join their hands in a long chain without crossing harms. If any hand touches any glove all the dwarves have lost their chance and will be immediately eaten by the Troll. If it is always hand-to-hand or glove-to-glove all the dwarves are set free.

Remember that all of this is happening tomorrow, so tonight the dwarves have plenty of time to think of a strategy that can save them from being eaten.

For which values of $N$ such strategy exists?

Disclaimer: I don't know the solution to this puzzle. I have found it here; there is just an hint in the comments:

A strategy works perfectly if and only if it works once and keeps working under adjacent transpositions

$\endgroup$
  • $\begingroup$ Are the numbers continuous? say from 0 to N. Is a dwarf can see N-1 dwarves numbers or only the number on the dwarf standing before? $\endgroup$ – Mostwanted Mani Feb 10 at 9:52
  • 2
    $\begingroup$ No, the distribution of the numbers is not given. Updating the question. $\endgroup$ – melfnt Feb 10 at 9:55
  • $\begingroup$ Can a dwarf tell the others to look for [insert a number he saw] without directly telling he saw it? $\endgroup$ – Nautilus Feb 10 at 15:19
  • $\begingroup$ For that matter, can a dwarf tell the others to look for N-1 numbers without directly telling he saw them? $\endgroup$ – Nautilus Feb 10 at 15:25
  • $\begingroup$ @nautilus the dwarves are not allowed to communicate in any way durig the first minutes nor they can during the lining up phase. They can however discuss a strategy before the game starts (I.e. before the hats are assigned) $\endgroup$ – melfnt Feb 10 at 15:48
20
$\begingroup$

I think the following strategy works for any $N$.
Note that it works for any kind of hat-labelling, as long as those labels are sortable and all distinct, so not just positive integers.

The dwarfs assign themselves their own ordering, for example by painting the numbers $1$ to $N$ on their shirts. When they get their hats, each dwarf looks at the other $N-1$ dwarfs and constructs a list of the hat-numbers they see, using the order given by the shirt numbers. Each dwarf then sorts their list by swapping adjacent entries, counting how many swaps are needed as they do so. Finally they add their own shirt number to the swap count. If the result is even, put the glove on the left hand, if it is odd put the glove on the right hand.

This is a bit complicated, so here is a small example with $N=5$. Instead of numbers on the hats, I'll use some random letters instead, otherwise it could get a bit confusing.

Suppose the five dwarfs with shirt numbers 1 to 5 are given hats with the following letters:

 12345
 SGEHL

Each dwarf then does the following sorting and counting procedure :
    List  Sorted  Swaps  Total Parity Glove
 1: GEHL->EGHL   1 swap  +1=2   even  left
 2: SEHL->EHLS   3 swaps +2=5   odd   right
 3: SGHL->GHLS   3 swaps +3=6   even  left
 4: SGEL->EGLS   4 swaps +4=8   even  left
 5: SGEH->EGHS   4 swaps +5=9   odd   right
The result is then that when they are sorted according to their hat letter, they alternate left and right gloves:
 32451
 EGHLS
 LRLRL

You can prove it works by using the hint given in the question.

If the hat labels are given out in the same order as the shirt numbers, then all the dwarfs already have a sorted list, and need 0 swaps to sort it. This means that the even-numbered ones put the glove on the left hand, the odd-numbered on the right, and they will alternate as required.

Suppose you have any hat-labelling for which this strategy worked, and then swap the hat labels of two dwarfs who will be adjacent in the final line-up. Those two dwarfs will still get the same result as before (one entry on their list is changed, but it is in the same place relative to all the other hat labels). One of them is left-gloved, the other right. In the eventual line-up they will however be in the opposite order, holding each other with the other hand. That still works, but they will have changed the type of hand that connects with the rest of the line. All the other dwarfs will need an extra swap to sort their list so will change the side of their glove, so still connect with the swapped pair correctly.

All possible permutations can be achieved by adjacent swaps from the sorted order, so all possible permutations still work.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is very nice. $\endgroup$ – Gareth McCaughan Feb 10 at 13:24
  • 1
    $\begingroup$ That's awesome, thank you $\endgroup$ – melfnt Feb 10 at 13:59
  • 1
    $\begingroup$ @melfnt does this answer violate the > The dwarves will be able to see the numbers on all the other dwarves' hat but they won't be able to see their own number nor to communicate in any way. Or is only communication of their numbers the only non-allowed communication? $\endgroup$ – Enthus3d Feb 10 at 20:55
  • 1
    $\begingroup$ @Enthus3d I don't understand why you think that this answer violates the non-communication constraint. The dwarves are not required to know their hat number/letter to apply this strategy, and their shirt numbers are fixed before the game starts. $\endgroup$ – melfnt Feb 10 at 21:16
  • 2
    $\begingroup$ @Enthus3d I don't think that's possible but if you find a way please share it with us $\endgroup$ – melfnt Feb 10 at 21:21
0
$\begingroup$

The accepted answer works as long as dwarves can tell each other apart, as in the answer given. If this is not the case - e.g. each dwarf learns only the set of other hats, but not their ordering, then the problem is impossible for N = 3.

Without loss of generality, assume that a dwarf seeing 01 will put the glove on the right hand. Then a dwarf seeing 02 must put the glove on the left hand, to avoid failing in the scenario 012. Likewise, a dwarf seeing 03 must put the glove on the left hand to avoid failing in the scenario 013. But then failure is assured in the scenario 023.

To put it briefly, if dwarves can't tell other dwarves apart, there is no strategy that works for all of 012, 013 and 023.

| improve this answer | |
$\endgroup$
  • $\begingroup$ From the question: "the dwarves are lined up in ascending order by the numbers on their hats" You're essentially saying, "If the dwarves are put in a random order, they can't win." That's not really a big surprise. $\endgroup$ – Spitemaster Feb 10 at 21:11
  • $\begingroup$ @Spitemaster No, that's not what I'm saying at all. I'm saying that if during the post-hat-wearing, pre-glove-wearing phase, the dwarves can't tell each other apart except for the hats, they're in trouble. Imagine if they're all wearing identical masks and identical clothes that they're not allowed to remove. $\endgroup$ – isaacg Feb 10 at 21:13
  • $\begingroup$ They can recognise themselves while they are wearing hats. Should I put this in the question? $\endgroup$ – melfnt Feb 10 at 21:23
  • 3
    $\begingroup$ @melfnt: The knowledge of which dwarves are wearing which hat is critical, and should be stated in the puzzle. $\endgroup$ – supercat Feb 10 at 22:12
  • 1
    $\begingroup$ @supercat modified the question, thank you $\endgroup$ – melfnt Feb 10 at 23:43
0
$\begingroup$

As stated in the question:

The dwarves will be able to see each other (they all look different thus they can recognise who is wearing which hat). They can look at the numbers on all the other dwarves' hat but they won't be able to see their own number nor to communicate in any way.

Although this does not necessarily mean that the dwarves are not allowed to create a strategy, I was interested in the case where the dwarfs have no chance to create a unified strategy.

Is there a set of strategies that the dwarfs could employ, while having no clue what the other dwarfs would do?

Probably not. It's likely that, whatever they choose, the it could be simulated with a coin flip.

If the coin lands as heads, they can put it on whatever hand they designated.

This guarantees an even distribution where they have no idea what the other dwarfs will do.

When they are all lined up, their chance of survival will be 0.5^(N-1), where each hand link has 50% chance of being faulty or successful. The graph below for their survival rate starting at one dwarf:

enter image description here

From this graph, and the equation, anything past 4 dwarves would mean less than 12.5% survival rate. The survival rate drastically falls the more dwarves we have due to the exponential nature of the arrangement. As an example, at 7 little dwarves, there would only be a 1.5625% survival rate.

We can see from these rates that the troll has basically rigged this game against dwarves with no strategy.

Knowing this, the strategy that guarantees the best survival rate with no unified strategy would probably be: if the number of dwarves is less than 5 or 6, they can attempt the challenge with the glove on a random hand. If they have more than 5 or 6, the dwarves should just leg it.

After all, no matter what the survival rate of trying to escape from a troll, it's probably higher than 1-3%. By having at least some survivors, and by telling future dwarves about the troll's arrangements, they can guarantee that the troll never eats another dwarf by telling the dwarves to travel in groups of N=1, allowing them to get out scotch-free each time.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In this question they were actually allowed to discuss a strategy before the game starts $\endgroup$ – melfnt Feb 11 at 16:54
  • $\begingroup$ I understand. I am just providing an answer where they do not have a chance to discuss the strategy, because it is interesting to consider what kind of strategy they would adopt if they cannot communicate with each other at all. $\endgroup$ – Enthus3d Feb 11 at 17:03
  • $\begingroup$ This was the best I could do under this assumption, although absolutely not the best the dwarves could do with communication. $\endgroup$ – Enthus3d Feb 11 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.