s10.4
10.4. Прямоугольник m х n можно разрезать на прямоугольники 1 x 1000. Докажите, что n или m делится на 1000.
Решение (способ 1)
Раскрасим в 2 цвета очень крупные клетки это будет 500 на 500. я утверждаю что если и м и н не кратные 1000 то клеток будет не поровну. почему?
Я знаю что m х n делится на 1000. А при этом сами m и n не делится на тысячу. Значит, рассмотрим остаток. Эр эн это остаток n по модулю 1000 и м это остаток m по модулю 1000. Тогда. Вот это 1000 это 1000 это рн это рм . смотрите вот здесь всё это кратно 1000. Поэтому в этой полосе будет поровну чёрных и белых клеток. Потому что 1000 то половина черная половина бело, но у нас столбики разбиваются, можно сказать. И в этой полосе тоже поровну чёрных и белых клеток. Значит, осталось разобраться вот с этим кусочком. Теперь вот этот кусок он как то кладётся вот на эту картинку крупную. И давайте посмотрим, где этот уголок может быть. Если она внутри этого квадрата, то просто все этого квадрата чёрное. Если rim меньше пятисот? Если вот этот уголок квадратная находится вот в этом прямоугольнике в этом квадратике, то смотрите. Здесь черных точно больше, чем белых. Потому что чёрное это вот эта сторона на 500. А белое это вот это на сторона меньше чем 500. Аналогично, если вот здесь находится уголок. Осталось убедиться со случаем, когда находится в этом квадрате. Давайте подробнее разберем. Вот мой квадрат. Вот это все черно. И вот это все черное. Вот эти 2 бело давайте просто руками посчитаем, значит вот это 500. Это какое то, а это бы это 500. Знаете, сколько чёрных? 500 квадратных плюс, а умножить на б. Сколько белых? Я утверждаю, что это больше чем 500, а плюс 500 б да. Перенесемся в левую часть, разложим на множители, что получится? Смотрите, вот это с этим 500 в квадрате минус 500, а плюс а б минус 500 д. Я утверждаю что это больше нуля. Вот здесь это 500. 500 минус. Плюс б. А минус 500. И разложим на множители. Нужно вот здесь минус вот здесь сделать 500 на 500 минус а минус. Бена 500 минус это то же самое, что 500 минус б eu 500 минус, а? Утверждают, что это больше нуля, то есть это больше нуля. Вот такое решение в крупную клетку.
Другое решение. Там всё понятнее с растущими полосками. Рассмотрим для его край. К. Количество полос акк, которые растут, пусть это m и m делится, но ты не 10000 тогда из 1 ряда 1 столбца растёт колок количество полос акк, сравнимая с м по модулю 1000. Тогда во 2 столбце уже есть эти полоски значит количество клеток, которые не заняты этими полосками не кратно. 1000. Какие то из них заняты вертикальными, значит, из 2 столбца растет кратная 1000, количество колосок из 3, кратная 1000 и так далее. И только в 1001 столбце. Вот будет уже не кратная 1000, а именно сравнимая с n по модулю 1000 всё то же самое как с 4 всё в один в один. Узнать, что у нас идут столбик, из которого сравнима с n по модулю 1000 количество полос как растёт 999. Столпов, которое кратно 1000 количество полос окрестят я 5 не кратно. Посмотрим, что в конце из последних 900 999 столбцов не растёт некуда, то значит предыдущий передними минус 999 его номер сравним с единицей по модулю 1000.