Выбрано 3 задачи 
Убрать все задачи
Команда из n школьников участвует в игре: на каждого из них надевают шапку одного из k заранее известных цветов, а затем по свистку все школьники одновременно выбирают себе по одному шарфу. Команда получает столько очков, у скольких её участников цвет шапки совпал с цветом шарфа (шарфов и шапок любого цвета имеется достаточное количество; во время игры каждый участник не видит своей шапки, зато видит шапки всех остальных, но не имеет права выдавать до свистка никакую информацию). Какое наибольшее число очков команда, заранее наметив план действий каждого её члена, может гарантированно получить:
а) при n = k = 2;
б) при произвольных фиксированных n и k?
В ящиках лежат камни. За один ход выбирается число k, затем камни в ящиках делятся на группы по k штук и остаток менее, чем из k штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за пять ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них
а) не более 460 камней;
б) не более 461 камня?
Докажите, что в любом множестве, состоящем из 117 попарно различных трёхзначных чисел, можно выбрать четыре попарно непересекающихся подмножества, суммы чисел в которых равны.
|
|
 |
Условие
Докажите, что в любом множестве, состоящем из 117 попарно различных трёхзначных чисел, можно выбрать четыре попарно непересекающихся подмножества, суммы чисел в которых равны.
Решение
Покажем, что среди произвольных 106 трехзначных чисел существуют даже четыре непересекающиеся пары с равными суммами.
Из 106 чисел можно образовать 106·105 : 2 = 5460 пар, сумма чисел в каждой паре лежит между 200 и 2000. Если пар с каждой суммой не более трёх, то всего пар не более 1800·3 = 5400, что не так.
Следовательно, у каких-то четырёх пар суммы совпадают. Пары, для которых совпадают суммы, не могут пересекаться: если x + y = x + z, то y = z, и пары совпадают.
Замечания
Выбирая не только пары, но также тройки и четвёрки, можно показать, что четыре непересекающиеся подмножества с равными суммами можно выбрать среди любых 97 трёхзначных чисел.
