Олимпиадная задача про "супершахматы" с 20 уникальными фигурами на доске 100×100
Игра в "супершахматы" ведётся на доске размером 100×100, и в ней участвует 20 различных фигур, каждая из которых ходит по своим правилам. Известно, что любая фигура с любого места бьет не более 20 полей (но больше о правилах ничего не сказано, например, если фигуру А передвинуть, то о том, как изменится множество битых полей мы ничего не знаем). Докажите, что можно расставить на доске все 20 фигур так, чтобы ни одна из них не била другую.
Разобрать решение
Расстановок, когда i-я фигура бьёт j-ю – не более чем 10000·20·9998·9997·...·9981. Умножив на число пар 20·19, получим грубую оценку сверху количества "плохих" расстановок: 20·19·10000·20·9998·9997·...·9981. Но это число меньше чем количество 10000·9999·...·9981 всех расстановок
(20·19·20 < 8000 < 9999).
Обсуждение
0Комментариев пока нет.