В какое наибольшее число цветов можно раскрасить клетки квадрата $$3\times 3$$ так, чтобы для любой пары цветов нашлись две соседние по стороне клетки, окрашенные в эти цвета?

У меня чисто семантическая загвоздка. Что именно следует понимать под парой цветов? Обязательно ли цвета в паре должны быть различными? Ведь от этого зависит ответ на задачу.

Если подразумеваются только пары различных цветов, то ответ, я полагаю, будет 5. Ведь при 6 и более цветах уже найдутся 15 пар различных цветов, а у нас только 12 «доминошек». Вот пример для пяти цветов: 425

513

342

Если же речь идёт о любых парах цветов, не обязательно различных, то ответ, я полагаю, будет 4. Ведь при 5 и более цветах уже найдутся 15 пар различных цветов, а у нас только 12 «доминошек». Вот пример для четырёх цветов:

212

412

433

Пожалуйста, помогите решить.

Заранее спасибо!

задан 31 Дек '16 0:02

@Сагемет Танюша: тут Вы уже всё решили, причём в двух вариантах. Если говорить о том, какая из трактовок более естественна, то я думаю, что первая. Под "парой" по умолчанию понимается неупорядоченная пара, то есть двухэлементное подмножество.

В принципе, можно было сформулировать условие задачи так, чтобы двусмысленности не возникало. Например, сказать "для любых двух различных цветов найдутся". Такого рода разночтения довольно часто возникают, и нередко получается так, что на месте одной задачи возникает несколько.

Интересно было бы рассмотреть и вариацию с соседями по стороне или вершине.

(31 Дек '16 0:22) falcao

@falcao , касаемо вариации с соседями по стороне или вершине. Если одноцветную пару считать парой, то ответ тоже 4. Ведь клеток каждого цвета как минимум две, а всего клеток - 9. И пример годится тот же самый, что и в вариации с соседними лишь по стороне.

(31 Дек '16 0:42) Машакит Хилу...

@Сагемет Танюша: видимо, интересного варианта при изменении условия всё-таки не получается. Одинаковых пар брать, конечно, не надо, но и при разных не получится примера с 6 цветами.

(31 Дек '16 1:16) falcao

@falcao , почему не получится?

(31 Дек '16 16:54) Машакит Хилу...

@Сагемет Танюша: вообще-то получится -- я даже нарисовал пример, но мне почему-то показалось, что он из общих соображений не подходит. А вот 7 цветов уже точно нельзя.

(31 Дек '16 17:53) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,392
×1,114
×370
×211
×94

задан
31 Дек '16 0:02

показан
733 раза

обновлен
31 Дек '16 17:53

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

по почте:

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

по RSS:

Ответы

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

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