Join the new world

Hey, everyone.

I’ve decided to publish my personal solution to the 2014 people and 2015 hats problem, which I posted around two weeks ago or so… Don’t hate on me if it’s too mathematical. 😛

It’s based on even and odd permutations. If you don’t know what odd and even permutations are, then you should read what I’m about to say right now…

You’re given a sequence of numbers from 1 to some number “n” so that it looks like this:

1 2 3 4 … n

and you have the ability to swap any two numbers. If you get some permutation by making an even number of swaps, that permutation is even, if you get it by making an odd number of swaps, then it’s odd.

For example, you’re given the sequence from 1 to 6:

1 2 3 4 5 6

If you swap 4 and 5, you will get:

1 2 3 5 4 6

This permutation is odd, because you’ve made one swap in order to obtain it. If you swap 3 and 4 in this new permutation, you get:

1 2 4 5 3 6

This permutation is now even, because you’ve made two swaps in total to obtain it, and two is an even number. If you swap 1 and 6 you get:

6 2 4 5 3 1

This permutation is odd, because three swaps have been made in total. And so on…

This is how odd and even permutations work. They are defined for any sequence of numbers, doesn’t matter how many numbers we have. That means that they also function for our 2015 numbers. An important thing for us to note is that two permutations that differ in only two places (you need to swap two numbers to get one from the other), are of different parity: one is odd and one is even.

So what do these 2014 people do? What’s their strategy?

Person #1 looks at all the hat numbers that he sees. We will call them x[2], x[3], x[4]... x[2014]... They represent the number on the hats for people #2, #3, #4, … #2014, respectively. He forms a sequence in his mind such that its first 2013 numbers are these 2013 numbers, and he has to put the remaining two numbers on the last two places. He has two possible combinations:

x[2] x[3] x[4] … x[2014] a b
x[2] x[3] x[4] … x[2014] b a
(“a” and “b” are these two extra numbers)

As we’ve already concluded, these two permutations are of different parity. One of them is odd, the other is even. We pick the one which is even. Denote the number which person #1 says “k” (k = key). Let “r” (r = rest) be the other number, which is totally useless.

The permutation in his head is now:

x[2] x[3] x[4] … x[2014] k r

The other people need to guess that permutation in order to be able to guess their hat number.

Person #2 sees all the hat numbers except his own, and he knows “k” (person #1 has said it). The permutation in his head is:

[something] x[3] x[4] … x[2014] k [something]

He knows all the numbers individually except x[2] and “r”. He knows which two numbers they are, he just doesn’t know which is which. But, he does know that the permutation he needs to guess is even (that’s how person #1 selected it). He is now able to guess the correct permutation, because out of his two possible choices, one is even and the other is odd, because we know that their parity isn’t the same. He is able to figure out his correct hat number and he says it.

When every next person’s turn comes, he knows all the other people’s hat number except his own (he sees the hat numbers for the people in front of him, and he has already heard the hat numbers for all the people behind him, except for person #1, who is unimportant). He also knows “k”, he just doesn’t know “r”. The same thing goes on… There are two possible permutation combinations, one is even, the other is odd, and since the given permutation must be even, he is able to correctly guess the permutation, and his hat number.

This way everyone guesses his hat number correctly, except for person #1, who can never be 100% sure about guessing his own hat number. The team will always be able to score at least 2013 points, no matter how the hats are distributed.

I-G-D