Можно ли покрасить некоторые клетки доски 8×8 так, чтобы в любом квадрате 3×3 было ровно 5 закрашенных клеток, а в каждом прямоугольнике 2×4 (вертикальном или горизонтальном) – ровно 4 закрашенные клетки?

   Решение

Темы:    [ Десятичная система счисления ] [ Принцип Дирихле (прочее) ] [ Показательные функции и логарифмы (прочее) ] [ Рациональные и иррациональные числа ]

Сложность: 5+ Классы: 10,11

Прислать комментарий

Условие

Докажите, что числа вида 2ⁿ при различных целых положительных n могут начинаться на любую наперёд заданную комбинацию цифр.

Решение

Пусть A — данное натуральное число. Покажем, что натуральное число n можно выбрать так, что 10^mA < 2ⁿ < 10^m(A + 1), т.е. m + lg A < n lg 2 < m + lg(A + 1). Эквивалентное условие таково: существуют натуральные числа m и n, для которых lg A < n lg 2 - m < lg(A + 1). Число lg 2 иррационально. (Действительно, предположим, что lg 2 = p/q, где p и q — натуральные числа. Тогда 10^p/q = 2, т.е. 10^p = 2^q. Этого не может быть.) Поэтому остаётся доказать следующее утверждение: `` Пусть — иррациональное число. Тогда для любых чисел a < b можно выбрать целые числа m и n, для которых a < m - n < b.'' Пусть = b - a. Для каждого целого числа m можно выбрать целое число n так, что 0m - n1. Разделим отрезок [0, 1] на равные отрезки, длина каждого из которых меньше . Пусть количество этих отрезков равно k. Тогда среди чисел - n₁, 2 - n₂, ..., (k + 1) - n_{k + 1} есть два числа, принадлежащих одному и тому же отрезку. Вычтем из большего числа меньшее: p - n_p - (q - n_q) = t. Ясно, что 0t < . Более того, t 0, поскольку иначе = — рациональное число. Рассмотрим числа вида Nt, где N — целое число. Каждое из этих чисел имеет вид m - n. А из того, что 0 < t < , следует, что хотя бы одно из этих чисел расположено строго между a и b.

Источники и прецеденты использования