The Troll, the dwarves and the gloves

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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:

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.