Problem 1 (Liceo Scientifico Leonardo, Brescia, Italy)
Find all pairs (m, n) of non-negative integers having the following three properties:
a) n is not divisible by the square of a prime number;
b) n has no prime divisor p with 33 < p <332; c) at least one of the numbers
2 2
33 1 2
mn
n + and
) 1 ( 33
1 2
3 2
− +
n m
m
is an integer.
Problem 2 (Liceo Scientifico Michelangelo di Forte dei Marmi, Italy)
The orginal problem in Italian reads: La LOLA senza TEO è CUPA, e LOLA vale 22. Quanti TEO, se non vanno dalla LOLA, la fanno diventare cupa?
Its literal translation is: LOLA without TEO is CUPA and LOLA is 22. How many TEOs not going to LOLA will make her sad?
(Note that in Italian the word CUPA means sad, while LOLA and TEO are the names of two friends.)
Problem 3 (American College, Sofia, Bulgaria)
A square of size 9×9 is divided into 81 squares of size 1×1. Write all integers from 1 to 81 in the 1x1 squares so that the sums of the numbers written in the 9 squares of size 3×3 are equal.
Problem 4 (Istituto Statale 'C. Lorenzini', Pescia, Italy)
A box contains 48 cylindrical cans ordered in 8 rows so that each row contains 6 cans. Show that one can put 50 cans in the same box.
Problem 5 (High School of Mathematics, Rousse, Bulgaria)
Nine books are labeled by the digits 1, 2,…,9 and are divided into five groups as shown below
Appendix to Chapter 3 58
We assign to each group the number formed by the digits of the books in the group.
(For example, the numbers assigned to the five groups in the picture are 7, 28, 196, 34 and 5.)
Change the labels of the books so that the following three numbers are equal: the number of the third group, the product of the numbers of the first and the second group, and the product of the numbers of the fourth and the fifth group. Give all possible solutions.
Problem 6 (Sofia High School of Mathematics, Bulgaria)
Appendix to Chapter 3 59 Hints and solutions
1. First, we consider the case, when the number 2
2
33 1 2
mn
n + is an integer. Note that the denominator 22n + 1= 4n + 1 is not divisible by 3; so m=0. Hence we have to find all n such that n2 divides 22n + 1. An obvious solution is n = 1. Suppose now that n
> 1
and let p be the least prime that divides n. Setting n = kp we have )
(mod 1 16 ) (mod 1 4
) (mod 0 1
22n + ≡ n2 ⇒ kp ≡− p ⇒ kp ≡ p . Let now d be the smallest power of 16 which is congruent to 1 modulo p. Then d divides φ(p) = p – 1 as well as kp=n and if d > 1, then p is not the least prime divisor of n. So d = 1 and p = 3 or p = 5. But we know that 3 cannot divide 22n + 1, so n = 5 and n = 5k. If k=1, then n=5 is a solution, since 210 + 1 = 1025 is divided by 25. One can verify that the assumption k >1 leads to a contradiction. Indeed, using the same argument as above one can show that the least prime divisor q of k divides 165 – 1=
(52)(41)(3)(11)(31) and the assumptions a) and b) of the problem imply that q = 3,11,31. To exclude these cases one can use the following lemma:
Lemma. If r is a prime of the form 4k+3 and r divides x2 + y2 , then r divides x and y. So the only solutions in this case are (m,n)=(0,1) and (0,5).
Now consider the case when the number
) 1 ( 33
1 2
3 2
− +
n m
m
is an integer. As in the previous case one can conclude that n=0. Therefore, we have to find all non-negative integers m, such that m3 – 1 divides 22m + 1. Note that m = 0 is an obvious solution and we can assume that m > 1. Note also that m3 – 1 has a prime divisor of the form 4k+3. Indeed, m3 – 1 = (m – 1)(m2 + m + 1) and considering m modulo 4, one can see that either m – 1 or m2 + m + 1 is an integer of the form 4k+3, hence at least one of them has a prime divisor of this form. Let p be the least prime of the form 4k+3 that divides m3 – 1. Then p = 4k+3 is a divisor of the numerator 22m + 1 and applying the Lemma above we conclude that the only solution in this case is (m, n) = (0, 0).
2. The statement LOLA without TEO is CUPA can be interpreted as follows:
LOLA – TEO CUPA
where each capital letter is a digit. The sentence LOLA is 22 can be interpreted in the following way: the sum of the digits of LOLA is 22. The question How many TEOs not going to LOLA will make her sad? could be interpreted as What is the integer part of the number (LOLA + CUPA)/TEO?”
Appendix to Chapter 3 60
All possible solutions according to the above interpretations are given in the table below.
TEO LOLA CUPA [(LOLA + CUPA)/TEO]
130 8086 7956 123
150 8086 7936 106
930 8086 7156 16
950 8086 7136 16
120 7078 6958 116
130 7078 6948 107
140 7078 6938 100
150 7078 6928 93
920 7078 6158 14
930 7078 6148 14
940 7078 6138 14
950 7078 6128 13
The question How many TEOs not going to LOLA will make her sad? could be reformulated as How many TEOs are needed to make LOLA happy? In this case the obvious answer is that one TEO is sufficient to make LOLA happy.
3. Note first that if we solve the problem for the numbers from 0 to 80 then we can solve the given problem by adding 1 to each of the numbers in the table found.
Now the idea is to write the numbers from 0 to 80 in base 3 and to place these numbers (we consider all of them as 4-digit numbers in base 3) in the table so that in every 3x3 square we have equal quantity of every digit 0, 1, 2 on each of the positions in the four-digit number. To do this we use different approaches for each of the four positions in order to avoid constructing the same number on two different places of the table.
For the first digit we use the following pattern: 0s in rows 1, 4, 7, then 1s in rows 2, 5, 8, and 2s in rows 3, 6, 9.
For the second digit we write 0s in columns 1, 4, 7, then 1s in columns 2, 5, 8, and 2s in columns 3, 6, 9.
For the third digit we put 0, 0, 0, 1, 1, 1, 2, 2, 2 in columns 1, 4, 7, then 1, 1, 1, 2, 2, 2, 0, 0, 0 in columns 2, 5, 8, and 2, 2, 2, 0, 0, 0, 1, 1, 1 in columns 3, 6, 9.
Finally, for the last digit we write 0, 0, 0, 1, 1, 1, 2, 2, 2 in rows 1, 4, 7, then 1, 1, 1, 2, 2, 2, 0, 0, 0 in rows 2, 5, 8, and 2, 2, 2, 0, 0, 0, 1, 1, 1 in rows 3, 6, 9.
Each of these patterns ensures equal distribution of the corresponding digit in each 3x3 square and hence equal sum of the numbers therein. The resulting table is as follows:
Appendix to Chapter 3 61
0000 0110 0220 0001 0111 0221 0002 0112 0222 1001 1111 1221 1002 1112 1222 1000 1110 1220 2002 2112 2222 2000 2110 2220 2001 2111 2221 0010 0120 0200 0011 0121 0201 0012 0122 0202 1011 1121 1201 1012 1122 1202 1010 1120 1200 2012 2122 2202 2010 2120 2200 2011 2121 2201 0020 0100 0210 0021 0101 0211 0022 0102 0212 1021 1101 1211 1022 1102 1212 1020 1100 1210 2022 2102 2212 2020 2100 2210 2021 2101 2211
Then by writing the numbers in the above table in base 10 and adding 1 to each of them we get the following solution of the problem:
1 13 25 2 14 26 3 15 27 29 41 53 30 42 54 28 40 52 57 69 81 55 67 79 56 68 80 4 16 19 5 17 20 6 18 21 32 44 47 33 45 48 31 43 46 60 72 75 58 70 73 59 71 74 7 10 22 8 11 23 9 12 24 35 38 50 36 39 51 34 37 49 63 66 78 61 64 76 62 65 77
4. We may assume the cans are of radius 1, hence the box has dimensions 12 x 16.
Taking the side of length 12, we put 6 cans in the first row as shown in Fig. 1. Then we put five cans over them (only the first one of them is shown in Fig.1), then 6 cans over these 5 cans and so on. We claim that we can put in the box 5 rows of 6 cans and 4 rows of 5 cans between them. Indeed, let us denote by A and D the centres of the first cans in the first two rows of 6 cans (Fig. 1). Then the smallest rectangle covering all 50 cans has sides of lengths 12 and 4AD+2. On the other hand, it is easy to check that AD=2*√3. Since 4AD+2 = 8*√3 + 2< 16 we see that we can put 50 cans in the box.
Appendix to Chapter 3 62
Fig.1
5. We label the books by the digits A, B, C, D, E, F, G, H, I as shown below:
A B C D E F G H I
It is easy to see that the digits F, A, C, H, I, B,G are different from 1 (prove this!).
Then show that up to a symmetry we have to consider the following four cases according to the positions of the digits 1 and 5:
A 5 C 1 E F G H I
A 5 C D 1 F G H I
A B C 5 1 F G H I
A B C 1 5 F G H I
Finally, prove that we have solutions only in the first and the fourth case and that all the solutions of the problem are given as follows:
3 5 8 1 7 4 2 9 6
6 2 9 1 7 4 5 8 3
2 7 8 1 5 6 3 9 4
4 3 9 1 5 6 7 8 2
Appendix to Chapter 3 63 6. One can prove the following assertion: If a board is painted in green and another board is painted in red, then there are two consecutive boards of different colors between these two fixed boards.The strategy of Huck can be described as follows.
He chooses the first board from left to right that is not painted and paints this board in a colour different from the colors chosen two days before.
Then one can show that there are at least 49 consecutive couples in different colors and this is the desired maximum.
Appendix to Chapter 3 64