Olympiad problems

1977 All Soviet Union Mathematical Olympiad, 246

Tags: combinatorics , impossible

There are $1000$ tickets with the numbers $000, 001, ... , 999$, and $100$ boxes with the numbers $00, 01, ... , 99$. You may put a ticket in a box, if you can obtain the box number from the ticket number by deleting one digit. Prove that: a) You can put all the tickets in $50$ boxes; b) $40$ boxes is not enough for that; c) it is impossible to use less than $50$ boxes. d) Consider $10000$ $4$-digit tickets, and you are allowed to delete two digits. Prove that $34$ boxes is enough for storing all the tickets. e) What is the minimal used boxes set in the case of $k$-digit tickets?

1971 All Soviet Union Mathematical Olympiad, 154

Tags: combinatorics , dodecagon , impossible

a) The vertex $A_1$ of the regular $12$-gon (dodecagon) $A_1A_2...A_{12}$ is marked with "$-$" and all the rest $--$ with "$+$". You are allowed to change the sign simultaneously in the $6$ vertices in succession. Prove that is impossible to obtain dodecagon with $A_2$ marked with "$-$" and the rest of the vertices $--$ with "$+$". b) Prove the same statement if it is allowed to change the signs not in six, but in four vertices in succession. c) Prove the same statement if it is allowed to change the signs in three vertices in succession.

1941 Moscow Mathematical Olympiad, 081

Tags: combinatorial geometry , square , rectangle , impossible , geometry

a) Prove that it is impossible to divide a rectangle into five squares of distinct sizes. b) Prove that it is impossible to divide a rectangle into six squares of distinct sizes.

1949 Moscow Mathematical Olympiad, 172

Tags: geometry , combinatorial geometry , square , impossible

Two squares are said to be [i]juxtaposed [/i] if their intersection is a point or a segment. Prove that it is impossible to [i]juxtapose [/i] to a square more than eight non-overlapping squares of the same size.

1945 Moscow Mathematical Olympiad, 094

Tags: geometry , combinatorial geometry , impossible , congruent triangles , divide

Prove that it is impossible to divide a scalene triangle into two equal triangles.

1976 All Soviet Union Mathematical Olympiad, 233

Tags: polygon , impossible , combinatorics

Given right $n$-gon wit the point $O$ -- its centre. All the vertices are marked either with $+1$ or $-1$. We may change all the signs in the vertices of regular $k$-gon ($2 \le k \le n$) with the same centre $O$. (By $2$-gon we understand a segment, being halved by $O$.) Prove that in a), b) and c) cases there exists such a set of $(+1)$s and $(-1)$s, that we can never obtain a set of $(+1)$s only. a) $n = 15$, b) $n = 30$, c) $n > 2$, d) Let us denote $K(n)$ the maximal number of $(+1)$ and $(-1)$ sets such, that it is impossible to obtain one set from another. Prove, for example, that $K(200) = 2^{80}$