Условие
Часть клеток бесконечной клетчатой бумаги покрашена в красный цвет, остальные
— в белый (не обязательно в шахматном порядке). По красным клеткам прыгает
кузнечик, по белым — блоха, причём каждый прыжок может быть сделан на любое расстояние по вертикали или горизонтали. Докажите, что кузнечик и блоха могут оказаться рядом, сделав в общей сложности (в сумме) не более трёх прыжков.
Решение
Докажем сначала, что если кузнечик и блоха сидят на одной линии (вертикали или
горизонтали), то они могут оказаться рядом, сделав в общей сложности не более
двух прыжков. Действительно, на этой линии есть клетки обоих цветов, а
значит, есть соседние клетки, одна из которых покрашена в красный цвет, а
другая в белый. Следовательно, кузнечик может прыгнуть в одну из них, а
блоха — в другую. Итак, если кузнечик и блоха сидят на одной линии, то они
могут оказаться рядом, сделав в сумме не более двух прыжков.
Докажем теперь, что кузнечик и блоха могут за один прыжок оказаться на одной
линии. Для этого проведём вертикаль, на которой сидит кузнечик, и горизонталь,
на которой сидит блоха. Так как клетка их пересечения покрашена в один из
цветов, то либо кузнечик, либо блоха могут прыгнуть в эту клетку. После этого
прыжка они окажутся на одной линии.
Итак, где бы ни сидели кузнечик и блоха, они могут за один прыжок оказаться на
одной линии, а потом не более чем за два прыжка оказаться рядом, т. е. они
могут оказаться рядом не более чем за три прыжка.
Источники и прецеденты использования
