polytheme: несколько забавных школьных задачек, чтоб не забыть

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

1. группу заключенных размещают в одиночных камерах, и каждый день по одному заключенному водят в комнату с включающейся/выключающейся лампочкой, которую кроме них никто не трогает - водят так, что за бесконечное число дней каждый заключенный сходит к лампочке бесконечное число раз. в какой-то момент любой заключенный может сказать "все побывали в комнате с лампочкой". если он прав, заключенные победили. перед размещением по камерам заключенным разрешают всем вместе сговориться. могут ли они победить ?

2. троих заключенных размещают в одиночных камерах, в каждой камере одна лампочка. каждый день каждая лампочка либо весь день горит, либо весь день потушена. неопределенное количество дней лампочки зажигаются произвольным образом, но начиная с некоторого дня (неизвестно заранее, с какого) приводится в действие либо схема А - каждый день горит ровно одна лампочка, либо схема Б - каждый день горят ровно две лампочки из трёх. после того, как заключенные отсидят весь натуральный ряд дней, их собирают проголосовать независимо друг от друга за одну из схем. побеждает большинство голосов. если схема будет угадана, заключенные победили. могут ли они так сговориться перед испытанием, чтобы победить ?

3. на n заключенных надевают шляпы, на каждой шляпе одно число от 1 до n, числа могут совпадать. заключенный видит все числа, кроме своего. после этого их разводят по камерам, и там каждый называет своё число. если хотя бы один угадает, они победили. могут ли они так сговориться перед и т.п.

4. как в 2^n-1 битах закодировать 2^n-n-1 так, чтобы при ошибке в любом одном бите (либо при отсутствии ошибок) можно было исходные биты однозначно декодировать ?

(Добавить комментарий)

	pet531 2013-04-03 19:47 (ссылка)
	а можно решение задачи 2? а то мы всем миром долго думали как-то и не вышло ничего. удалённым комментом, например. (Ответить) (Ветвь дискуссии)

	polytheme 2013-04-03 19:56 (ссылка)
	ага, я вспомню только, и запощу. наверное, завтра вечером. (Ответить) (Уровень выше) (Ветвь дискуссии)

	pet531 2013-04-04 16:22 (ссылка)
	а, прикольно, спасибо! (Ответить) (Уровень выше) (Ветвь дискуссии)

lenkasm
2013-07-18 13:56 (ссылка)

а вот оно, кстати
http://lj.rossia.org/users/polytheme/42074.html?thread=127834#t127834
если политем вам еще не написал
как не написал мне, кстати обидно немного:
предлагаешь для обсуждения задачи и не обсуждаешь

(Ответить) (Уровень выше) (Ветвь дискуссии)

	polytheme 2013-07-18 14:34 (ссылка)
	Лёня, извини, пожалуйста, замотался на работе, а потом забыл. Пожалуйста, не обижайся (Ответить) (Уровень выше) (Ветвь дискуссии)

	lenkasm 2013-07-18 14:37 (ссылка)
	а, ок мне уже объяснил stanton решения (Ответить) (Уровень выше) (Ветвь дискуссии)

	polytheme 2013-07-18 14:47 (ссылка)
	обидно, извини пожалуйста ещё раз, ты вторую почти решил на самом деле (Ответить) (Уровень выше) (Ветвь дискуссии)

lenkasm
2013-07-18 15:07 (ссылка)

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

	polytheme 2013-07-18 17:35 (ссылка)
	Lyonya, please don't be afraid that someone hit you. I will explain mistake in your solution later, now I'm in some catastrophic situation, my linux crashed and I have to repair it. Sorry for english, I have no russian letters now (Ответить) (Уровень выше)

	stanton 2013-07-22 16:01 (ссылка)
	Просто переход не зависит от любой конечной части расклада => не зависит от расклада, не верен. Пример: f(X) = 1, если существует k такое, что X(n) = 1, для любого n > k; f(X) = 0, иначе (Ответить) (Уровень выше) (Ветвь дискуссии)

polytheme
2013-07-22 17:23 (ссылка)

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

(Ответить) (Уровень выше)

lenkasm
2013-07-28 00:11 (ссылка)

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

	stanton 2013-07-29 03:50 (ссылка)
	Пришлешь смс, когда вы надумаете? Я не уверен, что смогу, очень щас занят, но если это совпадет с моментом, когда я вымотаюсь и захочу отдыхать, то, конечно, тусить это лучшее отдыхать (Ответить) (Уровень выше)

(Скрытый комментарий)

(Скрытый комментарий)

lenkasm
2013-04-24 19:59 (ссылка)
задача повышенной трудности сводится к задаче обычной трудности за счет того, что тот кто считает когда первый раз попадает к лампочке выключает ее, и дальше считается как если бы с этого дня начинается заключение

насчет сумматора я конечно погорячился, просто думал сначала о другом решении, и когда из него получилось наконец правильное, не подумал что лишнее и в чем соль
(Ответить) (Уровень выше) (Ветвь дискуссии)

polytheme
2013-04-24 23:31 (ссылка)
p.s. я засунул основную часть нашей беседы под глаз, чтобы никто не догадался :)
(Ответить) (Уровень выше) (Ветвь дискуссии)

lenkasm
2013-04-25 00:30 (ссылка)
ты попутал мне кажется в задаче повышенной сложности.
" если она была выключена заключенным, а он сочтет, что с самого начала, он зажжёт лампочку лишний раз и будет ждать, пока её выключат, вечно, потому что все заключенные уже выполнили свою норму."

это ерунда, ему плевать, кто выключил лампу, он начинает считать с нуля до n-1. если лампочка уже была выключена заключенным, то этот заключенный ведь снова придет и ее выключит когда-нибудь, и он его посчитает тогда. а то, что заключенный выключал ее еще до начала отсчета - кого ебет?
(Ответить) (Уровень выше)

lenkasm
2013-04-25 00:38 (ссылка)
ой, я туплю
(Ответить) (Уровень выше) (Ветвь дискуссии)

lenkasm
2013-04-25 00:39 (ссылка)
ну ок, тогда просто первый заключенный который приходит выключает лампу и не считает это за свою норму. он же знает что это первый день
(Ответить) (Уровень выше)

polytheme
2013-04-23 18:25 (ссылка)
извини, забыл ответить:
элементы - это http://elementy.ru/
там периодически бывает разная прикольная инфа из разных отраслей науки
(Ответить) (Уровень выше) (Ветвь дискуссии)

lenkasm
2013-04-24 19:59 (ссылка)
спасибо!
(Ответить) (Уровень выше) (Ветвь дискуссии)

polytheme
2013-04-24 23:36 (ссылка)
а ты сейчас в Германии, или в Питере ?
(Ответить) (Уровень выше) (Ветвь дискуссии)

lenkasm
2013-04-25 00:30 (ссылка)
г.
(Ответить) (Уровень выше)

lenkasm
2013-04-25 00:30 (ссылка)
а ты в М или П?
(Ответить) (Уровень выше)

lenkasm
2013-04-26 02:16 (ссылка)
вторая задача, алгоритм мог бы быть такой:
назовем условием х для данного заключенного: количество дней с включенными лампочками больше либо равно количеству дней с выключенными лампочками
*как-нибудь воспользуемся этим*

проблема в том, что условие х нематематическое, по крайней мере по моим воспоминаниям. меня учили, что две бесконечности так нельзя сравнивать; (бесконечность = бесконечность * 2); хотя конечно бесконечность < (2 ^ бесконечность), но это не тот случай. не подскажешь, как тут с теорией?
(Ответить) (Ветвь дискуссии)

lenkasm
2013-05-08 04:10 (ссылка)
Задача 2, опять хочу доказать невозможность.

Ограничимся для схемы А случаями, когда у одного из заключенных лампочки всегда потушены, для схемы Б у одного из заключенных все ламопчки всегда горят, и докажем невозможность проголосовать за правильную схему в этих случаях.

При нашем ограничении двое заключенных получают одинаковые правила для зажжения лампочек при
обоих схемах.
Если они голосуют одинаково, то есть при каком-нибудь раскладе оба голосуют за одну из схем, то они проигрывают, поскольку побеждает эта схема, а такой же расклад возможен и при другой схеме.
Значит, они должны проголосовать каждый за разные схемы.

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

Таким образом, необходимы функции f1 и f2 для двух заключенных, f: расклад -> схема, такие что
f1( X) = not f2(X*),
где X это известный заключенному набор состояний лампочек в его камере в каждый из дней заключения ("расклад"), а X* - это любой возможный расклад у другого заключенног, а not схема А = схема Б и vice versum.

Таких функций не существуют, для того чтобы это доказать, покажем, что
для любого натурального k
f1( X) = f1( X_k)
где расклад X_к - это любой фиксированный расклад, в котором первые k дней лампочки зажигались как-нибудь по-другому, чем в раскладе X, а в остальные дни зажигались так же.

Мы имеем
f1(X) = not f2(X*)
и
f1(X_k) = not f2(X_k*)
и (ad absurdum)
f1(X) = not f1(X_k),
откуда следует
f2(X*) = not f2(X_k*)
то есть у другого заключенного тоже должны быть разные расклады в этом случае.

Очевидно, что мы можем имитировать первые k дней у другого заключенного как нам угодно,
то есть он всегда будет иметь одно и то же значение функции, противоречие.

Иными словами мы показали, что значение функций не зависит от первых k значений расклада для любого k, то есть не зависит ни от одного дня расклада, т.е. для всех раскладов одинаково. q.e.d.
(Ответить) (Уровень выше)

(Скрытый комментарий)

stanton
2013-07-16 22:13 (ссылка)
ПЫЫЦ
(Ответить) (Уровень выше)