#maths problems

#maths was an IRC channel full of crazy miracles. We used to have a problem 'on the go', set by one of the channel users. Everyone else then worked together to try to solve it.

The problems

There were ten problems in all.

Problem 1. Geoff and his frogs

There are $$n \geq 2$$ line segments in the plane such that every two segments cross, and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it, facing the other endpoint. Then he will clap his hands $$n - 1$$ times. Every time he claps, each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will ever occupy the same intersection point at the same time.

1. Prove that Geoff can always fulfil his wish if $$n$$ is odd.
2. Prove that Geoff can never fulfil his wish if $$n$$ is even.

IMO 2016, problem 6.

Problem 2. Two digit squares

Squares which are composed of only two distinct digits seem to be very common: 16, 25, 36, 49, 64, 81, 100, 121, 144, 225, 400, 441, 484. Show how to construct infinitely many.

Squares which are comosed of only two distinct non-zero digits are somewhat rarer. Here they are up to $$10^{14}$$: 16, 25, 36, 49, 64, 81, 121, 144, 225, 441, 484, 676, 1444, 7744, 11 881, 29 929, 44 944, 55 225, 69 696, 9 696 996, 6 661 661 161. Are there infinitely many?

M500 magazine, issue 271.

There are $$n$$ lamps $$L_0, \dots, L_{n−1}$$ in a circle ($$n > 1$$), where we denote $$L_{n+k} = L_k$$. (A lamp at all times is either on or off.) Perform steps $$s_0, s_1, \dots$$ as follows: at step $$s_i$$, if $$L_{i−1}$$ is lit, switch $$L_i$$ from on to off or vice versa, otherwise do nothing. Initially all lamps are on. Show that:

1. There is a positive integer $$M(n)$$ such that after $$M(n)$$ steps all the lamps are on again;
2. If $$n = 2^k$$, we can take $$M(n) = n^2 − 1$$;
3. If $$n = 2^k + 1$$, we can take $$M(n) = n^2 − n + 1$$.

IMO 1993, day 2, problem 3.

Problem 4. Penpals

Seventeen people correspond by mail with one another — each one with all the rest. In their letters only three different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

IMO 1964, problem 4.

This week we think about a set of four problems about the movement of checkers along a row of spaces.

94. Jumping checkers. Imagine a row of 7 checkers squares, numbered 1 to 7. Place three white checkers in squares 1, 2 and 3 and three black ones in squares 5, 6 and 7. Shift the white checkers to the square occupied by the black ones, and vice versa. You may move a checker forward to the adjacent unoccupied square, if any. You may jump a checker forward over and adjacent checker into the vacant square. The solution requires 15 moves.

95. White and black. Take 4 black and 4 white checkers (or 4 pennies and 4 other coins) and put them on a table in a row, white, black, white, black and so on. Leave a vacant place at one end which can hold 2 checkers. After 4 moves, all the black checkers should be on one side and the white ones on the other. A move consists of shifting 2 adjacent checkers, keeping their order, into any vacant space.

96. Complicating the problem. In the last problem, 8 checkers took 4 moves. Show how 10 checkers take 5 moves, 12 take 6, and 14 take 7.

97. The general problem. From Problems 95–96, can you derive a general procedure for arranging $$2n$$ checkers in $$n$$ moves?

– Boris Kordemsky, The Moscow Puzzles: 359 Mathematical Recreations.

Problem 6. Some more Moscow puzzles

278. A logical draw. Three puzzle competitors are blindfolded. A white piece of paper is glued to each one's forehead and they are told that not all the pieces of paper are black. The blindfolds are removed and the prize goes to the first man to deduce whether the paper on his forehead of white or black. All three announce white at the same time. Why?

279. Three sages. Three ancient Greek philosophers took a nap under a tree. While they were asleep, a prankster smeared their faces with charcoal. On awakening, they began to laugh, each thinking the other two were laughing at each other. Suddenly one man stopped laughing. How did he realise his own face was also smeared?

308. Is there such a number? Is there a number which when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6 gives a remainder of 4?

– Boris Kordemsky, The Moscow Puzzles: 359 Mathematical Recreations.

Problem 7. A Fibonacci sum

The Fibonacci sequence $$F_n$$ is given by 1, 1, 2, 3, 5, 8, 13, 21, ... where $$F_n$$ is the $$n$$th Fibonacci number (i.e. $$F_1 = 1$$, $$F_2 = 1$$, $$F_3 = 2$$ and the sequence is defined by $$F_n = F_{n-1} + F_{n-2}$$.

Find a value $$x > 0$$ such that $\sum_{n=1}^{\infty} x^n F_n = x F_1 + x^2 F_2 + x^3 F_3 + x^4 F_4 + \cdots = 1$

Problem 8. Some problems from Seye

1. You are standing in a school hallway lined with one hundred closed lockers. You then open all one hundred lockers. After this, you then close every second locker (so the second, fourth, sixth, ..., ninety-eighth and hundredth are all closed). Then, you go to every third locker and open it if it is closed or close it if it is open (let's call this toggling the locker for our discussion). You proceed to toggle every $$n$$th locker on pass number $$n$$. So, for example, on pass number 16 you will toggle every sixteenth locker.

1. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are now open?
2. In a hall with $$x$$ lockers, how many lockers remain open after pass number $$x$$?

2. Imagine two one-litre bottles each $$n$$% full of respectively liquid A and liquid B. You top up B from A and A from B. how many rounds do you have to do to get a 50% (to 2 d.p.) mix of A and B in each (assuming that when you top up, the resulting mixture is homogeneous)?

3. You go round a one mile racetrack at an average speed of 50mph. At what speed do you have to do a second lap to average 100mph for the two laps?

Problem 9. Chessboard puzzles

On an infinite chessboard, a game is played as follows. At the start, $$n^2$$ pieces are arranged on the chessboard in an $$n$$ by $$n$$ block of adjoining squares, one piece in each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed. Find those values of $$n$$ for which the game can end with only one piece remaining on the board.

IMO 1993, day 1, problem 3.

Consider an $$n \times n$$ square board, where n is a fixed even positive integer. The board is divided into $$n^2$$ unit squares. We say that two different squares on the board are adjacent if they have a common side. $$N$$ unit squares on the board are marked in such a way that every square (marked or unmarked) on the board is adjacent to at least one marked square. Determine the smallest possible value of $$N$$.

IMO 1999, day 1, problem 3.

Problem 10. A long division

All the Xs in this long division are digits, but not all the same. It's possible to uniquely determine every digit in this working from the information presented, and knowledge of the long division method.