18th Tournament of Towns

Autumn 1996, A-level.

Your total score is based on the three problems for which you earn the most points; the scores for the individual parts of a single problem are summed. Points for each problem are shown in brackets [ ].

Juniors

1. [3] Can one paint some four points of the plane red and some other four points black so that for any three points of the same color (black or red), these three points and a point of the other color are the vertices of a parallelogram?

N.Vasiliev

2. Does there exist a triple of different prime integers p, q, r such that p2 + d is divisible by the product qr, q2 + d is divisible by rp, r2 + d is divisible by pq if
a) [2] d=10,
b) [2] d=11.

V.Senderov

3. [5] Prove the inequality (where n!=1·2·...·n):
2/2! + 7/3!+14/4!+23/5!+...+(k2-2)/k!+ ... + 9998/100! < 3

V.Senderov

4a. [2] A square is cut into equal right triangles with the legs 3 and 4. Prove that the total number of the triangles is even. 4b. [4] A rectangle is cut into equal right triangles with the legs 1 and 2. Prove that the total number of the triangles is even.

A.Shapovalov

5. [8] Can one find a 6-digit number A such that in no one of the 500000 numbers A, 2A, 3A, ... , 500000A the last 6 digits are equal (like ...000000, or ...1111111 etc.) ?

S.Tokarev

6. The 'mathlotto' card is a table of 36=6×6 cells. A player has to mark 6 of the cells in the card and to send the card (in an envelope). After it, a set of 6 'losing' (forbidden) cells will be published in a certain newspaper. Prove that
a) [5] the player can fill in 9 cards so that at least one of the cards will certainly 'win' - it will contain no losing cells,
b) [5] but 8 cards are not sufficient for the guaranteed win.

S.Tokarev

Seniors

1. [3] Can one paint some four vertices of a cube red and the other four vertices black so that any plane passing through three vertices of the same color (black or red) contains a vertex of the other color?

A.Möbius, I.Sharygin

2a. [3] Prove for any n>2 the inequalities (where k!=1·2·...·k):
3 - 2/(n-1)! < (22-2)/2!+(32-2)/3!+...+(n2-2)/n! < 3
2b. [3] Find some positive integers a, b, c for which (for any n>2)
b - c/(n-2)! < (23-a)/2!+ (33-a)/3!+...+ (n3-a)/n! < b holds.

V.Senderov, N.Vasiliev

3. [5] Let A',B',C',D',E',F' be the midpoints of the sides AB, BC, CD, DE, EF, FA of an arbitrary convex hexagon ABCDEF respectively. The areas of the triangles ABC', BCD', CDE', DEF', EFA', FAB' are known. Find the area of the hexagon ABCDEF.

A.Lopschits, N.Vasiliev

4. [10] Prove that no function y=f(x) (even though discontinuous) exists for which f(f(x))= x2-1996 for all (real) x.

S.Bogatyj, M.Smurov

5a. [4] On a certain circle island, there are four sea ports: 1, 2, 3, and 4, listed clockwise. There is a plane net of roads on this island, all of them one-way, such that there are no cyclic routes: once you leave a certain port or a branch point (where the roads meet each other or branch off), there is no way you can return back. For any two sea ports i and j, let fij denote the number of different non-self-intersecting routes for travel from i to j. Show that f14·f23 > f13·f24.
5b. [6] Suppose there were six ports on the island: 1, 2, 3, 4, 5, and 6, in the clockwise order. Show that
f16·f25·f34+f15·f24·f36+f14·f26·f35 > f16·f24·f35+f15·f26·f34+f14·f25·f36
('Plane net' means that there are no intersections of the roads at different levels on the island.)

S.Fomin

6. The 'mathlotto' card is a table of 100=10×10 cells. A player has to mark 10 of the cells in the card an to send the card (in an envelope). After it, a set of 10 'losing' (forbidden) cells will be published in newspaper. Prove that
a) [5] the player can fill in and send 13 cards so that at least one of the cards will certainly 'win' - it will contain no losing cells,
b) [5] but 12 cards are not sufficient for the guaranteed win.

S.Tokarev