Шляпник (russhatter) wrote,
Шляпник
russhatter

Математика болтушек, настоящий финал

Задача: за какое минимальное число попарных разгоровов N болтушек могут расказать всем все свои тайны?
Обозначим это число: M(N)
Ответ: при N>3: M(N) = 2N - 4, M(3) = 3, M(2) = 1, M(1) = 0.

Реализация Строим всех болтушек. кроме трёх, в ряд. Сначала пусть проговорят слева направо. Возьмём последнюю болтушку и оставшиеся три, пусть теперь переговорят 1-2, 3-4, 1-3, 2-4. После этого эти 4 болтушки знают все тайны, осталось раздать их оставшимся, по разговору на каждую. Итого разговоров: (N-4) + 4 + (N-4).
Замечание Бывают другие реализации, при 8 по кубу, при 6 как-то хитро, но вот по гиперкубу уже нельзя: число разговоров не-минимальное.

Трёп не по делу.

Я вообще-то не знаю, зачем вам всё это читать. Скорее, это даже не нужно.

Нет, я понимаю, почему я это написал: я всё-таки решил эту страшную для меня задачу, наконец-то решил её убойно правильно. Вот запишу, выгружу её из головы, и займусь другими... Но вам-то, вам зачем это всё?

Вообще: вокруг безумие с кодивом, десятый месяц пошёл, как народ старается вырабатывать у себя привычки типа умения спать на потолке, но почему-то никак оно не привыкается. А тут - Шляпник! В своём репертуаре! Что-то очень заумное по какому-то заумному поводу, ... а зачем оно всё? Вас действительно интересует, чему равно это минимальное число разговоров?

Вот и вправду: незачем Вам больше это читать...

* * *

... Всё? Все ушли?... А для остальных, которых вполне может и не быть, продолжаю.

Я решал эту задачу - кусочек вечности. Кто из моих читателей с хорошей памятью, тот может вспомнить, что я уже публиковал её решение немногим меньше года назад, да с большим пафосом, с чередой ссылок, тянущихся аж в 2004 год... И вот: попытавшись пару месяцев назад воспроизвести то доказательство, я обнаружил, что оно дырявое. И что дырку закрыть я не могу.

Довольно долго я был почти в панике: ладно бы там единичку туда - единичку сюда, у меня получалось ассимптотика оценки снизу только в (3/2 N) - а надо бы 2N. Но я посидел, помучился, и каким-то чудом всё-таки дoдумал другое решение. И вот - этот пост.

Задачка учебная, из олимпиадной математики - я люблю их, всю жизнь люблю такие решать. Мучаюсь, трудно это, но люблю. Вообще-то задачки на то и олимпиадные, что решать их вроде бы нужно на время - а вот этого я никогда не ценил и не любил. Я люблю решать такие задачи долго, обстоятельно.... Впрочем, в этот раз я перебрал, невообразимо перебрал. Но всё-таки решил.

Почему я так вцепился именно в эту задачу, а задача вцепилась в меня? Мне лично это очень даже понятно: потому, что у неё уж очень простая формулировка. Почти всегда задачки с такими условиями имеют тривиальное решение - а тут... В этом что-то есть, тут может скрываться какая-то нездешняя красота, а потому...

За что я люблю Математику: это за то, что Ей много что совершенно всё равно. Всё равно, сколько решается задача, сколько тебе лет, что ты умеешь, чего у тебя нет - это всё не важно. Важно только одно: решил ты задачу или нет. Да и это, в конце концов не столь уж ценно: ответ на любую (корректно поставленную) задачу хоть какой, да обязательно существует, даже если его никто не придумал до сих пор, даже если не придумает потом. Говорить про вот такую совершенно индифферентную Математику совершенно бессмысленно - но когда ты решаешь задачу, особенно в тот момент, когда ты её решил - вот тут ты ощущаешь, что ты ко всему этому абстрактному Величию - ... прикасаешься. В конце концов, выходит, что для меня всё это напряжение мозгов - это... просто погоня за эмоциями. Ergo существую, короче....

А задачка-то оказалась действительно сложная. Так работает математика: чтобы что-то решить, надо воспользоваться правильными инструментами. И заготовлено этих инструментов, которые многое что решают, много. Но на то эти задачки и "олимпиадные", что довольно часто они не решаются стандартными инструментами - и надо придумывать ... подходящие. Я почему сейчас уверен, что действительно, в отличие от прошлого раза, решил? Потому, что горд тем, что для этой задачи правильный инструмент подобрал. Долго-долго тужился - и увидел. Вообще, эта машинерия с инструментами - для меня самое интересное. Хоть я и не могу, да и никто не может, что-то важное и универсальное тут сказать, но чую, что оно есть. Видите: опять эмоции... Как там говорила та дама Штирлицу в баре: "когда о нас, математиках, говорят, как о чёрствых сухарях - это ЛОЖЬ!". Ну да, ну да!..

...А если кого смущает олимпиадный характер задачи, её видимая несерьёзность, так вот вам переформулировка её же, но в более основательных терминах.

Пусть у нас есть N-мерное пространство, и линейные операторы, работающие только по двум координатам, и эти координаты как-то "перемешивающие". Например, пусть это будут повороты в двух координатах на какие-то углы, скажем, меняющиеся от параметра. Если сделать суперпозицию небольшого числа таких операторов и посмотреть на матрицу получившегося оператора, в ней будет довольно много нулей. Сколько нужно сопрячь "элементарных" операторов, чтобы все коэфициенты в общей матрице перестали быть нулевыми? Ответ - такой же, как в задаче о болшушкак. Утверждение не очень-то осмысленное, но в принципе может оказаться полезным в каких-то доказательствах вполне "серьёзных" результатов.

...Всё! Лирику я заканчиваю, осталось выложить доказательство. Все ушли - понятно? Я тут быстренько всё доделаю, и тоже уйду...

Трёп по делу: доказательство

Дополнительное построение
Рассмотрим последовательность разговоров N болтушек, в результате которой все болтушки узнали все тайны.

Определение Пусть выделено некоторое множество тайн.
1. Назовём разговор двух болтушек "активным" (в контексте выделенного множества тайн), если в этом разговоре распространяется хотя бы одна из выделенных тайн.
2. Назовём разговод двух болтушек "неаккуратным", если в нём распространяется хотя бы одна выделенная тайна и хотя бы одна невыделенная, но при этом не все выделенные тайны сразу.
3. Назовём выделенное множество тайн "аккуратным", если в его контeксте в последовательности нет "неаккуратных" разговоров

Утверждение.Выделение одной тайны всегда является "аккуратным", а число соответствующих ему активных разговоров - не меньше (N - 1).

Лемма. Любое непустое множество выделенных тайн можно сократить до (непустого) "аккуратного" множества, таким способом, при котором число разговоров, исключаемых из "активных", не меньше числа исключаемых тайн.

Доказательство леммы. Пусть при данном выделении тайн имееются "неаккуратные разговоры" - выберем из них самый ранний. До него никакого перемешивания выделенных и невыделенных тайн нет, а в этом разговоре как раз оно происходит: встречается болтушка, знающая какое-то число выделенных тайн, пусть будет m, и болтушка, знающая только невыделенные тайны. Исключим из выделения все m тайн, участвующих в разговоре (заметим: что-то в выделении всё-таки всегда остаётся...). Из активных исключатся все произошедшие до этого момента включительно разговоры с участием любой из m болтушек, и этих разговоров не меньше m: этот вот "неакуратный", а перед тем ещё и все те (m - 1) разговора, которые привёли к тому, что болтушка знает все m тайн.

Итак, инструмент, на который я выше намекал, сформулирован и подготовлен. Это - число активных разговоров в зависимости от выделения тайн. При одной тайне это уже порядка N разговоров, и Лемма утверждает, что при расширении/сужении множества тайн работает принцип "одна тайна - один разговор". А как раз без подобного инструмента, в изначальной постановке мы имеем раскладку "одна тайна - два разговора", и это дико неудобно...

В-общем, задача почти решена, и дальше - ... в очередной раз можно не читать, а, например, додумать доказательство самому... Там всё-таки есть, чего додумывать, хотя это дело техники.

Но вот увидеть именно это построение, добраться о него, поймать... - вот это заняло у меня в сумме невероятное время. Впрочем, получилось-то хорошо...

Доказательство основного результата

Будем считать, что при N <= 4 доказательство очевидно. Дальше работаем по индукции.

Берём N > 4 и рассмотрим какой-то сценарий разгоровов N болтушек, в результате которой все всё узнали. Число разговоров в ней обозначим через MM. Наша конечная цель - доказать, что

min(ММ)<по сценариям> = M(N) >= 2N - 4

Шаг 1: определяем начальное выделение тайн. Берём первый разговор, и исключаем из полного множества тайн две тайны, принимающие в нём участие. Итого: исключили две тайны - из активных исключился один разговор.

Шаг 2: применяем Лемму: сводим выделение к аккуратному выделению из k тайн. Исключили (N - k -2) тайны, и не меньше такого же числа активных разговоров.

Шаг 3 разбираемся с "аккуратным выделением" из k тайн.
Имеем два вида разговоров:
- обмен выделенными тайнами между своими, исключительно между выделенными болтушками, пока всем не станут известны все выделеные тайны, и только они - таких разговоров по определению не меньше M(k) (пока индукцию не применяли, просто воспользовались обозначением)
- разговоры, в которых полный пакет выделенных тайн распространяется по всем оставшимся (N - k) болтушкам. Таких разговоров ровно (N - k).

Суммируем разговоры с трёх шагов, начиная с шага 1:

MM >= 1 + (N - k - 2) + M(k) + (N - k) = 2N + M(k) - 2k - 1

* при k = 1: M(k) = 0, MM >= 2N - 3, оценка выше заявленной минимальной

* при k = 2, 3 получается ровно то, что нам нужно:

М(2) = 1, MM >= 2N + 1 - 4 - 1 = 2N - 4

М(3) = 3, ММ >= 2N + 3 - 6 - 1 = 2N - 4

* ... а вот дальше - хуже: уже при k = 4, не говоря о следующих, прямая оценка даёт 2N - 5, и вроде бы доказательство ломается. Но нас не надуешь! Мы с дырочкой!

Проговариваем, что у нас есть на настоящий момент. Мы разбираемся со сценариями разговоров N болтушек, и провели для каждого сценария выделение некоего "большого аккуратного" подмножества из k тайн, k < N. Если это "большое аккуратное" подмножество для сценария оказалось маленьким, k < 4, то мы уже доказали полностью нашу оценку. А вот если "большое аккуратное" выделение оказалось слишком большим, то мы тут будем разбираться. Используя - именно построенное "большое аккуратное" выделение, с числом тайн k > 4.

Для начала, заметим: "большое аккуратное" выделение в сценарии для N болтушек обязано включать не больше, чем (N-2) тайны: для его построения две тайны выбрасываются с самого начала. А следовательно, все сценарии для 5 болтушек уже закрыты, в них не случается неприятностей, и оценка M(5) доказана. База индукции у нас есть.

Теперь заметим ключевое: если "большое аккуратное" выделение действительно большое, k >= 4, то M(k) >= k. То есть (по предположению индукции) число активных разговоров для этого выделения не меньше числа тайн. И при N = 6 сценарии с такими выделениями уже действительно существуют. Ну что-же, давайте применять индукцию.

Пусть доказана оценка M(k) >= 2k - 4 при всек k < K. Рассмотрим сценарий переговоров из N = (K + 2) болтушек, для которого "большое аккуратное" выделение содержит k > 4 тайн. Докажем, что ММ >= 2N - 4. Из этого следует, что значение К можно поднять на 1 и перейти к следующему шагу (так как для других сценариев с этим N всё уже доказано).

Шаг 1': Определяем начальное выделение тайн по-новому: выкидываем не первую пару болтушек, а вот это вот "большое аккуратное" выделение. Начиная таким образом, мы исключаем какое-то число тайн (N - k') = k (оно не меньше 4 и не больше N - 2) - но разговоров при этом мы исключаем не меньше.

Проведём после Шага 1' Шаги 2 и 3:
MM >= (N - k') + M(k') + (N - k')

число k' - любое, от 1 до К = (N - 2), для всех из них по предположению индукции уже доказано: M(k') = (2k' - 4). Итого:

ММ >= 2N + M(k') - 2k' = 2N - 4.

Ух... Вот теперь ВСЁ!!!!

Пока.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments