математики в тюрьме
Sep. 2nd, 2001 01:10 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaА вот ещё одна задачка, тоже хорошая и совсем из другой области. Интересна она будет только тем, кто имеет склонность к математике, поэтому закрываю её элжекатом. Любопытна она своим садистским началом:
Троих математиков сажают в тюрьму на бесконечное количество дней.
Бесконечность дней - счётная, она же алеф-ноль. Каждый математик сидит
в отдельной одиночной камере, и общаться между собой во время заточения
они никак не могут.
В каждой камере есть лампа, которая в каждый конкретный день может либо гореть весь день (т.е. в этот день есть свет в камере), либо не гореть (т.е. в камере темно). Каждый математик знает о состоянии света только в своей камере.
Математикам известен следующий факт. Распределение света по дням в камерах произойдёт по одному из двух сценариев:
1. В каждый отдельный день свет горит только в одной камере из трёх (но необязательно в одной и той же в разные дни).
2. Сначала, некоторое конечное количество дней, свет горит только в одной камере из трёх как и раньше, а потом, на протяжении всего срока, он горит каждый день в двух камерах из трёх (которые тоже могут меняться изо дня в день).
После того, как математики отсидят свой срок (все алеф-ноль дней), их выпустят и каждого в отдельности спросят (не дав возможности общаться с другими): какой из двух вариантов выше, по его мнению, на самом деле имел место? Если больше половины математиков (т.е. двое или трое) ответят на этот вопрос правильно, всех троих отпускают на свободу; если меньше половины ответят правильно, их опять сажают в тюрьму.
До начала заключения математики могут договариваться о чём угодно. Вопрос: могут ли они составить стратегию поведения, которая обеспечила бы им, что после отсидки срока их отпустят на свободу?
Update: Осторожно! В комментах находится правильное решение.
Троих математиков сажают в тюрьму на бесконечное количество дней.
Бесконечность дней - счётная, она же алеф-ноль. Каждый математик сидит
в отдельной одиночной камере, и общаться между собой во время заточения
они никак не могут.
В каждой камере есть лампа, которая в каждый конкретный день может либо гореть весь день (т.е. в этот день есть свет в камере), либо не гореть (т.е. в камере темно). Каждый математик знает о состоянии света только в своей камере.
Математикам известен следующий факт. Распределение света по дням в камерах произойдёт по одному из двух сценариев:
1. В каждый отдельный день свет горит только в одной камере из трёх (но необязательно в одной и той же в разные дни).
2. Сначала, некоторое конечное количество дней, свет горит только в одной камере из трёх как и раньше, а потом, на протяжении всего срока, он горит каждый день в двух камерах из трёх (которые тоже могут меняться изо дня в день).
После того, как математики отсидят свой срок (все алеф-ноль дней), их выпустят и каждого в отдельности спросят (не дав возможности общаться с другими): какой из двух вариантов выше, по его мнению, на самом деле имел место? Если больше половины математиков (т.е. двое или трое) ответят на этот вопрос правильно, всех троих отпускают на свободу; если меньше половины ответят правильно, их опять сажают в тюрьму.
До начала заключения математики могут договариваться о чём угодно. Вопрос: могут ли они составить стратегию поведения, которая обеспечила бы им, что после отсидки срока их отпустят на свободу?
Update: Осторожно! В комментах находится правильное решение.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2001-09-02 03:54 am (UTC)Ðàçóìååòñÿ, ÷àñòîòà íå îáÿçàíà ñóùåñòâîâàòü. Íî ÿ äóìàþ, ÷òî îáùåå ðåøåíèå ðàáîòàåò íà òîì æå ïðèíöèïå.
no subject
no subject
no subject
Date: 2001-09-02 06:02 am (UTC)To choose one sock from each of infinitely many pairs of socks requires the Axiom of Choice, but for shoes the Axiom is not needed.
no subject
Ïðî óëüòðàôèëüòðû ìîãó âêðàòöå îáúÿñíèòü, åñëè íàäî.
óæå :)
no subject
Date: 2001-09-02 09:45 am (UTC)no subject
Date: 2001-09-02 03:12 pm (UTC)Íî ýòî âñ¸ æå ïåðèôåðèéíî î÷åíü, ðàçâå íåò? Áîëüøèíñòâó ìàòåìàòèêîâ ãëóáîêî íàïëåâàòü íà ïðîáëåìû, ñâÿçàííûå ñ àêñèîìîé âûáîðà, è íå âñåãäà îíè îá ýòèõ ïðîáëåìàõ âîîáùå çíàþò.
ß ïîäîçðåâàþ, ÷òî ýòî ñâÿçàíî ñ èíòåðåñîì Êîíâåÿ ê èñòîðèè ìàòåìàòèêè. Îí î÷åíü ìíîãî çíàåò â ýòîé îáëàñòè è èíòåðåñíî îá ýòîì ðàññêàçûâàåò - ÿ áûë ïîäïèñàí íåñêîëüêî ëåò íà ðàññûëêó ïî history of mathematics, íà êîòîðîé îí òîæå áûë è äîâîëüíî ÷àñòî ïèñàë (ðàññûëêà, êàæåòñÿ, ðàñïàëàñü ñ òåõ ïîð).
À åñòü ëè ó Âàñ ìíåíèå ïî ïîâîäó äðóãîé òåìû - îòíîøåíèÿ ê äîêàçàòåëüñòâàì, èñïîëüçóþùèì êîìïüþòåðíóþ âåðèôèêàöèþ? ß èìåþ â âèäó â ïåðâóþ î÷åðåäü èìåþùèåñÿ äîêàçàòåëüñòâà òåîðåìû î ÷åòûð¸õ öâåòàõ.
no subject
Date: 2001-09-02 03:33 pm (UTC)Ó ìåíÿ åñòü íåêàÿ ôèëîñîôèÿ íà ýòîò ñ÷åò. Îòïèøó ÷óòü ïîçæå.
Ïîñìîòðèòå, êñòàòè, ñòðàíèöó Çàéëüáåðãåðà (ññûëêà â ìîåì ïîñòèíãå ïðî äîêëàä). Ó íåãî äîâîëüíî ðàäèêàëüíûå âîççðåíèÿ íà ýòî.
computer-aided math êàê è îáåùàë
Date: 2001-09-03 01:34 am (UTC)Âîçðàæåíèÿ ïðîòèâ êîìïüþòåðíîé ìàòåìàòèêè äåëÿòñÿ, ãðóáî ãîâîðÿ, íà ôîðìàëüíûå, êîíöåïòóàëüíûå è ïñèõîëîãè÷åñêèå.
Ôîðìàëüíûå âîçðàæåíèÿ: êîìïüþòåð íå îáåñïå÷èâàåò ñòðîãóþ ôîðìàëüíóþ ïðîâåðêó äîêàçàòåëüñòâà. Âîïåðâûõ, îí ìîæåò ñáîèòü. Âîâòîðûõ, ýëåêòðîíû âåðîÿòíîñòíû è íåèçâåñòíî êóäà çàëåòàþò. Òàê ÷òî êîìïüþòåðó âåðèòü íåëüçÿ.
Îòâåò çäåñü î÷åâèäåí: ÷åëîâå÷åñêèé ìîçã òîæå ìîæåò "ñáîèòü". Âîîáùå, ñ ýòîé ìàêñèìàëèñòêîé òî÷êè çðåíèÿ, ìàòåìàòè÷åñêàÿ ñòðîãîñòü íåâîçìîæíà. Âåäü, ñêàæåì, äîêàçàòåëüñòâî òåîðåìû Ïèôàãîðà áûëî ïðîâåðåíî êîíå÷íûì ÷èñëîì ïåðñîí, êàêæäûé èç êîòîðûõ ìîã îøèáèòüñÿ ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ. Ò.î. åñòü ïîëîæèòåëüíàÿ âåðîÿòíîñòü, ÷òî Ò.Ï. íåâåðíà.
Ìåíÿ ýòà ïðîáëåìà áåñïîêîèò ñî øêîëüíûõ ëåò, è ÿ íå âèæó äðóãîãî âûõîäà, êðîìå êàê ïðèçíàòü ðåëÿòèâèçì íàøèõ ïðåäñòàâëåíèé î ñòðîãîñòè. Íàì âñå æå î÷åíü äàëåêî äî Ãäà Áãà.
Òàê èëè èíà÷å, ïîÿâëåíèå êîìïüþòåðîâ íå ïðèâíîñèò íîâîé íåíàäåæíîñòè. Áîëåå òîãî, êîìïüþòåð êóäà áîëåå, ÷åì ÷åëîâå÷åñêèé ìîçã, ïðèãîäåí äëÿ ìåõàíè÷åñêîé âåðèôèêàöèè ñëîæíûõ ôîðìàëüíûõ ðàññóæäåíèé.
Êîå÷òî íà ýòî òåìó ïèñàë Ìàíèí:
Manin, Yu. I., Truth, rigour, and common sense. Truth in mathematics (Mussomeli, 1995), 147--159, Oxford Univ. Press, New York, 1998.
Âïðî÷åì, êîãäà ÿ ïðèñòàë ê íåìó ïî ïîâîäó ýòîé ñòàòüè, îí ïîïðîñèë íå âîñïðèíèìàòü åå ñëèøêîì âñåðüåç. Åìó ïðîñòî î÷åíü õîòåëîñü çàëåçòü íà Ýòíó, à äëÿ ýòîãî íàäî áûëî ïîåõàòü íà ýòó êîíôåðåíöèþ, à òàì íàäî áûëî äàòü äîêëàä.
Êîíöåïòóàëüíûå âîçðàæåíèÿ: êîìïüþòåð ïîäìåíÿåò êîíöåïòóàëüíûå ðàññóæäåíèÿ ìåõàíè÷åñêèì ñ÷åòîì. Ïî÷òîìó êîìïüþòåðíûå äîêàçàòåëüñòâà ÿâëÿþòñÿ "äîêàçàòåëüñòâàìè ðàäè äîêàçàòåëüñòâà" è íå ñïîñîáñòâóþò ðàçâèòèþ ìàòåìàòèêè.
(ïðîäîëæó çàâòðà, åñëè èíòåðåñíî)
Ï.Ñ. Ïî ïîâîäó Êîíâåÿ. Îí äàâíî âîþåò ñ àêñèîìîé âûáîðà. ß íå îòñëåæèâàë äåòàëåé, íî ýòî èçâåñòíàÿ èñòîðèÿ. Äåëî íå â åãî èíòåðåñå ê èñòîðèè, à, êàê ìíå êàæåòñÿ, îí ïðîñòî õî÷åò ïîâûñòóïàòü. Íî ìàòåìàòèê îí áîëüøîé, ñïîðó íåò.
Re: computer-aided math êàê è îáåùàë
Date: 2001-09-03 01:38 am (UTC)Îáÿçàòåëüíî ïðîäîëæó,
Date: 2001-09-03 02:12 am (UTC)Âîéíó âèäàë. Ñåðüåçíî.
computer-aided math (îêîí÷àíèå)
Íà ýòî ó ìåíÿ åñòü äâà çàìå÷àíèÿ. Âîïåðâûõ, ñàìî ñâåäåíèå ïðîáëåìû ê êîìïüþòåðíî ðåøàåìîìó âèäó ÿâëÿåòñÿ çà÷àñòóþ âåñüìà ñîäåðæàòåëüíîé çàäà÷åé. Âîçüìåì, ñêàæåì, çíàìåíèòóþ ãèïîòåçó Êàòàëàíà (1844):
Óðàâíåíèå x^u-y^v=1 íå èìååò íåòðèâèàëüíûõ ðåøåíèé â ïîëîæèòåëüíûõ öåëûõ ÷èñëàõ, êðîìå 3^2-2^3=1.
 1975 ã. ãîëëàíäåö Òàéäåìàí ñäåëàë ñåáå èìÿ, ðåøèâ çàäà÷ó â ïðèíöèïå, ò.å. ñâåäÿ åå ê êîíå÷íîìó âû÷èñëåíèþ. Âåñüìà îñòðîóìíûì ðàññóæäåíèåì îí ïîêàçàë, ÷òî âñå 4 ïåðåìåííûå x,y,u,v îãðàíè÷åíû âû÷èñëèìîé àáñîëþòíîé ïîñòîÿííîé. Âåëè÷èíà æå ïîñòîÿííîé áûëà òàêîâà, ÷òî äàæå äëÿ ñîâðåìåííûõ ãèãàãåðöåâûõ êîìïüþòåðîâ çàäà÷à áåçíàäåæíà.
Ñ òåõ ïîð â ýòîé îáëàñòè ñäåëàí íåìàëûé ïðîãðåññ (â îñíîâíîì óñèëèÿìè ôðàíöóçà Ìèíüîòòà è ðóìûíà Ìèõàéëåñêó), íî êîìüþòåðíîìó ñ÷åòó çàäà÷à ïîïðåæíåìó íå ïîääàåòñÿ. Ïðè ýòîì, ïðèìåíÿþòñÿ ìåòîäû êóäà áîëåå ãëóáîêèå, ÷åì îðèãèíàëüíîå ðàññóæäåíèå Òàéäåìàíà.
Äà è ðåøåíèå 4 êðàñîê âîâñå íå òîëüêî ñ÷åò. Ñàìî ñâåäåíèå ê ñ÷åòó äîâîëüíî ñåðüåçíàÿ ìàòåìàòèêà.
Âòîðîå çàìå÷àíèå îòíîñèòñÿ ïîíÿòèþ "âíóòðåííåé òðóäíîñòè" çàäà÷è. Êàæäàÿ ìàòåìàòè÷åñêàÿ çàäà÷à èìååò ñâîþ "âíóòðåííþþ òðóäíîñòü". Óìåíèå îöåíèòü ýòî òðóäíîñòü îäíî èç ãëàâíåéøèõ äëÿ ïðîôåññèîíàëüíîãî ìàòåìàòèêà. Çà÷àñòóþ, ÷òîáû ðåøèòü çàäà÷ó, äîñòàòî÷íî ïî÷óâñòâîâàòü, ÷òî îíà ïîääàåòñÿ ðåøåíèþ. Îá ýòîì ìîæíî ìíîãî ïèñàòü (ìîæåò áûòü, êîãäà íèáóäü è íàïèøó), íî äëÿ íàñ âàæåí ëèøü ñëåäóþùèé àñïåêò. Ìîæåò áûòü, âíóòðåííÿÿ òðóäíîñòü 4 êðàñîê èìåííî òàêîâà, ÷òî áåç êîìïþòåðíîãî ïåðåñ÷åòà îíà â ïðèíöèïå íå ðåøàåòñÿ? Ìîæåò áûòü, ýòîò ñ÷åò íå ïîäìåíÿåò íèêàêîå êîíöåïòóàëüíîå ðàññóæäåíèå? Íåòó çà ýòèì êîíöåïöèè, è âñå òóò, íåñìîòðÿ äàæå íà ëþáîïûòíûå
íàáëþäåíèÿ ÁàðÍàòàíà.
Ïñèõîëîãè÷åñêèå âîçðàæåíèÿ: íó õî÷åòñÿ âñåòàêè îáîéòèñü áåç êîìïüþòåðîâ.
Àãà, ìíå òîæå èíîãäà õî÷åòñÿ. Íî ýòî âðåìåííîå, ïðîéäåò.
Âîò, ñîáñòâåííî è âñå. Äîñòàòî÷íî ïîâåðõíîñòíî, íî ïîìîåìó, ïî äåëó.
Ïðèâåò,
Ôðàíöóçèê.
Zagadka
Date: 2001-09-05 12:38 pm (UTC)Sidjat, stal byt', matematiki i schitajut summu
shodjaschegosja rjada, i n-yj chlen mnozhat na 0
esli sveta net i na 1 esli sveta est'.
A potom tipa skladyvajut vse vmeste
Nishtjak!
Re: Zagadka
Date: 2001-09-09 04:01 pm (UTC)no subject
Date: 2004-10-28 06:24 pm (UTC)pdf
Date: 2004-10-28 06:34 pm (UTC)no subject
Date: 2009-12-26 04:54 pm (UTC)no subject
Date: 2011-02-12 01:44 am (UTC)