Traveling Salesmen

Between every pair of major cities in Russia, there is a fixed travel cost for going from either city to the other. Traveling salesman Alexei Frugal starts in Moscow and visits all cities exactly once, choosing every time the cheaper flight to a city he has not visited so far. Salesman Boris Lavish starts in St Petersburg and visits all cities exactly once, choosing every time the most expensive flight to a city he has not visited so far. Can Alexei end up spending more money than Boris after they end their journeys?

No, it is impossible. For every trip of Alexei we will choose a trip of Boris, which costs at least as much.

Let the number of cities is n and Alexei visits them in order 1 -> 2 -> … -> n.

If Boris visits city n-1 before city n, then pair Alexei’s trip (n-1, n) with Boris’ trip (n-1, #). Notice that C(n-1, n) < C(n-1, #).

If Boris also visits city n-2 before city n, then pair Alexei’s trip (n-2, n-1) with Boris’ trip (n-2, #). Notice that C(n-2, n-1) < C(n-2, n) < C(n-2, #).

Continue like this until get to a city k which Boris visits after city n. Then pair Alexei’s trip (k, k+1) with Boris’ trip (n, #). Notice that C(k, k+1) < C(k, n) < C(n, #).

Next, check whether Boris visits city k – 1 before city k, and pair Alexei’s trip (k-1, k) with either (k-1, #) or (k, #). Continue like this, until pair all of Alexei trips with more expensive Boris trips.

Chess Aggression

Starting from this position, can you make 39 consecutive checks – 20 from White and 19 from Black?

The sequence is as follows:

1. Nh2+ f1N+
2. Rxf1+ gxf1N+
3. Ngxf1+ Bg5+
4. Qxg5+ Bg2+
5. Nf3+ exf3+
6. Kd3+ Nc5+
7. Qxc5+ Re3+
8. Nxe3+ c1N+
9. Qxc1+ d1Q+
10. Qxd1+ e1N+
11. Qxe1+ Bf1+
12. Nxf1+ f2+
13. Ne3+ f1Q+
14. Qxf1+ Qxf1+
15. Nxf1+ Re3+
16. Nxe3+ b1Q+
17. Rxb1+ axb1Q+
18. Nc2+ Nf2+
19. Bxf2+

The Answer to This Riddle Is a Number

The key to this riddle is only for you
Below are instructions, above this the clue
First strike the one near the head of a year
Then remove he who begins a cheer
Next take away the end of a tunnel
Then let us go to solve this puzzle
What you first took you must now take again
With three you are left, but fret not dear friend
Fattest to front and thinnest to rear
Add in two “eyes” and all becomes clear

Remark: The instructions in this riddle are quite literal.

Source: Puzzling StackExchange

The answer is XVIII, or 18 in Roman numerals.

The key is “only for you” – EXCLUSIVE. Remove “the one near the head of a year” – E. Remove “he who begins a cheer” – C. Remove “the end of the tunnel” – L. Remove “us” – U and S. Remove again E. Now you are left with X, I, V. Arrange them “fattest to front and thinnest to rear” – X > V > I. Add “two ‘eyes'” – I and I, so you get XVIII=18.

Policeman and Thief

There is a town which consists of 3 horizontal and 3 vertical roads, separated by 4 blocks from each other. There are a policeman and a thief running along the roads of the town, with speeds of 21km/h and 10km/h respectively. Show that no matter how the thief tries to hide, the policeman has a strategy ensuring he will eventually see him and shoot him.

Remark: The policeman can see the thief if they are on the same road at some moment. He has no idea about his position at any time.

A working strategy for the policeman would be to go to the center and to start encompassing the four blocks clock-wise one by one, in a clockwise manner.

Since the policeman is twice as fast as the thief if the thief is in the center of the town at some point, then there exists a moment in which the policeman is in the center, and the thief is not on the boundary, i.e. he gets shot.

Now, assuming the thief never visits the center, his angle with respect to the coordinate system defined by the two middle roads changes continuously. The angle of the policeman with respect to the same coordinate system can be defined to change continuously as well. Since the policeman needs less time to increase his angle with 360 degrees than the thief, there will be a moment when the two have the same angle. However, this implies that the policeman will be able to see the thief and shoot him.

Knocked Off Piece

The following position occurs in a real game, right after one of the pieces gets knocked off the board. What was the piece?

It was a black knight. First, notice that the black pawns have moved 14 times diagonally and thus they have taken 14 pieces. Therefore the knocked off piece is black. Since it is impossible for both kings to be checked at the same time, the missing piece was positioned on a2. It couldn’t be a queen or a rook, because the white king would be checked both by it and the pawn on b3, which is impossible. Therefore the missing piece is either the black white-squared bishop or the black knight. However, the pawns on b7 and d7 haven’t been moved the entire game and then the black white-squared bishop hasn’t either. Thus we conclude that the knocked off piece is a black knight.

15 Puzzle

On the picture, you can see the famous “15 Puzzle”. The rules are simple – you can slide any of the 15 squares to the empty spot if it neighbors with it. The question is: if the squares with numbers 14 and 15 are exchanged, can you solve the puzzle, i.e. can you bring it to the state shown on the picture?

No, you can’t. In order to see this, at each moment count the number of pairs of little squares, which are wrongly ordered. For example, if the numbers on the first row are 7, 2, 12 and 5 in this order, then 7 and 2, 7 and 5, and 12 and 5 are wrongly ordered. Notice that after every move you make, the number of wrongly ordered pairs changes with an odd number – ± 3 or ± 1. If you want to go from the state in which squares 14 and 15 are exchanged to the solved state on the picture, you must make an even number of moves and therefore you would change the number wrongly ordered pairs by an even number. However, the number of wrongly ordered squares in the starting state is 1, whereas in the ending state is 0, which yields a contradiction.

Prisoners and Boxes

There are 100 inmates living in solitary cells a prison. In a room inside the prison there are 100 boxes and in each box there is a paper with some prisoner’s name (all different). One day the warden tells the prisoners that he has aligned next to the wall in a special room 100 closed boxes, each of them containing some prisoner’s name (all different). He will let every prisoner go to the room, open 50 of the boxes, then close them and leave the room the way it was, without communicating with anybody. If all prisoners find their names in the boxes they open, they will be set free, otherwise they will be executed. The prisoners are allowed to come up with a quick plan before the challenge begins. Can you find a strategy which will ensure a success rate of more than 30%?

The prisoners can assign numbers to their names – 1, 2, 3, … , 100. When prisoner X enters the room, he should open first the X-th box in the line. If he sees inside prisoner’s Y name, he should open next the Y-th box in the line. If he sees in it prisoner’s Z name, he should open next the Z-th box in the line and so on.

The only way which will prevent all prisoners from finding their names is if there is a long cycle of boxes (length 51 or more), such that the first box in the cycle directs to the second box in it, the second box to the third box, the third box to the fourth box and so on.

It is not hard to compute that the probability of having a cycle of length K>50 is exactly 1/K. Then the probability for failure will be equal to the sum 1/51 + 1/52 + … + 1/100, which is very close to ln(100) – ln(50) = ln(2) ~ 69%. Therefore this strategy ensures a success rate of more than 30%.

Sum to 15

Tango and Cash are playing the following game: Each of them chooses a number between 1 and 9 without replacement. The first one to get 3 numbers which sum to 15 wins. Does any of them have a winning strategy?

Place the numbers from 1 to 9 in a 3×3 grid so that they form a magic square. Now the game comes down to a standard TIC-TAC-TOE and it is well-known that it always leads to a draw using optimal strategies by both players.

Gods of Truth

You encounter three Gods in a room – the God of Truth, the God of Lie and the God of Uncertainty. You don’t know which one is which, but know that the God of Truth always says the truth, the God of Lie always says the lie and the God of Uncertainty sometimes lies and sometimes says the truth. You can ask in succession each of the Gods a unique question, to which they can reply only with “Yes” or “No”. However, their responses will be in their native language – “Da” or “Ne”, and you don’t know which translation to which answer corresponds. Your task is to figure out what questions to ask the Gods, so that will recognize which one of them is the God of Truth, which one is the God of Lie and which one is the God of Uncertainty.

Label the gods with numbers – 1, 2, and 3.

First, ask god 1 “If I ask you whether god 2 is random, would you say ‘Da’?”. If he responds “Da”, then god 3 is not the god of uncertainty. If he responds “Ne”, then god 2 is not the god of uncertainty. In both cases we will be able to find a god which is not the god of uncertainty, let without of generality that is god 3.

Next, ask god 3 “If I ask you whether you are the God of Lie, would you say ‘Da’?”. If he says “Da”, then he is the God of Truth. If he says “No”, then he is the God of Lie.

Finally, ask god 3 whether god 1 is the God of Uncertainty and conclude the identities of all gods.