В котокафе установлен квадратный стеллаж с лежанками размером 5 * 5 ячеек. Там живут пушистые и лысые (сфинксы) котики. 1. В каждой лежанке не более одного котика. 2. В каждом горизонтальном и вертикальном ряду находятся котики только одного вида (иначе они шипят друг на друга). 3. Заселение называется полным, если нельзя добавить ни одного котика без нарушения правил. а) Может ли при полном заселении мирно спать суммарно ровно 13 котиков? б) Может ли при полном заселении мирно спать суммарно ровно 15 котиков? в) Известно, что пушистых и лысых котиков оказалось поровну. Какое наибольшее количество котиков может быть на стеллаже?
Лемма: при полном заселении нет пустых рядов или столбцов, иначе на их пересечении можно было бы посадить котика. Каждый ряд и каждый столбец должен быть закреплён за определённым видом. Пусть пушистым котикам отдано x строк и y столбцов, тогда они занимают ровно xy ячеек. Лысым котикам досталось 5 - x строк и 5 - y столбцов, они занимают (5 - x)(5 - y) ячеек. Суммарное количество котиков S : S = xy + (5 - x)(5 - y). а) Пусть x = 2 , y = 2 . Тогда: S = 2 * 2 + (5 - 2)(5 - 2) = 4 + 9 = 13. Да, может. б) Рассмотрим уравнение: S = xy + 25 - 5x - 5y + xy = 2xy - 5x - 5y + 25 = 15. 2xy - 5x - 5y + 10 = 0 * 2; 4xy - 10x - 10y + 20 = 0. Отсюда: (2x - 5)(2y - 5) = 5. Целые делители числа 5 — это +- 1; +- 5 . Так как для наличия котиков обоих видов x, y in 1; 2; 3; 4 , то значение выражения 2x - 5 может принимать значения из множества -3; -1; 1; 3 . Получить произведение 5 с такими множителями невозможно. Следовательно, ровно 15 котиков быть не может. в) По условию котиков поровну: xy = (5 - x)(5 - y) => xy = 25 - 5x - 5y + xy => 5x + 5y = 25 => y = 5 - x. Общее количество котиков: S = 2xy = 2x(5 - x) = 10x - 2x^2. Графиком функции является парабола, ветви которой направлены вниз. Максимум достигается в вершине: x_0 = (-10)/(2 * (-2)) = 2,5. Так как x — целое число, подставим ближайшие значения x = 2 или x = 3 : S_() = 10 * 2 - 2 * 2^2 = 20 - 8 = 12. Ответ: а) да б) нет в) 12
а) Да; б) Нет; в) 12