Выбрана 1 задача 
Убрать все задачи
Покажите, как разрезать квадрат размером 5×5 клеток на "уголки" шириной в одну клетку так, чтобы все "уголки" состояли из разного количества клеток. (Длины "сторон" уголка могут быть как одинаковыми, так и различными.)
Решение
|
|
 |
Условие
В НИИЧАВО работают несколько научных сотрудников. В течение 8-часового рабочего дня сотрудники ходили в буфет, возможно по нескольку раз. Известно, что для каждых двух сотрудников суммарное время, в течение которого в буфете находился ровно один из них, оказалось не менее x часов (x > 4). Какое наибольшее количество научных сотрудников могло работать в этот день в НИИЧАВО (в зависимости от x)?
Решение
Пусть в НИИ в тот день работали n человек. По условию, для каждой пары сотрудников время, когда в буфете присутствовал ровно
один из них, не меньше x. Суммируя все эти промежутки времени по всем парам, получим число S ≥ ½ n(n + 1)x.
Посчитаем это число другим способом. Отметим моменты, когда в буфет кто-то входил или из него кто-то выходил. Рабочий день разбился на m промежутков с длинами t1, ..., tm. Пусть на промежутке с номером i в буфете находилось ki человек. Тогда этот промежуток будет посчитан ровно для тех пар сотрудников, в которых ровно один присутствует в буфете; таких пар ki(n – ki). Поэтому этот промежуток внесёт в S вклад tiki(n – ki). Выражение k(n – k) достигает максимума при k = [n/2], поэтому указанный вклад не больше ti [n/2](n – [n/2]). Поскольку t1 + ... + tm = 8, то, суммируя, получаем, что 8 [n/2](n – [n/2]) ≥ S ≥ ½ n(n + 1)x.
Рассмотрим два случая.
1) n = 2l. Тогда 8l² ≥ l(2l – 1)x, то есть (2x – 8)l ≤ x,
2) n = 2l + 1. Тогда 8l(l + 1) ≥ l(2l + 1)x, то есть (2x – 8)l ≤ 8 – x,
То есть в любом случае
Покажем, что эта оценка достигается. Положим Рассмотрим все способы отметить l сотрудников из n = 2l (число K таких способов равно
). Разобьём 8-часовой интервал на K отрезков длины 8/K. Каждому отрезку сопоставим группу из l человек; пусть в течение этого отрезка времени ровно эти l человек и находились в буфете. Из симметрии ясно, что для каждых двух сотрудников время, в течение которого ровно один из них был в буфете, одно и то же – пусть оно равно y. Тогда в подсчете, проделанном выше, все неравенства обратятся в равенства, и мы получим 8l² = (2l – 1)y. Отсюда
(последнее неравенство равносильно
), что и требовалось.
Ответ
сотрудников.
Замечания
При x ≤ 4 число сотрудников может быть каким угодно.
