|
Каждый из $%8$% ящиков содержит $%6$% шаров. Каждый шар окрашивается в один из $%n$% цветов так, что ни в одном из ящиков нет шаров одного цвета и никакие два цвета не встречаются вместе более, чем в одном ящике. Найти наименьшее $%n$%, для которого это возможно. задан 17 Янв '14 9:46 
student |
|
У меня получился ответ 23. Пример будет приведён по ходу рассуждения. Если каждый цвет используется не более двух раз, то цветов как минимум 24. Рассмотрим случай, когда цвет 1 встречается ровно трижды. Тогда в каждом из трёх ящиков с ним идут 5 своих цветов. Итого стало 16 цветов. В пяти оставшися ящиках цвета 1 уже нет, а из 15 цветов, использованных с 1, в пределах одного ящика могут встречаться максимум три (ввиду принципа Дирихле). Значит, в каждом из пяти ящиков есть какие-то три шара других цветов, и можно рассмотреть такую же задачу с другими параметрами: когда ящиков 5, и в каждом лежит по 3 шара. Утверждается, что здесь минимальное число цветов равно 7. Пример строится так: a b c a d e a f g b d f c e g Шести цветов здесь мало по той причине, что какой-то цвет повторится как минимум трижды. Если он встретится 3 раза, то нужны будут ещё 6 цветов кроме него, а если более трёх, то цветов потребуется ещё больше. Из этого примера строится конструкция для исходной задачи с 23 цветами: 1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 2 7 12 a b c 3 8 13 a d e 4 9 14 a f g 5 10 15 b d f 6 11 16 c e g Осталось проверить, что меньшим числом цветов не обойтись. Для случая, когда какой-то цвет встречается ровно трижды, всё рассмотрено. Если цвет 1 встречается пять и более раз, то дополнительных цветов будет уже 25. Пусть цвет 1 встретился четыре раза. Тогда с ним вместе присутствует 20 дополнительных цветов. В каждом из оставшихся четырёх ящиков будет не более 4 шаров уже использованных цветов, то есть как минимум по два цвета будет новых. Тогда возникает задача с 4 ящиками и 2 шарами. При этом не обойтись даже тремя цветами, так как из них можно образовать только три пары. При таком плане всего потребуется не менее 25 цветов, то есть 23 будет минимальным значением. отвечен 17 Янв '14 20:17 
falcao |
|
Вариант с 24 использованными цветами: 1, 2, 3, 4, 5, 6 // 1, 7, 8, 9,10,11 // 2, 7,12,13,14,15 // 3, 8,12,16,17,18 // 4, 9,13,16,19,20 // 5,10,14,17,19,21 // 6,11,15,18,20,21 // 6,10,13,22,23,24 // Думаю, что можно для 7 ящиков доказать, что использование 21 цвета есть оптимальным. А в ответе с 24 цветами для 8 ящиков не уверен. отвечен 17 Янв '14 19:54 
aid78 |