Based on the prisoner riddle video posted in the funny videos thread, I thought it might be fun to have a math puzzle thread.
I enjoy a good math puzzle, but what makes a puzzle really special is if it sounds near impossible to solve, but has a really elegant solution that doesn't require knowledge of high power mathematics.
I'll share the few that I know - maybe one a week. But I hope there will be other contributions. If the puzzle follows the above guidelines, it is good incentive not to look up the solution online, but to spend some time trying to figure it out yourself.
Here's the first one.
The cigar game.
This game involves two players each with an unlimited number of cigars. The cigars are perfectly cylindrical, 1" diameter and 6" in length. They are perfectly balanced.
There is a circular table, 24" in diameter.
Each player takes turns placing a single cigar on the table. They can place the cigar on the table in any orientation, as long as it is not touching any other cigar on the table.
The last player who can successfully place a cigar on the table wins.
Prove that if you play first, you can guarantee a win.
The Following User Says Thank You to psyang For This Useful Post:
Put one exactly in the middle, then mirror exactly whatever your opponent does?
Yup. Radial symmetry for the win. The measurements and shapes are largely red herrings. As long as the table is a flat, radially symmetric shape (a square would work) and the "cigars" have at least one orientation when placed on the table so that (from above) it is also radially symmetric (like a block in the shape of an equilateral triangle), the winning strategy works.
Or does it? Are the above rules sufficient, or can you think of a counter example?
I have a couple that I came across the other day. I don't think the math is too complex, but just not intuitive.
1. How many people would you need in a room for there to be a 50% chance that 2 of the people will share the same birthday?
2. If you had a rope and extended it around the circumference of the Earth (40,075 km), then wanted to elevate the rope 1 foot off the ground across the whole plant, so it was like a ring hovering over the Earth, how much more rope would you need? Then do the same thing with a tennis ball and compare the numbers.
I will admit that I am not a math guy, but the answers surprised me.
__________________
"A pessimist thinks things can't get any worse. An optimist knows they can."
Last edited by FlamesAddiction; 06-30-2022 at 11:20 PM.
Location: In my office, at the Ministry of Awesome!
Exp:
Quote:
Originally Posted by FlamesAddiction
I have a couple that I came across the other day. I don't think the match is too complex, but just not intuitive.
1. How many people would you need in a room for there to be a 50% chance that 2 of the people will share the same birthday?
2. If you had a rope and extended it around the circumference of the Earth (40,075 km), then wanted to elevate the rope 1 foot off the ground across the whole plant, so it was like a ring hovering over the Earth, how much more rope would you need? Then do the same thing with a tennis ball and compare the numbers.
I will admit that I am not a math guy, but the answers surprised me.
1.
Spoiler!
Classic birthday problem. 23 baby!
I can do the math, I'm not gonna do the math.
2.
Spoiler!
Another classic
6.28 ft for both
C=2*pi*r
It should be C=pi*tau, but no need to get into why tau is better than pi right now.
r=radius of tennis ball of earth (in feet)
Original rope = 2*pi*r
New rope = 2*pi*(re+1)=2*pi*re + 2*pi*1
difference = 2*pi*1=6.28
__________________
THE SHANTZ WILL RISE AGAIN. <-----Check the Badge bitches. You want some Awesome, you come to me!
Last edited by Bring_Back_Shantz; 06-30-2022 at 04:14 PM.
The Following User Says Thank You to Bring_Back_Shantz For This Useful Post:
Two people are in prison, and the jailer offers them a math puzzle, which if they give the right answer, the jailer will let them go free, if they give the wrong answer, they will be executed.
- the prisoners know all of the rules of the game beforehand and can discuss their strategy before the puzzle starts.
- there is a chess board, and 64 coins, one for each space. There is also a token that can completely hide under a coin without being able to tell if it’s there.
- after the prisons discuss their strategy, the jailer sends one of them out of the room, no communication is possible between the two prisoners.
- with only the jailer and one prisoner in the room, the jailer places one coin on each space of the chess board, head or tails in each space, jailers choice.
- the jailer places the token under one coin, with the prisoner aware of where the coin is placed.
- The prisoner can flip any ONE and only one coin from heads to tails or vice versa.
- there is no heat transfer, to tell if one coin is warmer than others.
- After the coin is flipped, the second prisoner returns to the cell, and has ONE choice to pick up a coin to see if the token is underneath. If they pick up the coin with the token under, they go free, if not, they are executed.
Two people are in prison, and the jailer offers them a math puzzle, which if they give the right answer, the jailer will let them go free, if they give the wrong answer, they will be executed.
- the prisoners know all of the rules of the game beforehand and can discuss their strategy before the puzzle starts.
- there is a chess board, and 64 coins, one for each space. There is also a token that can completely hide under a coin without being able to tell if it’s there.
- after the prisons discuss their strategy, the jailer sends one of them out of the room, no communication is possible between the two prisoners.
- with only the jailer and one prisoner in the room, the jailer places one coin on each space of the chess board, head or tails in each space, jailers choice.
- the jailer places the token under one coin, with the prisoner aware of where the coin is placed.
- The prisoner can flip any ONE and only one coin from heads to tails or vice versa.
- there is no heat transfer, to tell if one coin is warmer than others.
- After the coin is flipped, the second prisoner returns to the cell, and has ONE choice to pick up a coin to see if the token is underneath. If they pick up the coin with the token under, they go free, if not, they are executed.
- how do the prisoners survive?
I haven't heard this problem before, but my initial instinct is it is a parity problem, and probably closely related to hamming codes. I'll try to take some time this weekend to work it out.
I haven't heard this problem before, but my initial instinct is it is a parity problem, and probably closely related to hamming codes. I'll try to take some time this weekend to work it out.
Ok, I figured it out, but I had a bit of help. It had been a while since I learned about hamming codes - I just remembered it was a clever way to do parity-based error checking while also being able to identify the location of the error bit.
But reviewing the specifics of how hamming codes work clued me into the solution.
Quick solution + example
Spoiler!
Consider heads as 0s and tails as 1s and the chessboard as a 64 bit long bitstring.
Mentally (not physically) flip the quarter with the token. Using this new bitstring, you can always convert it to a "well prepared bitstring" by flipping one bit. That is the quarter to physically flip.
A well prepared bitstring is one where, if you take all the positions in the bitstring that have a 1, and xor those positions, the result is 0.
As an example, I'll use 16 bits for brevity. Let's say the 16 bits are:
1001001011110100
and the token is under position 5 (using positions 0-based indexing, so position 5 is the 6th bit):
Mentally, I flip 5 to get:
1001011011110100
Now I make it well-prepared. To do this it is easier to think of the bitstring as a 4x4 block:
1001
0110
1111
0100
Now I look at the parity of bits in all the indexes where the 4th (last) bit is 1 (2nd and 4th column). Then do the same for where the 3rd bit is 1 (3rd and 4th column), 2nd bit is 1 (2nd and 4th row), and 1st bit is 1 (3rd and 4th row). I am interested only in the value where the parity is odd.
In the above example the parities are:
4th bit=1: odd
3rd bit=1: even
2nd bit=1: odd
1st bit=1: odd
Since 1st, 2nd, and 4th bit is odd, I have to flip the bit in position 1101 which is position 13. That is the quarter I physically flip.
1001011011110000
The second prisoner comes in and sees:
1001001011110000
which looks like
1001
0010
1111
0000
Now he does the same thing - get the parity of all indexes that have a one, grouping by whether the position's 4th bit is 1, 3rd bit, etc. He gets:
4th bit=1: odd
3rd bit=1: even
2nd bit=1: odd
1st bit=1: even
That converts to the bitstring 0101 which is 5 which is where the token is.
More detail
Spoiler!
Hamming codes are like magic, which is why this problem seems so impossible at the outset.
The core idea of hamming codes is in addition to the bit itself, its position within the string is important information.
The 64 bits have position
0, 1, 2, ..., 62, 63
or in binary
000000, 000001, 000010, ..., 111110, 111111
When you see the chessboard, if you number so that top-left is 0, and bottom right is 63, moving left-to-right only, then the positions where:
-6th bit is 1: every other column (cols 1,3,5).
-5th bit is 1: every other group of two columns (cols 2+3, 6+7).
-4th bit is 1: last four columns (cols 4-7).
-3rd bit is 1: every other row (row 1,3,5).
-2nd bit is 1: every other group of two rows (rows 2+3, 6+7).
-1st bit is 1: last four rows (rows 4-7).
By computing parity of each group, and storing it in positions 1, 2, 4, 8, 16, and 32, you have a block of 64 bits whose parity of all 6 groups will always be even. Another way of putting it is that the xor of all the positions that have a 1 will end up with 0 (if parity is even, # of 1s is even, so xor'ing those 1s will always result in 0).
After doing this, if you flip any bit (quarter), the xor of all the positions that have a 1 will always give the position in the bitstring that was flipped. This is the magic of the hamming code. It not only detects the error, but the location of the error. It does this because, by flipping one quarter, you are changing the parity of one or more of those 6 groups. But since those 6 groups represent the index of the bits' binary positions, the groups you are changing necessarily form the binary representation of the position that you flipped.
Another way to look at it is, if you flip position 38, its binary representation is 100110. That means you have changed the parity for the groups where the 1st, 4th, and 5th bit is 1. So when the second prisoner computes those parities, he will see that groups for bits 1, 4, and 5 are odd, which gives 100110 which gives location 38.
There are some great resources on hamming codes. I was introduced to them a while back from this 2-parter:
It was after the python code example in the second video was shown that everything clicked for me.
The Following User Says Thank You to psyang For This Useful Post:
Yup. Radial symmetry for the win. The measurements and shapes are largely red herrings. As long as the table is a flat, radially symmetric shape (a square would work) and the "cigars" have at least one orientation when placed on the table so that (from above) it is also radially symmetric (like a block in the shape of an equilateral triangle), the winning strategy works.
Or does it? Are the above rules sufficient, or can you think of a counter example?
Ok, I don't know why I said an equilateral triangle was radially symmetric. it's not, and using it would not work. Use a square instead. Oops.
Ok, I figured it out, but I had a bit of help. It had been a while since I learned about hamming codes - I just remembered it was a clever way to do parity-based error checking while also being able to identify the location of the error bit.
But reviewing the specifics of how hamming codes work clued me into the solution.
Quick solution + example
Spoiler!
Consider heads as 0s and tails as 1s and the chessboard as a 64 bit long bitstring.
Mentally (not physically) flip the quarter with the token. Using this new bitstring, you can always convert it to a "well prepared bitstring" by flipping one bit. That is the quarter to physically flip.
A well prepared bitstring is one where, if you take all the positions in the bitstring that have a 1, and xor those positions, the result is 0.
As an example, I'll use 16 bits for brevity. Let's say the 16 bits are:
1001001011110100
and the token is under position 5 (using positions 0-based indexing, so position 5 is the 6th bit):
Mentally, I flip 5 to get:
1001011011110100
Now I make it well-prepared. To do this it is easier to think of the bitstring as a 4x4 block:
1001
0110
1111
0100
Now I look at the parity of bits in all the indexes where the 4th (last) bit is 1 (2nd and 4th column). Then do the same for where the 3rd bit is 1 (3rd and 4th column), 2nd bit is 1 (2nd and 4th row), and 1st bit is 1 (3rd and 4th row). I am interested only in the value where the parity is odd.
In the above example the parities are:
4th bit=1: odd
3rd bit=1: even
2nd bit=1: odd
1st bit=1: odd
Since 1st, 2nd, and 4th bit is odd, I have to flip the bit in position 1101 which is position 13. That is the quarter I physically flip.
1001011011110000
The second prisoner comes in and sees:
1001001011110000
which looks like
1001
0010
1111
0000
Now he does the same thing - get the parity of all indexes that have a one, grouping by whether the position's 4th bit is 1, 3rd bit, etc. He gets:
4th bit=1: odd
3rd bit=1: even
2nd bit=1: odd
1st bit=1: even
That converts to the bitstring 0101 which is 5 which is where the token is.
More detail
Spoiler!
Hamming codes are like magic, which is why this problem seems so impossible at the outset.
The core idea of hamming codes is in addition to the bit itself, its position within the string is important information.
The 64 bits have position
0, 1, 2, ..., 62, 63
or in binary
000000, 000001, 000010, ..., 111110, 111111
When you see the chessboard, if you number so that top-left is 0, and bottom right is 63, moving left-to-right only, then the positions where:
-6th bit is 1: every other column (cols 1,3,5).
-5th bit is 1: every other group of two columns (cols 2+3, 6+7).
-4th bit is 1: last four columns (cols 4-7).
-3rd bit is 1: every other row (row 1,3,5).
-2nd bit is 1: every other group of two rows (rows 2+3, 6+7).
-1st bit is 1: last four rows (rows 4-7).
By computing parity of each group, and storing it in positions 1, 2, 4, 8, 16, and 32, you have a block of 64 bits whose parity of all 6 groups will always be even. Another way of putting it is that the xor of all the positions that have a 1 will end up with 0 (if parity is even, # of 1s is even, so xor'ing those 1s will always result in 0).
After doing this, if you flip any bit (quarter), the xor of all the positions that have a 1 will always give the position in the bitstring that was flipped. This is the magic of the hamming code. It not only detects the error, but the location of the error. It does this because, by flipping one quarter, you are changing the parity of one or more of those 6 groups. But since those 6 groups represent the index of the bits' binary positions, the groups you are changing necessarily form the binary representation of the position that you flipped.
Another way to look at it is, if you flip position 38, its binary representation is 100110. That means you have changed the parity for the groups where the 1st, 4th, and 5th bit is 1. So when the second prisoner computes those parities, he will see that groups for bits 1, 4, and 5 are odd, which gives 100110 which gives location 38.
There are some great resources on hamming codes. I was introduced to them a while back from this 2-parter:
It was after the python code example in the second video was shown that everything clicked for me.
Say you want two primes to be separated by at least n cosecutive composite numbers.
(n+1)! + 2
(n+1)! + 3
...
(n+1)! + n+1
This is a run of n consecutive composite numbers. Now just choose n to be as large as you want.
Great job!
Maybe going forward we spoiler the solutions to give others a chance. I think figuring out a problem by yourself is extremely rewarding.
Also, if you've heard the problem before (not saying you did), maybe wait a day or so before posting to give people time to think about it.
I like this problem because it sounds difficult but the solution is so elegant. The trick is to shift your focus from the primes to the composites in between the primes.
You have a meter stick placed so that the 0cm marker is on the left, and the 100cm marker is on the right.
99 ants are placed on every cm marker from 1 to 99.
The ant at cm 1 is facing to the right. The ant at cm 99 is facing left.
For the 97 ants in between, a coin is flipped to determine if that ant is facing left or right: heads, the ant faces left, tails the ant faces right.
Ants only walk in a straight line at 1cm/s in the direction they are heading. If an ant bumps into another ant, both ants immediately turn around and start walking in the opposite direction.
If an ant walks to either end of the meter stick, it falls off.
1) Prove that, eventually, all ants will fall off?
2) What is the maximum time it will take for all ants to fall off?
Math Puzzles
<-----Check the Badge bitches. You want some Awesome, you come to me!
