2
1

Каждый из $%8$% ящиков содержит $%6$% шаров. Каждый шар окрашивается в один из $%n$% цветов так, что ни в одном из ящиков нет шаров одного цвета и никакие два цвета не встречаются вместе более, чем в одном ящике. Найти наименьшее $%n$%, для которого это возможно.

задан 17 Янв '14 9:46

изменен 17 Янв '14 14:47

10|600 символов нужно символов осталось
3

У меня получился ответ 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

10|600 символов нужно символов осталось
1

Вариант с 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

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×796
×515
×393
×56

задан
17 Янв '14 9:46

показан
1571 раз

обновлен
17 Янв '14 20:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru