Версия для печати
Убрать все задачи
(Сообщил А. Л.Брудно)
Прямоугольное поле
m×
n разбито на
mn
квадратных клеток. Некоторые клетки покрашены в чёрный
цвет. Известно, что все чёрные клетки могут быть разбиты на
несколько непересекающихся и не имеющих общих вершин чёрных
прямоугольников. Считая, что цвета клеток даны в виде
массива типа
array[1..m] of array [ 1..n] of boolean;
подсчитать число чёрных прямоугольников, о которых шла
речь. Число действий должно быть порядка
mn.

Решение
Имеется 1959 положительных чисел
a1,
a2...,
a1959, сумма которых равна 1. Рассматриваются всевозможные комбинации из 1000 чисел, причём комбинации считаются совпадающими, если они отличаются только порядком чисел. Для каждой комбинации рассматривается произведение входящих в неё чисел. Доказать, что сумма всех этих произведений меньше 1.

Решение