Олимпиадная задача на НОК На клетчатой доске 10х20 несколько клеток покрашено в красный цвет. Костя разрезал доску по клеточкам на прямоугольники так, что в каждом оказалось 5 красных клеток. А Влад разрезал такую же доску на прямоугольники так, что в каждом оказалось 7 красных клеток. Докажите, что Дима не сможет разрезать такую же доску на прямоугольники так, что в каждом будет 6 красных клеток.

Предыдущий
вопрос Следующий
вопрос

Предположим, что Дима может разрезать такую же доску на прямоугольники так, что в каждом будет 6 красных клеток.

Пусть общее количество красных клеток на доске равно N. Так как в каждом прямоугольнике, на который разрезал Костя, содержится 5 красных клеток, то общее количество прямоугольников, на которые разрезала доску Костя, равно N/5.

Аналогично, общее количество прямоугольников, на которые разрезала доску Влад, равно N/7.

Теперь предположим, что Дима разрезал доску на прямоугольники так, что в каждом из них содержится 6 красных клеток. Обозначим количество таких прямоугольников за К. Тогда 6K = N, откуда K = N/6.

Так как К равно целому числу (все прямоугольники должны быть целыми), то разность между N/5 и N/6 должна быть целым числом. Но N/5 - N/6 = 6N/30 - 5N/30 = N/30, что является дробным числом, так как N делится на 2 (10) и не делится на 3. Получили противоречие, следовательно, Дима не сможет разрезать такую же доску на прямоугольники с 6 красными клетками в каждом.