Отзывы пользователей

гдз

Олимпиадная задача по математике из коллекции задач Турнира Ломоносова на темы: Шахматные доски и шахматные фигуры, Арифметика остатков (прочее), Принцип Дирихле (прочее).

Условие

Какое максимальное число ладей можно расставить в кубе 8 × 8 × 8, чтобы они не били друг друга?


Решение

Очевидно, что в каждом столбике из 8 кубиков-клеток может стоять только одна ладья, поэтому больше 64 ладей поставить нельзя.

Покажем, как поставить 64 ладьи, чтобы они не били друг друга. Введем систему координат с осями, направленными вдоль ребер куба так, чтобы каждая клетка имела координатами тройку (x,y,z) чисел от 0 до 7 и поставим ладьи в клетки, сумма координат которых делится на 8. Эта расстановка является искомой.

Докажем сначала, что эти ладьи не бьют друг друга. Предположим противное — какие-то две ладьи бьют друг друга. Значит, две их координаты (скажем, x и y) совпадают, а третья — различна (обозначим ее z1 и z2 соответственно). По построению суммы x + y + z1 и x + y + z2 делятся на 8. Значит, на 8 делится и их разность z1 – z2, что невозможно, так как z1 и z2 — различные неотрицательные числа, меньшие 8.

Докажем теперь, что в каждом вертикальном столбике находится по ладье, то есть что мы поставили 64 ладьи. Каждый такой столбик определяется своей парой координат x и y. Координата z для ладьи в этом столбике однозначно задается условием x + y + z ≡ 0(  8). А именно, если x + y делится на 8, то z = 0, в противном случае z равно 8 минус остаток от деления на 8 суммы x + y.

 
Поделиться: