Competition problem — Combinatorics

Library / /29 of 57

Combinatorics Difficulty 6.8 National olympiad Prove it Russia

In a bazaar, there is a carpet-changer. If he gets from a client an $a \times b$ carpet, he can give instead either a $\frac{1}{a} \times \frac{1}{b}$ carpet, or two carpets of sizes $c \times b$ and $\frac{a}{c} \times b$ (at each such change, a number $c$ is chosen by the client). A traveler tells that initially he had one carpet whose side lengths were greater than $1$ , and after a series of changes each of his carpets had a side longer than $1$ as well as a side shorter than $1$ . Could this be a correct story? (G. Zhukov)

У месялы па базаре есть много ковров. Он согласен взамен ковра размера $a \times b$ дать либо ковёр размера $\frac{1}{a} \times \frac{1}{b}$ , либо два ковра размеров $c \times b$ и $\frac{a}{c} \times b$ (при каждом таком обмене число $c$ клиент может выбрать сам). Путешественник рассказал, что изначально у него был один ковёр, стороны которого превосходили $1$ , а после нескольких таких обменов у него оказался набор ковров, у каждого из которых одна сторона длиннее $1$ , а другая — короче $1$ . Не обманывает ли он? (По просьбе клиента меяла готов ковёр размера $a \times b$ считать ковром размера $b \times a$ .) (Г. Жуков)

Solution

No.

We say that a carpet is large (resp., small) if both its side lengths are larger (resp., smaller) than $1$ . Show that the total number of large and small carpets does not decrease.

Назовём ковёр, все стороны которого больше $1$ , большим, а ковёр, все стороны которого меньше $1$ , — маленьким. Таким образом, изначально у путешественника был один большой ковёр. Докажем, что общее число больших и маленьких ковров у путешественника не уменьшается; отсюда следует, что описанная ситуация невозможна. Для этого достаточно рассмотреть только случай, когда путешественник отдаёт меняле большой или маленький ковёр.

При обменах первого вида большой ковёр меняют на маленький, а маленький — на большой. Поэтому общее количество больших и маленьких ковров не уменьшается.

Рассмотрим обмены второго вида. При обмене большого ковра $a \times b$ путешественник получит ковры $a_1 \times b$ и $a_2 \times b$ . Если $0 < a_1, a_2 \le 1$ , то $a = a_1 a_2 \le 1$ , что неверно. Учитывая равенство $b > 1$ , получим, что хотя бы один из новых ковров будет большим. Аналогично, при обмене маленького ковра хотя бы один из новых ковров будет маленьким. Значит, при таком обмене общее количество больших и маленьких ковров также не уменьшается.

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.