We solve problems

Problem #PRU-32088

Problems Methods Examples and counterexamples. Constructive proofs Pigeonhole principle Pigeonhole principle (other) Discrete Mathematics Algorithm Theory Theory of algorithms (other)

13–16 4.0

It is known that a certain polynomial at rational points takes rational values. Prove that all its coefficients are rational.

Problem #PRU-32092

Problems Methods Algebraic methods Counting in two ways Fun Problems Word Problems Tables and tournaments Number tables and its properties

10–12 2.0

In each square of a rectangular table of size \(M \times K\), a number is written. The sum of the numbers in each row and in each column, is 1. Prove that \(M = K\).

Problem #PRU-32095

Problems Geometry Plane geometry Visual geometry

10–13 2.0

Is it possible to draw this picture (see the figure), without taking your pencil off the paper and going along each line only once?

Problem #PRU-32104

Problems Discrete Mathematics Set theory and logic Mathematical logic Mathematical logic (other)

10–13 2.0

One of five brothers baked a cake for their Mum. Alex said: “This was Vernon or Tom.” Vernon said: “It was not I and not Will who did it.” Tom said: “You’re both lying.” David said: “No, one of them told the truth, and the other was lying.” Will said: “No David, you’re wrong.” Mum knows that three of her sons always tell the truth. Who made the cake?

Problem #PRU-32110

Problems Number Theory Numeral systems Decimal number system Divisibility Division with remainders. Arithmetic of remainders Division with remainder Methods Pigeonhole principle Pigeonhole principle (other)

12–14 4.0

Reception pupil Peter knows only the number 1. Prove that he can write a number divisible by 1989.

Problem #PRU-32124

Problems Methods Pigeonhole principle Pigeonhole principle (finite number of poits, lines etc.) Geometry Solid geometry Tetrahedron and pyramid Particular cases of tetrahedra Regular tetrahedron

13–15 3.0

A scone contains raisins and sultanas. Prove that inside the scone there will always be two points 1cm apart such that either both lie inside raisins, both inside sultanas, or both lie outside of either raisins or sultanas.

Problem #PRU-32132

Problems Methods Extremal principle Extremal principle (other) Discrete Mathematics Set theory and logic Order relations Algebraic methods Proof by exhaustion

13–15 3.0

The order of books on a shelf is called wrong if no three adjacent books are arranged in order of height (either increasing or decreasing). How many wrong orders is it possible to construct from \(n\) books of different heights, if: a) \(n = 4\); b) \(n = 5\)?

Problem #PRU-32135

Problems Methods Pigeonhole principle Pigeonhole principle (finite number of poits, lines etc.) Discrete Mathematics Combinatorics Systems of points and line segments Systems of points and line segments (other)

12–14 3.0

101 points are marked on a plane; not all of the points lie on the same straight line. A red pencil is used to draw a straight line passing through each possible pair of points. Prove that there will always be a marked point on the plane through which at least 11 red lines pass.

Problem #PRU-32783

Problems Methods Pigeonhole principle Pigeonhole principle (other)

12–14 3.0

33 representatives of four different races – humans, elves, gnomes, and goblins – sit around a round table.

It is known that humans do not sit next to goblins, and that elves do not sit next to gnomes. Prove that some two representatives of the same peoples must be sitting next to one another.

Problem #PRU-32784

Problems Methods Pigeonhole principle Pigeonhole principle (other)

12–13 2.0

What is the maximum number of rooks – also known as castles – you could place on an 8 by 8 chess board such that no two could take one another? Rooks can attack any number of squares horizontally and vertically, but not diagonally.