Дано натуральное число n > 10. Вокруг стола сидит n человек. На каждом из них надет колпак синего или красного цвета, причём каждый из сидящих видит только цвет колпаков у двух соседей по столу. Каждый из этих n людей пишет на бумажке два числа: номер своего места и количество синих колпаков, которое он видит. При каких n по всем этим бумажкам можно наверняка установить, на ком какой колпак надет?

задан 3 Янв '19 22:08

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

Занумеруем участников по кругу. Пусть a(i)=1, если на i-го участника надет синий колпак, и a(i)=0 в противном случае. Тогда можно сказать, что a(i) равно количеству синих колпаков, надетых на i-го участника. Нам известны числа b(i)=a(i-1)+a(i+1) при 1<=i<=n, где a(0)=a(n), a(n+1)=a(1). Вопрос состоит в том, можно ли однозначно решить данную систему линейных уравнений относительно неизвестных a(i).

Сразу заметим, что при n кратном 4 это невозможно, так как ситуация ККСС...ККСС неотличима от ССКК...ССКК. Покажем, что при прочих значениях n это возможно.

Пусть имеется нечётное количество чисел c(1), c(2), ... , c(2k+1), для которых нам известна сумма любых соседних (циклически). Тогда числа легко восстановить с учётом тождества 2c(1)=(c(1)+c(2))-(c(2)+c(3))+...-(c(2k)+c(2k+1))+(c(2k+1)+c(1)). Понятно, что отсчёт можно начать с любого из имеющихся чисел, что есть все значения c(i) восстанавливаются.

При нечётном n мы рассмотрим список чисел a(1), a(3), ... , a(n), a(2), a(4), ... , a(n-1), для которого нам известна сумма двух (циклических) соседей. По этим данным все числа восстанавливаются. Если n=2(2k+1) чётно, и при этом не делится на 4, то рассматриваем два списка: a(1), a(3), ... , a(4k+1) и a(2), a(4), ... , a(4k+2), в каждом из которых нечётное количество членов, и сумма (циклических) соседей нам известна. Это позволяет восстановить все a(i).

ссылка

отвечен 3 Янв '19 23:22

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

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

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

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

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

отмечен:

×310

задан
3 Янв '19 22:08

показан
275 раз

обновлен
3 Янв '19 23:22

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

по почте:

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

по RSS:

Ответы

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

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