We solve problems

Problem #PRU-116539

Problems Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other)

13–15 3.0

There are a thousand tickets with numbers 000, 001, ..., 999 and a hundred boxes with the numbers 00, 01, ..., 99. A ticket is allowed to be dropped into a box if the number of the box can be obtained from the ticket number by erasing one of the digits. Is it possible to arrange all of the tickets into 50 boxes?

Problem #PRU-116873

Problems Methods Extremal principle Extremal principle (other) Mathematical induction Mathematical induction (other) Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other)

14–15 4.0

We are given $n + 1$ different natural numbers, which are less than $2 n$ ( $n > 1$ ). Prove that among them there will always be three numbers, where the sum of two of them is equal to the third.

Problem #PRU-31363

Problems Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other) Proof by contradiction

12–14 3.0

a) In a group of 4 people, who speak different languages, any three of them can communicate with one another; perhaps by one translating for two others. Prove that it is always possible to split them into pairs so that the two members of every pair have a common language.

b) The same, but for a group of 100 people.

c) The same, but for a group of 102 people.

Problem #PRU-34976

Problems Probability and statistics Probability theory Discrete distribution Methods Algebraic methods Partitions into pairs and groups; bijections

12–16 4.0

Two people toss a coin: one tosses it 10 times, the other – 11 times. What is the probability that the second person’s coin showed heads more times than the first?

Problem #PRU-35149

Problems Geometry Plane geometry Geometrical inequalities Area inequalities Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (area and volume)

13–15 3.0

In a square which has sides of length 1 there are 100 figures, the total area of which sums to more than 99. Prove that in the square there is a point which belongs to all of these figures.

Problem #PRU-35643

Problems Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (finite number of poits, lines etc.) Geometry Plane geometry Polygons Regular polygons

13–14 4.0

2001 vertices of a regular 5000-gon are painted. Prove that there are three coloured vertices lying on the vertices of an isosceles triangle.

Problem #PRU-35667

Problems Algebra and arithmetic Algebraic geometry Cryptography Methods Algebraic methods Partitions into pairs and groups; bijections

13–14 2.0

The key of the cipher, called the “swivelling grid”, is a stencil made from a square sheet of chequered paper of size $n \times n$ (where $n$ is even). Some of the cells are cut out. One side of the stencil is marked. When this stencil is placed onto a blank sheet of paper in four possible ways (marked side up, right, down or left), its cut-outs completely cover the entire area of the square, where each cell is found under the cut-out exactly once. The letters of the message, that have length $n^{2}$ , are successively written into the cut-outs of the stencil, where the sheet of paper is placed on a blank sheet of paper with the marked side up. After filling in all of the cut-outs of the stencil with the letters of the message, the stencil is placed in the next position, etc. After removing the stencil from the sheet of paper, there is an encrypted message.

Find the number of different keys for an arbitrary even number $n$ .

Problem #PRU-35719

Problems Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other)

12–14 3.0

26 numbers are chosen from the numbers 1, 2, 3, ..., 49, 50. Will there always be two numbers chosen whose difference is 1?

Problem #PRU-60299

Problems Number Theory Divisibility Divisibility of a number. General properties Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other)

13–15 4.0

From the set of numbers 1 to $2 n$ , $n + 1$ numbers are chosen. Prove that among the chosen numbers there are two, one of which is divisible by another.

Problem #PRU-60359

Problems Number Theory Numeral systems Decimal number system Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other)

14–16 4.0

We are given 51 two-digit numbers – we will count one-digit numbers as two-digit numbers with a leading 0. Prove that it is possible to choose 6 of these so that no two of them have the same digit in the same column.