We solve problems

Problem #PRU-22000

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

12–13 3.0

You are given 11 different natural numbers that are less than or equal to 20. Prove that it is always possible to choose two numbers where one is divisible by the other.

Problem #PRU-22001

Problems Methods Pigeonhole principle Pigeonhole principle (other) Set theory and logic Set theory Union, intersection, and set difference

12–14 4.0

11 scouts are working on 5 different badges. Prove that there will be two scouts \(A\) and \(B\), such that every badge that \(A\) is working towards is also being worked towards by \(B\).

Problem #PRU-23304

Problems Algebra Word Problems Tables and tournaments Number tables and its properties Methods Pigeonhole principle Pigeonhole principle (other)

11–13 2.0

Is it possible to place the numbers \(-1, 0, 1\) in a \(6\times 6\) square such that the sums of each row, column, and diagonal are unique?

Problem #PRU-30682

Problems Algebra Number theory. Divisibility Divisibility of a number. General properties Division with remainders. Arithmetic of remainders Fermat's little theorem Methods Pigeonhole principle Pigeonhole principle (other)

14–15 3.0

Let \(p\) be a prime number, and \(a\) an integer number not divisible by \(p\). Prove that there is a positive integer \(b\) such that \(ab \equiv 1 \pmod p\).

Problem #PRU-30810

Problems Methods Pigeonhole principle Pigeonhole principle (other)

12–13 3.0

At a conference there are 50 scientists, each of whom knows at least 25 other scientists at the conference. Prove that is possible to seat four of them at a round table so that everyone is sitting next to people they know.

Problem #PRU-30811

Problems Algebra Number theory. Divisibility Odd and even numbers Methods Pigeonhole principle Pigeonhole principle (other) Proof by contradiction

13–15 4.0

Each of the 102 pupils of one school is friends with at least 68 others. Prove that among them there are four who have the same number of friends.

Problem #PRU-30815

Problems Combinatorics Painting problems Methods Pigeonhole principle Pigeonhole principle (other)

12–13 3.0

Each of the edges of a complete graph consisting of 6 vertices is coloured in one of two colours. Prove that there are three vertices, such that all the edges connecting them are the same colour.

Problem #PRU-30830

Problems Methods Pigeonhole principle Pigeonhole principle (other)

13–14 4.0

In some state, there are 101 cities.

a) Each city is connected to each of the other cities by one-way roads, and 50 roads lead into each city and 50 roads lead out of each city. Prove that you can get from each city to any other, having travelled on no more than on two roads.

b) Some cities are connected by one-way roads, and 40 roads lead into each city and 40 roads lead out of each. Prove that you can get form each city to any other, having travelled on no more than on three roads.

Problem #PRU-31086

Problems Methods Pigeonhole principle Pigeonhole principle (other)

11–13 4.0

In the oriented graph, there are 101 vertices. For each vertex, the number of ingoing and outgoing edges is 40. Prove that from each vertex you can get to any other, having gone along no more than three edges.

Problem #PRU-31295

Problems Algebra Number theory. Divisibility Equations in integer numbers Methods Pigeonhole principle Pigeonhole principle (other)

11–13 4.0

There are 100 notes of two types: \(a\) and \(b\) pounds, and \(a \neq b \pmod {101}\). Prove that you can select several bills so that the amount received (in pounds) is divisible by 101.