Задача из журнала «Квант» (1991 год, 3 выпуск)

Условие

Можно ли покрыть всю плоскость квадратами с длинами сторон $1, 2, 4, 8, 16, …$ (без наложения), используя каждый квадрат не более а) десяти раз; б) одного раза?

Доказательство

1. Можно. Пример покрытия (где квадрат со стороной $1$ используется $4$ раза, а остальные — по $3$ раза) приведен на рисунке $1$.
   

   

2. Нельзя. Предположим, что существует покрытие, в котором все квадраты различны. Поскольку сумма всех чисел не превосходящих $2^{n-1}$, меньше $2^n$ $(1+2+2^2+ … +2^{n-1} = 2^n-1)$, то к каждой стороне любого из квадратов нашего покрытия должна примыкать сторона большего квадрата. Отсюда следует, что каждая вершина квадрата должна лежать на стороне большего квадрата (если вершина $B$ квадрата $ABCD$ лежит на стороне большего квадрата, примыкающего к стороне $AB$ (рис. $2$), то вершина $C$ будет лежать на стороне большего квадрата, примыкающего к $BC$, и т.д.).

Рассмотрим теперь наименьший из всех квадратов покрытия. Четыре квадрата будут примыкать к нему так, как показано на рисунке $3$.

Рассмотрим больший из этих квадратов — пусть он примыкает к стороне $AB$ наименьшего (на рисунке — это черный квадрат). Тогда вершина $A$ этого квадрата не лежит на стороне большего, чем он, квадрата. Получили противоречие.

Д.Фомин