Математика и секс
Август 5th, 2011

Гномики и аксиома выбора

По наводке читателя.

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

По сигналу гномики одновременно выкрикивают цвета (синий или красный), пытаясь угадать цвет своей шапки.

Существует ли стратегия (т.е. функция $latex \mathbb F_2 ^\infty \times \mathbb N \to \mathbb F_2$, определяющая цвет, который гномик должен выкрикнуть исходя из того, какую раскраску он видит впереди) придерживаясь которой ошибется лишь конечное число гномиков (для каждой раскраски гномиков из условия задачи)?

Вначале мне показалось, что задача некорректно сформулирована. Если гномики выкрикивают свои цвета одновременно, то у них пропадает какая-либо возможность обмениваться информацией, что меня и смутило. Я предположил, что вероятно кричат свои номера они все же не одновременно, а по порядку, и в этом случае задачу я почти решил: количество ошибок гномиков довольно простым способом возможно сильно сократить (сколь угодно сильно), хотя все равно ошибшихся гномиков будет бесконечное множество (если предположить, что они называют только цвет и не могут передать дополнительной информации). Вы можете попытаться решить задачу в таком варианте сами — это не сложно. Ну либо почитайте мой комментарий к прошлой заметке.

Однако оказалось, что при использовании аксиомы выбора задача все же решается. Сам я ее решить не смог, потребовав решения от задавшего задачу, и вот собственно это решение я теперь и привожу (сама задача изначально читателем как я понимаю была обнаружена в блоге «The everything seminar», перевод на русский здесь).

Фактически, когда на гномиков надеваются шапки, реализуется некоторая последовательность цветов. На множестве всех таких последовательностей введем отношение эквивалентности следующим образом: две последовательности будем считать эквивалентными, если они отличаются лишь конечным числом цветов. Далее в каждом классе эквивалентности выберем по одному представителю (то есть это должны сделать гномики). Мы имеем на это право именно по аксиоме выбора.

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

Очевидно, что представитель класса отличается от любой другой раскраски данного класса лишь конечным количеством цветов. Так что ошибку допустит лишь конечное число гномиков. Что и требовалось.

Аксиома выбора вообще замечательная, но эта головоломка с гномиками до сих пор на мой взгляд самый яркий пример ее применения (абсурдный конечно, как может показаться, но вполне себе занятный). Здесь был бы уместен рассказ и о других применениях аксиомы выбора, но его не будет, так как одного только подготовительного текста о лемме Цорна и базисе Гамеля будет довольно много, и он будет не слишком тривиален. Поэтому всех интересующихся отправляю за книжкой Верещагина и Шеня «Начала теории множеств». Она как раз во многом об этом, и понять ее сможет почти каждый, что важно.

14 комментариев »

  1. ух–ты, математика! неожиданно

    Comment by Старков Владимир — 05.08.2011 @ 15:46
  2. @ Старков Владимир:
    К сожалению о математике я сейчас почти не пишу, так как она требует в несколько раз больше времени, которое тратится на набор формул. Увы, просто совершенно не успеваю.

    Comment by Хеллер — 05.08.2011 @ 16:01
  3. здесь перевод оригинального поста: http://lj.rossia.org/users/muda/5782.html

    Comment by D — 06.08.2011 @ 00:53
  4. Лучше ещё про шлюх — эта тема жизненнее, чем аксиома выбора

    Comment by Anonymous — 06.08.2011 @ 02:30
  5. @ D:
    Ага, поставил ссылку.

    Comment by Хеллер — 08.08.2011 @ 10:36
  6. @ Anonymous:
    В ряд стоит счётное число шлюх…

    Роман, тут существенно используется простой факт, который мне не показался сначала очевидным: из транзитивности НЕ следует счётная транзитивность. Сначала я рассуждал так: из любой последновательности можно получить любую путём счётного числа преобразований, меняющих конечное число элементов (например, по одному: на n-том шаге преобразовываем n-й член). Каждые две соседние последовательности эквивалентны, поэтому исходные последовательности — тоже, значит вообще все последовательности эквивалентны. Но то что это не так опровергает исходное предположение, значит нельзя применять счётную транзитивность.

    Comment by overrider — 14.08.2011 @ 17:20
  7. @ overrider:
    Спасибо. Да, наколка здоровская получилась. Завтра добавлю это в заметку.

    Comment by Хеллер — 14.08.2011 @ 22:41
  8. @ overrider:
    Писал сейчас заметку, посвященную вашему замечанию, и столкнулся с затыком — я не вижу каким образом из того, что в последовательности все элементы принадлежат одному классу эквивалентности, следует, что «результат» (вторая последовательность, которую мы строим через эти конечные замены) будет принадлежать тому же классу эквивалентности. Я либо не выспался, либо подзабыл теорию множеств, но вот это место какое-то совершенно неочевидное, и у меня не получается таким образом увидеть противоречия в изначальном решении.

    Comment by Хеллер — 16.08.2011 @ 10:13
  9. @ Хеллер:
    долго въезжал в вопрос. мы говорим здесь уже про последовательность последовательностей, не про последовательность шапок.
    просто интуитивно казалось, что из попарной эквивалентности соседних элементов следует через предельный переход эквивалентность первого (или любого другого) элемента пределу. очевидно, что это не так, иначе бы нарушались аксиомы эквивалентности по отношению к отношению изменения конечного числа элементов.

    Comment by overrider — 17.08.2011 @ 09:17
  10. Вот решение которое могу предложить: Пусть если количество синих (красных) шляп четно, то говорит синий (или наоборот, это не важно), если не четно, то наоборот. Таким образом, гном стоящий последним ошибется 50/50, остальные зная четность какого то цвета и видя перед собой остальные шляпы сможет сказать какого цвета на нем шляпа (т.е. если при переходе очереди к нему четность, которую он видит изменилась, значит на нем синяя (красная) шляпа ). Только вот я пока не могу отображение придумать. :(

    Comment by noam — 19.08.2011 @ 19:43
  11. Хорош ты пацан, ты молодец — умница, никого не боишься. p(n) — вот мое решение, и я это решил можешь не сомневаться.

    Comment by тотем — 11.09.2011 @ 21:00
  12. Тебе повезло, пишу потому как пьян. Блаженный Харди обыскался тщясь найти бумажки или как их там они называют. Так что спрашивай пока я пьян.

    Comment by тотем — 11.09.2011 @ 21:22
  13. То,что были удалены мои комменты сообщено. В частности на лж у Миши.

    Comment by Тот — 11.09.2011 @ 23:29
  14. Аксиома выбора утверждает, что существует Функция выбора, но не говорит, как её найти. Бедные гномики будут знать, что искомая стратегия существует, но не смогут её применить. И бдут умирать.

    Comment by Никита — 11.12.2011 @ 11:30

RSS feed for comments on this post. TrackBack URI

Оставить комментарий

This work is licensed under GPL - 2009 | Powered by Wordpress using the theme aav1
SEO Powered by Platinum SEO from Techblissonline