Brain Teasers 3 - Puzzle Prime

FEATURED

Numbers on Prisoners’ Foreheads

Section: Brain Teasers Category: Mathematics

Difficulty: Hard Tags: Featured

A hundred prisoners are locked up in a prison. The warden devises the following game: he writes 100 different numbers on the foreheads of the prisoners. Then, each of the prisoners inspects the numbers on the foreheads of the others and decides to put either a black or a white hat on his head. Once the prisoners put their hats on, the warden arranges them in a line according to the numbers on their foreheads, starting with the lowest one and ascending to the highest one.

If the hats in the resulting line alternate their colors, then the prisoners will be set free. If not, the prisoners will be executed.

Can the prisoners devise a strategy that will guarantee their freedom?

SOLUTION

Once the warden writes the numbers on the prisoners’ foreheads, they form a mental circle, arranging themselves alphabetically in it (or according to any other order they agree on). They include the warden in this mental circle and imagine he has infinity written on his forehead.

Then, each prisoner examines the sequence of 100 numbers written on the foreheads of the others, and computes the number of inversions, i.e. the pairs which are not in their natural order. The prisoners which count an even number of permutations put black hats on, and the prisoners that count an odd number of permutations put white hats on. The infinity symbol is treated as the largest number in the sequence.

For example, if a prisoner sees the sequence {2, -6, 15.5, ∞, -100, 10}, then he counts seven inversions, which are the pairs (2, -6), (2, -100), (-6, -100), (15.5, -100), (15.5, 10), (∞, -100), (∞, 10), and puts a white hat on.

Next, we prove that the devised strategy works. We consider two prisoners, P1 and P2, who are adjacent in the final line the warden forms. These two prisoners split the mental circle in two arcs: A and B.

The number of inversions P1 counts is:

I_1 = I(A)+I(B)+I(A,B)+I(A, P_1) + I(P_1, B),

where $I(X)$ denotes the number of inversions in a sequence $X$ , and $I(X, Y)$ denotes the number of inversions in a pair of sequences $(X, Y)$ :

I(X) = \|x_i, x_j \in X : \quad i < j, \quad x_i > x_j\| \\ I(X, Y) = \|x \in X, y \in Y : \quad x > y\|

Similarly, the number of inversions P2 counts is:

I_2 = I(A) + I(B) + I(B, A) + I(B, P_2) + I(P_2, A)

We sum $I_1$ and $I_2$ to get:

\begin{align*} I_1 + I_2 &= 2I(A) + 2I(B) + I(A, B) + I(B, A) \\ &+ I(A, P_1) + I(P_2, A) + I(P_1, B) + I(B, P_2) \\ &= 2(I(A) + I(B)) + \|A\|\|B\|+\|A\|+\|B\| \end{align*}

Since $\|A\| + \|B\| = 99$ is an odd number, we see that $I_1+I_2$ is also odd. Therefore, one among P1 and P2 would have counted an even number of inversions, and one would have counted an odd number of inversions. Thus, their hats have alternating colors.

Unknown Author January 4, 2024

9 Comments

Third Business Day

Section: Brain Teasers Category: Deduction

Difficulty: Medium

What is the chance that the third business day of a month is Wednesday?

SOLUTION

Assuming there is an equal chance that the given month begins with any of the seven days of the week, the answer is 3/7. That’s because Saturday and Sunday are non-working days, and therefore if the month starts with any of them, the third business day will still be Wednesday.

We note that 3/7 is actually an approximation of the actual answer, since the frequencies with which the days of the week appear as first in a given month, are close to but not equal to 1/7 each.

Unknown Author December 28, 2023

2 Comments

The Madman’s Speech

Section: Brain Teasers Category: Insight

Difficulty: Hard

You are walking through the prairie when you find a madman wandering around talking to himself. The following is what you manage to hear of his speech:

“How? I – I’ll ask her. I owe her much, again. I’d a home on town, a tax as florid as out the coat, a virgin a year. Oh, yodel – aware you take all or I do. Never the road: I’ll land in the Anna-Marie land. Main can’s a sore gone; tennis is out t’car. Oh, line a canned turkey!”

What is the man really talking about?

Source: Puzzling StackExchange

SOLUTION

The man is actually reciting the states in America, even though you can’t hear him well:

“How? – I” = Hawaii
“I’ll ask her.” = Alaska
“I owe her” = Iowa
“much again” = Michigan
“I’d a ho…” = Idaho
“…me on town, a” = Montana
“tax as” = Texas
“florid a…” = Florida
“…s out the coat, a” = South Dakota
“virgin a year.” = Virginia
“Oh yo…” = Ohio
“…del – aware” = Delaware
“You ta…” = Utah
“…ke all or i do” = Colorado
“Never the” = Nevada
“road: I’ll land” = Rhode Island
“in the Anna-…” = Indiana
“…Marie land” = Maryland
“Main” = Maine
“can’s a s…” = Kansas
“…ore gone;” = Oregon
“tennis i…” = Tennessee
“…s out t’car. Oh line a” = South Carolina
“canned Turkey” = Kentucky

Rand al'Thor December 25, 2023

0 Comments

Mate No Matter What

Section: Brain Teasers Category: Chess

Difficulty: Advanced

If White is to play, can he always mate Black in 2 moves, regardless of the moves played before?

SOLUTION

First, we notice that since Black made the last move, either the king or the rook has been moved, consequently rendering Black unable to castle. Now White plays Qa1 and no matter what is Black’s next move, Qh8 gives check-mate.

Unknown Author December 22, 2023

0 Comments

Ping Pong Ball

Section: Brain Teasers Category: Insight

Difficulty: Medium

Your last ping pong ball falls down into a narrow pipe embedded in concrete one foot deep. How can you get it out undamaged if all you have is your tennis paddle, your shoelaces, keys, wallet, and a plastic water bottle, which does not fit into the pipe?

SOLUTION

Using the plastic bottle, pour water into the pipe so that the ball will rise up.

Unknown Author December 19, 2023

0 Comments

Grasshoppers

Section: Brain Teasers Category: Mathematics

Difficulty: Hard

Four grasshoppers start at the ends of a square in the plane. Every second one of them jumps over another one and lands on its other side at the same distance. Can the grasshoppers after finitely many jumps end up at the vertices of a bigger square?

SOLUTION

The answer is NO. In order to show this, assume they can and consider their reverse movement. Now the grasshoppers start at the vertices of some square, say with unit length sides, and end up at the vertices of a smaller square. Create a lattice in the plane using the starting unit square. It is easy to see that the grasshoppers at all times will land on vertices of this lattice. However, it is easy to see that every square with vertices coinciding with the lattice’s vertices has sides of length at least one. Therefore the assumption is wrong.

Unknown Author December 16, 2023

0 Comments

Fathers, Sons, and Fish

Section: Brain Teasers Category: Insight

Difficulty: Medium

Two fathers and two sons went out fishing. Each of them catches two fish. However, they brought home only six fish. How so?

SOLUTION

They were a son, his father, and his grandfather – 3 people in total.

Unknown Author December 10, 2023

1 Comment

Mirrors

Section: Brain Teasers Category: Deduction

Difficulty: Advanced

Why do mirrors flip left and right but do not flip up and down?

SOLUTION

Solution coming soon.

Unknown Author December 7, 2023

4 Comments

Sunome Variations

Section: Brain Teasers Category: Deduction

Difficulty: Advanced

The main challenge of a Sunome puzzle is drawing a maze. Numbers surrounding the outside of the maze border give an indication of how the maze is to be constructed. To solve the puzzle you must draw all the walls where they belong and then draw a path from the Start square to the End square.

The walls of the maze are to be drawn on the dotted lines inside the border. A single wall exists either between 2 nodes or a node and the border. The numbers on the top and left of the border tell you how many walls exist on the corresponding lines inside the grid. The numbers on the right and bottom of the border tell you how many walls exist in the corresponding rows and columns. In addition, the following must be true:

Each puzzle has a unique solution.
There is only 1 maze path to the End square.
Every Node must have a wall touching it.
Walls must trace back to a border.
If the Start and End squares are adjacent to each other, a wall must separate them.
Start squares may be open on all sides, while End squares must be closed on 3 sides.
You cannot completely close off any region of the grid.

In addition, these variations of Sunome have the following extra features:

Paths (borders with a hole in the middle) designate places where the solution should pass through.
Pits (black squares) designate places where the solution does not pass through.
Portals (circled letters) designate places where the solution should pass through and teleport from one portal to the other.
Sunome Cubed is solved similarly but on the surface of a cube. The numbers on the top right, top left, and center left of the border tell you how many walls exist on the corresponding pairs of lines inside the grid. The numbers on the center right, bottom right, and bottom left of the border tell you how many walls exist in the corresponding pairs of rows/columns.

Examine the first example, then solve the other three puzzles.

SOLUTION

The solutions are shown below.

Adam Bontrager December 4, 2023

0 Comments

The Connect Game

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

Two friends are playing the following game:

They start with 10 nodes on a sheet of paper and, taking turns, connect any two of them which are not already connected with an edge. The first player to make the resulting graph connected loses.

Who will win the game?

Remark: A graph is “connected” if there is a path between any two of its nodes.

SOLUTION

The first player has a winning strategy.

His strategy is with each turn to keep the graph connected, until a single connected component of 6 or 7 nodes is reached. Then, his goal is to make sure the graph ends up with either connected components of 8 and 2 nodes (8-2 split), or connected components of 6 and 4 nodes (6-4 split). In both cases, the two players will have to keep connecting nodes within these components, until one of them is forced to make the graph connected. Since the number of edges in the components is either $C^8_2+C^2_2=29$ , or $C^6_2+C^4_2=21$ , which are both odd numbers, Player 1 will be the winner.

Once a single connected component of 6 or 7 nodes is reached, there are multiple possibilities:

The connected component has 7 nodes and Player 2 connects it to one of the three remaining nodes. Then, Player 1 should connect the remaining two nodes with each other and get an 8-2 split.
The connected component has 7 nodes and Player 2 connects two of the three remaining nodes with each other. Then, Player 1 should connect the large connected component to the last remaining node and get an 8-2 split.
The connected component has 7 nodes and Player 2 makes a connection within it. Then, Player 1 also must connect two nodes within the component. Since the number of edges in a complete graph with seven nodes is $C^7_2=21$ , eventually Player 2 will be forced to make a move of type 1 or 2.
The connected component has 6 nodes and Player 2 connects it to one of the four remaining nodes. Then, Player 1 should make a connection within the connected seven nodes and reduce the game to cases 1 to 3 above.
The connected component has 6 nodes and Player 2 connects two of the four remaining nodes. Then, Player 1 should connect the two remaining nodes with each other. The game is reduced to a 6-2-2 split which eventually will turn into either an 8-2 split, or a 6-4 split. In both cases Player 1 will win, as explained above.

Unknown Author November 19, 2023

10 Comments