Library / Ukrainian Mathematical Olympiad /21 of 49

Ukrainian Mathematical Olympiad

Combinatorics Difficulty 5.7 AIME, harder Prove it Ukraine

Vandal Peter cut a rectangular head teacher's portrait along a straight line. After this he cut one of the pieces along a straight line, then he cut one of the new pieces etc. After he had made 100 cuts, the head teacher arrived and forced Peter to pay 2 kopecks for each triangular piece and 1 kopeck for each quadrangular piece. Prove that Peter paid more than 1 hryvnya (1 hryvnya = 100 kopecks).

Solution

Очевидно, що отримані під час розрізання шматки є опуклими многокутнимами. Одним розрізанням загальна кількість вершин збільшується щонайбільше на 4. Тому після 100 розрізань многокутники матимуть не більше за 404 вершини. З іншого боку, після 100 розрізань утворився 101 многокутник. Нехай серед них $n$ трикутників та $m$ чотирикутників. Тоді утворені многокутники мають не менше за $3n + 4m + 5(101 - m - n) = 505 - 2n - m$ вершин. Отже, $505 - 2n - m \le 404$ , звідки $2n + m \ge 101 > 100$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.