Y-Town

In Y-town all crossroads are Y-shaped, and there are no dead-end roads. Is it true that if you start from any point in the city and start walking along the roads, turning alternatingly left and right at each crossroad, eventually you will arrive at the same spot?

Yes, it is true. If you start walking forward, eventually you will end up in a loop. It is easy to see that your entire path, including the starting spot, must belong to this loop. Therefore, eventually you will end up in the starting spot again.

Reverse Puzzling

George is a great puzzler, so I was extremely surprised when he didn’t immediately know the answer to a really famous puzzle. It’s a puzzle that you probably did years ago, and have heard so often you can do it from memory rather than working it out. It’s also not really that difficult, so I was also surprised when it appeared to be stumping him.

“Come on, surely you know this one,” I said.

“I don’t. And don’t call me Shirley.” He answered grumpily. I could tell his mood was declining rapidly, but like any great puzzler he was down and not out, and I watched his facial expression change as he reached into his mental bag of tricks. He nodded towards a conveniently located whiteboard. “Have you got a marker for that?”

I handed him one, and he drew up the following diagram:

He stepped back, admiring his work, beaming proudly. “Well, now the solution is very obvious!” he commented. And indeed it was. The question for you is:

What is the puzzle?

Source: Puzzling StackExchange

The diagram represents the puzzle about the man, trying to cross the river with a fox (F), a chicken (C) and a sack of barley (B). He can carry at most one of them with himself in the boat, and he shouldn’t leave the chicken alone with the fox or with the barley on one side of the river. The red dots represent all admissable configurations and the lines between them all available moves.

Princess in a Palace

A princess is living in a palace which has 17 bedrooms, arranged in a line. There is a door between every two neighboring bedrooms and also a hallway which connects them all. Every night the princess moves through the inner doors from one bedroom to another. Every morning for 30 consecutive days you are allowed to go to the hallway and knock on one of the 17 doors. If the princess is inside, you will marry her. What your strategy would be?

You knock on doors:
2, 3,…, 15, 16, 16, 15,…, 3, 2.
This makes exactly 30 days. If during the first 15 days you don’t find the princess, this means that every time you were knocking on an even door, she was in an odd room, and vice versa. Now it is easy to see that in the next 15 days you can’t miss her.

Invisible King

The white king has made himself invisible. Where is he?

The white king is on c3. Since he cannot be currently on b3 (he will be in double check from the black rook and the black bishop), Black must be currently in check from the white bishop. That’s possible only if White has given a discovered check with his king. That’s possible only if on the previous move, the white king was on b3 and was in double check. The only possible way for this to happen is if Black gave two discovered checks at the same time. The one way to do this is if a black pawn on b4 captured a white pawn on c3 using en passant. Thus after b4xc3, the white king has just captured the black pawn on c3, and that is where he is currently hiding.

35 Moves

Design a game that takes less than 35 moves to get to the position below.

One possible solution is:

1.d3 h6 2.Bxh6 f5 3.Qd2 f4 4.Qxf4 a5 5.Qxc7 Kf7 6.g3 Kg6 7.Bg2 Kh5 8.Bxb7 Kg4 9.Nf3 Kh3 10.Bxc8 e5 11.Bxg7 e4 12.Kd2 e3+ 13.Kxe3 Kg2 14.Ng1 Kf1 15.Kf3 Ke1 16.Qxa5+ Bb4 17.Nc3+ Kd2 18.Rf1 Rh3 19.Bxd7 Nh6 20.Nd1 Kc1 21.Bxh6+ Kb1 22.Bc1 Na6 23.Kg2 Rc8 24.Bxh3 Rc3 25.Nxc3+ Ka1 26.Nb1 Nc5 27.Rd1 Be1 28.Qxe1 Ne4 29.Kf1 Nd2+ 30.Rxd2 Qd5 31.Qd1 Qg2+ 32.Ke1 Qf1+ 33.Bxf1

Royal Wedding

A prince decides to get married to the prettiest girl in his kingdom. All 100 available ladies go to the palace and show themselves to the prince one by one. He can either decide to marry the girl in front of him or ask her to leave forever and call the next one in line. Can you find a strategy which will give the prince a chance of 25% to get married to the prettiest girl? Can you find the best strategy?

Remark: Assume that the prince can objectively compare every two girls he has seen.

A strategy which ensures a chance of 25% is the following:
The prince banishes the first 50 girls which enter the palace and then gets married to the first one which is prettier than all of them (if such one arrives). If the prettiest girl in the kingdom is in the second 50, and the second prettiest girl is in the first 50, he will succeed. The chance for this is exactly 25%.

The best strategy is to wait until ~1/e of all girls pass, and then choose the first one which is more beautiful than all of them. This yields a chance of ~37% for succeeding. The proof is coming soon.

Two Monks on a Mountain

Two monks are standing on the two sides of a 2-dimensional mountain, at altitude 0. The mountain can have any number of ups and downs, but never drops under altitude 0. Show that the monks can start climbing/descending the mountain simultaneously on its 2 sides, keeping their altitudes equal at all times, until they meet each other at the same point.

Coming soon.

Spiders and a Fly

There are a fly and three spiders on the edges of a cube. If the spiders’ velocities are at least 1/3 of the fly’s velocity, and all insects can travel only along the edges of the cube, show that the spiders can eventually catch the fly.

Choose two opposite edges of the cube, then let two of the spiders “protect” them from the fly. You can do this by keeping the distance from the two spiders to the edges’ endpoints at most 1/3 of the distance from the fly to these endpoints. The remaining parts of the cube do not contain any loops, so the third spider can easily catch the fly there.