Question

Клетчатый квадрат 17 × 17 разрезали на прямоугольники по линиям сетки. Докажите, что найдется прямоугольник, у которого обе стороны нечетные.

Answer 1

Пусть прямоугольника, у которого обе стороны нечетны - не существует, тогда у нас могут существовать такие прямоугольники, где a, b стороны

1) a - четное, b - четное

2) a - нечетное, b - чётное

Заметим такой факт:

Произведение четного числа на чётное, и чётного числа на нечетное - чётное число, таким образом, площади наших прямоугольников - чётны, так как они равны a * b.

Площадь нашего квадрата 17 * 17 - нечетное число. Нечетное число не делится на чётное, противоречие. Значит точно существует прямоугольник с двумя нечетными сторонами, поскольку только у него площадь - нечетна

Answer 2

Для решения данной задачи воспользуемся методом математической индукции.

Пусть у нас имеется клетчатый квадрат размером 17×17. Разрежем его на прямоугольники по линиям сетки. Так как начальный квадрат имеет нечётные стороны, то высказывание верно для него.

Предположим, что для квадратов размером (2n-1)×(2n-1), где n — натуральное число, высказывание верно. Докажем его для квадрата размером (2n+1)×(2n+1).

Разделим квадрат на 4 прямоугольника размером n×n, два прямоугольника размером n×1 и два прямоугольника размером 1×n. По предположению индукции, в каждом из прямоугольников n×n найдется прямоугольник с нечётными сторонами.

Рассмотрим прямоугольники n×1. Если в каждом из них найдется прямоугольник с нечётными сторонами, то мы уже доказали высказывание для квадрата размером (2n+1)×(2n+1).

Если в одном из прямоугольников n×1 не найдется прямоугольника с нечётными сторонами, то второй прямоугольник n×1 должен содержать прямоугольник с нечётными сторонами. Так как сумма двух нечётных чисел всегда чётна, то сумма сторон прямоугольника, в который входят прямоугольники n×1, также будет чётной. Тогда второй прямоугольник n×1 будет иметь нечётные стороны.

Таким образом, в любом случае найдется прямоугольник с нечётными сторонами в квадрате размером (2n+1)×(2n+1). Высказывание доказано.