Answers to math puzzles.
Here are the answers to the math puzzles I posted last week. Of course, they're behind a cut, so you can just ignore them if you don't want to be spoiled.
Question 1:
The answer is 5.
Before you spin, you don't know anything about the position of the glasses:
??
??
1) After one spin, you feel two glasses which are on the same side. You turn them the right way up:
XX X? ?? ?X
?? X? XX ?X
I'll write X to mean "right way up", and O to mean "upside down".
These four variations are the same thing, but rotated. Since the rotation becomes irrelevant after a spin (we don't know a thing about it anyway), I'll just write down the actually distinct possibilities.
After having done this, and you hear the bell, you know that all question marks must also be U. Because of this, we'll assume that, whenever there are still question marks, we won't hear a bell. This way, we really play the longest game possible.
2) Now you spin the table, and reach for two diagonally opposite glasses. This will always be one of the glasses from the first turn, and an unknown. If needed, turn the one unknown the right way up. We now have:
XX
X?
Because the bell doesn't have to ring, we'll assume that the ? is an O:
XX
XO
3) Spin the table, and again reach for two diagonally opposite glasses. If you feel the O, turn it up and win, if they're both X, turn one upside down. We now have:
XX
OO
4) Spin the table again, and this time, reach for two glasses on the same side. If they're the same, turn them around and you win (you'll have grabbed the two Os, or the two Xs).
If they're different, also turn both of them around. We now have:
XO
OX
5) Spin the table for the last time. Now reach for two diagonally opposite glasses, and turn both of them around. You win.
Question 2:
Yes, this is always possible.
Realize that the rotating table only has 24 possible positions, and that for all 24 mathematicians, there is one position in which they are seated correctly. However, since one of the 24 table positions has 0 mathematicians seated correctly, there must be at least one table position in which at least two mathematicians are seated correctly.
Question 3:
Yes, this is always possible.
For this question, we introduce the "displacement number" for every mathematician. This is the minimum amount of positions the table needs to be rotated clockwise before the mathematician is seated correctly.
We will now be counting the mathematicians in a special way:
Pick a mathematician that is seated incorrectly, and note down its displacement number. Then look at the mathematician who is sitting where the previous one is supposed to sit. Add its displacement number to the previous one. *Then* look at the mathematician who is sitting where the (now) second one is supposed to sit, and add its displacement number. Repeat this until you encounter the first mathematician in a row.
Because we're at the start again, the sum of the displacement numbers must be a multiple of 24. If you don't understand that, the displacement number is exactly the number of rotations needed to go from someone to the place where he is supposed to sit. We go to this next person in a row until we end up at the beginning, so the total amount of seats we passed is exactly the same as the sum of the displacement numbers.
If there are still uncounted mathematicians, repeat the process. For every cycle you complete, the sum of displacement numbers will be a multiple of 24.
The one guy who is sitting right has a displacement number of 0, which is a multiple of 24 as well.
So now we know that the sum of all displacement numbers is a multiple of 24. Now, assume that there is no way to turn the table such that two or more mathematicians are seated correctly. This means that every mathematician must have its own unique displacement number (from 0 to 23). The sum of all numbers from 0 to 23 is 276... which isn't a multiple of 24.
We have reached a contradiction with something we know that must be true, through some earlier reasoning. That means our assumption is wrong, and there is indeed a way to turn the table such that at least two mathematicians are seated correctly.
Question 4, the bonus question:
It will be possible for all even numbers.
Note that nothing significant will have to change to the proof of what to do if nobody is seated correctly. If we have an n-sided table, we'll have 1 position in which no mathematician is seated correctly, and so we need (n-1) positions to seat n mathematicians correctly. This means at at least one position, at least one mathematician is seated correctly.
The proof of what happens if one person is seated correctly doesn't change much either:
Instead of the sum of displacement numbers being a multiple of 24, it'll be a multiple of n. We still want every mathematician to have a unique displacement numbers, so the sum of all of them will be the sum of the numbers 0 to (n-1), which is n*(n-1)/2.
If n*(n-1)/2 is not a multiple of n, then we reach the contradiction, and we can turn the table in such a way that two mathematicians are seated correctly.
If n is even, it can be written as (2*k), for some k:
(2*k)*(2*k-1)/2 = k*(2*k-1). This is not a multiple of (2*k), so we have a contradiction.
However, if n is odd, it can be written as (2*k + 1) for some k:
(2*k+1))*(2*k)/2 = (2*k+1)*k, which is obviously a multiple of (2*k + 1), so it might be impossible to rotate the table is such a way.
Question 1:
The answer is 5.
Before you spin, you don't know anything about the position of the glasses:
??
??
1) After one spin, you feel two glasses which are on the same side. You turn them the right way up:
XX X? ?? ?X
?? X? XX ?X
I'll write X to mean "right way up", and O to mean "upside down".
These four variations are the same thing, but rotated. Since the rotation becomes irrelevant after a spin (we don't know a thing about it anyway), I'll just write down the actually distinct possibilities.
After having done this, and you hear the bell, you know that all question marks must also be U. Because of this, we'll assume that, whenever there are still question marks, we won't hear a bell. This way, we really play the longest game possible.
2) Now you spin the table, and reach for two diagonally opposite glasses. This will always be one of the glasses from the first turn, and an unknown. If needed, turn the one unknown the right way up. We now have:
XX
X?
Because the bell doesn't have to ring, we'll assume that the ? is an O:
XX
XO
3) Spin the table, and again reach for two diagonally opposite glasses. If you feel the O, turn it up and win, if they're both X, turn one upside down. We now have:
XX
OO
4) Spin the table again, and this time, reach for two glasses on the same side. If they're the same, turn them around and you win (you'll have grabbed the two Os, or the two Xs).
If they're different, also turn both of them around. We now have:
XO
OX
5) Spin the table for the last time. Now reach for two diagonally opposite glasses, and turn both of them around. You win.
Question 2:
Yes, this is always possible.
Realize that the rotating table only has 24 possible positions, and that for all 24 mathematicians, there is one position in which they are seated correctly. However, since one of the 24 table positions has 0 mathematicians seated correctly, there must be at least one table position in which at least two mathematicians are seated correctly.
Question 3:
Yes, this is always possible.
For this question, we introduce the "displacement number" for every mathematician. This is the minimum amount of positions the table needs to be rotated clockwise before the mathematician is seated correctly.
We will now be counting the mathematicians in a special way:
Pick a mathematician that is seated incorrectly, and note down its displacement number. Then look at the mathematician who is sitting where the previous one is supposed to sit. Add its displacement number to the previous one. *Then* look at the mathematician who is sitting where the (now) second one is supposed to sit, and add its displacement number. Repeat this until you encounter the first mathematician in a row.
Because we're at the start again, the sum of the displacement numbers must be a multiple of 24. If you don't understand that, the displacement number is exactly the number of rotations needed to go from someone to the place where he is supposed to sit. We go to this next person in a row until we end up at the beginning, so the total amount of seats we passed is exactly the same as the sum of the displacement numbers.
If there are still uncounted mathematicians, repeat the process. For every cycle you complete, the sum of displacement numbers will be a multiple of 24.
The one guy who is sitting right has a displacement number of 0, which is a multiple of 24 as well.
So now we know that the sum of all displacement numbers is a multiple of 24. Now, assume that there is no way to turn the table such that two or more mathematicians are seated correctly. This means that every mathematician must have its own unique displacement number (from 0 to 23). The sum of all numbers from 0 to 23 is 276... which isn't a multiple of 24.
We have reached a contradiction with something we know that must be true, through some earlier reasoning. That means our assumption is wrong, and there is indeed a way to turn the table such that at least two mathematicians are seated correctly.
Question 4, the bonus question:
It will be possible for all even numbers.
Note that nothing significant will have to change to the proof of what to do if nobody is seated correctly. If we have an n-sided table, we'll have 1 position in which no mathematician is seated correctly, and so we need (n-1) positions to seat n mathematicians correctly. This means at at least one position, at least one mathematician is seated correctly.
The proof of what happens if one person is seated correctly doesn't change much either:
Instead of the sum of displacement numbers being a multiple of 24, it'll be a multiple of n. We still want every mathematician to have a unique displacement numbers, so the sum of all of them will be the sum of the numbers 0 to (n-1), which is n*(n-1)/2.
If n*(n-1)/2 is not a multiple of n, then we reach the contradiction, and we can turn the table in such a way that two mathematicians are seated correctly.
If n is even, it can be written as (2*k), for some k:
(2*k)*(2*k-1)/2 = k*(2*k-1). This is not a multiple of (2*k), so we have a contradiction.
However, if n is odd, it can be written as (2*k + 1) for some k:
(2*k+1))*(2*k)/2 = (2*k+1)*k, which is obviously a multiple of (2*k + 1), so it might be impossible to rotate the table is such a way.