پستها: 14
زبان: Esperanto
Sxak (نمایش مشخصات) 19 نوامبر 2009، 15:44:03
En prizono troviĝas 100 malliberuloj. Ĉiu el tiuj 100 havas unikan nomon (estu numero) Morgaiŭ ili havos gravan teston. En aparta ĉambro estos 100 kestoj. En ĉiu kesto estos 1 papero kun nomo (do numero) de unu el la malliberuloj. (Certe por ĉiu malliberulo estos kesto kun lia nomo)
Morgaŭ ili po unu homo eniros tiun ĉambron. Ĉiu rajtos rigardi 50 kestojn kaj devos trovi keston kun sia nomo. Post ĉiu malliberulo la ĉambro kun kestoj restos en la sama stato, kia ĝi estis antaŭ lia vizito (tio signifas, ke ili ne rajtos remeti la paperojn, la kestojn, ktp). Vizitinte tiun ĉambron malliberulo foriras en alian lokon (do povas nenion sciigi al la ankoraŭ ne testitaj malliberuloj) Se almanaŭ 1 el la malliberuloj ne trovos sian keston, do ili ĉiuj estos ekzekutitaj.
Montru, ke la malliberuloj havas strategion, kiu permesos al ili travivi tiun teston kun la probableco ne malpli ol 30% (fakte la probableco strebas al 1-log(2) kaj jam ĉe 2n=100 superas 0.3)
Miland (نمایش مشخصات) 19 نوامبر 2009، 17:10:48
'Lasi la ĉambron en la sama stato' signifas nur ke antaŭulo ne remetu keston nek paperon. Sed ĝi ne eksklusivas re-aranĝon.
La unua prizonulo rearanĝas 49 de la kestoj, kiujn li povos malfermi, por ke iliaj numeroj estas ordigitaj. Li ankaŭ proksimigas kiel najbarojn kestoj inter kiuj estas neniu aliaj. Tio donos pli da informo.
Lia probableco de sukceso estas kompreneble 0.5.
La dua unue serĉos la ordigitan vicon. Li rapide povos lerni ĉu la lia estas tie (dum, ni diru, 6 serĉoj) kaj havas pli ol 40 provoj al la aliaj 50, kaj verŝajne trovos sian. Li aranĝos (ni diru) aliajn 40 kestojn simile al la unua prizonulo.
Pro la klopodoj de la unua, mi kredas ke la probableco de la dua travivi estas pli ol 0.6, por ke la probableco de la travivo de la unua du estas pli ol 0.3.
La tria havos sufiĉe da provoj por ordigi la ceterajn kestojn kaj aldoni ĝin al la dua vico, krom trovi sian propran keston.
La ceteraj prizonuloj scias ke estas du ordigitaj vicoj kaj do povos rendimente serĉi iliajn kestojn kaj verŝajne eskapos.
Sxak (نمایش مشخصات) 20 نوامبر 2009، 2:36:28
Miland:Jen provo, kiu ne estas matematike pruvita solvo:Mi ne komprenis, kiel eblas rearanĝi la kestojn sen remeto de ili.
'Lasi la ĉambron en la sama stato' signifas nur ke antaŭulo ne remetu keston nek paperon. Sed ĝi ne eksklusivas re-aranĝon.
Tamen mi instistas, ke ekzistas absolute honesta solvo, kiu ekskluzivas ajnan ŝanĝon de la stato de la ĉambro kun kestoj, kvazaŭ neniu estus tie
Se vi dubas, ke ekzistas solvo pli favora ol 2^(-100), do imagu, ke 2n=2 (2 malliberuloj, 2 kestoj kaj 1 provo). Se la unua malfermos la unuan keston kaj la dua -- la duan, do la probableco saviĝi estas 1/2 kaj ne 1/4! (ĝeneraligo de tiu strategio por pli grandaj 2n estas solvo de tiu tasko)
Fakte en tiu strategio la probalecoj trovi siajn kestojn por ĉiuj malliberuloj estas multe interdependaj (mi ne scias ĝustan esperantan terminon, ĉar miaj vortaroj nun estas hejme kaj mi -- oficeje, sed mi esperas, ke la termino interdependa devas esti komprenebla)
Ĉe tiu forumo estis interesa historio de la solvo de tiu enigmo
Foje frumatene mi trovis tiun enigmon tie k komencis pensi. Post iom da minutoj mi revenis por relegi la enigmon kaj tuj trovis, ke unu forumano jam skribis strategion, pri kiu mi tuj kredis, ke ĝi estas sufiĉe favora (sed mi kontrolis tion poste, ĉar ne estis facile tuj kaj des pli pense trovi analitikan formulon por tiu probableco) kaj skribis, ke ĝi strebas al log(2). Evidentiĝis, ke baldaŭ li forigis ĉion, krom tiun log(2) kaj kiam vekiĝis moskvanoj, kiuj konsistigas plimulton da tiu forumo, ili tiuj komencis laŭte dubi Sed mi loĝas en multe pli orienta tempa zono, do la solvinto fakte montris la solvon al mi. Do mi povis nur ĵuri, ke la solvo ekzistas kaj mi vidis ĝin Fine de la tago la komuna racio solvis tiun enigmon... Post iom da semajnoj tiu enigmo estis proklamita la plej bona enigmo de tiu jaro (mi ne ĝuste memoras de kiu jaro, ŝajne de 2006)Sed via strategio certe estas interesa kaj ŝajne donas la probablecon pli grandan ol tiu 1-(1/51+1/52+...+1/100)
(pli ĝuste por ĝii la probableco estas ~ 0.47) Sed bedaŭrinde ĝi rompas la regulojn de la enigmo. 
fizikisto (نمایش مشخصات) 20 نوامبر 2009، 13:48:26
Ni nur rigardas la pozitivan kazon. (Se la unua ne trovus sian keston, la ago de la dua estus egala.)
Do, ni supozu, ke la nombro 1 troviĝas inter la kestoj 1...50. Se la dua malfermos kestojn 1...50, li trovas sian nombron je probableco 49/99 (ĉar ni scias, ke en unu el tiuj kestoj estas la nombro 1). Se la dua malfermos kestojn 51...100, la probableco estas 50/99. Se li elektos kaj el kestoj 1...50 kaj el kestoj 51...100, la probableco estas inter ambaŭ valoroj.
Tial, la probableco estas 1/2 * 50/99, kio estas nur malmulte pli bone ol 1/4. Sed nun ne eblas ke la tuta probableco estas pli ol 1/3.
Ĉu mi eraris?
Sxak (نمایش مشخصات) 20 نوامبر 2009، 14:56:25
fizikisto:Mi jam skribis, ke la eventoj "Ko-a malliberulo trovas sian keston" estas tre dependaj unu de la alia, do vi ne povas multipliki ilin
Tial, la probableco estas 1/2 * 50/99, kio estas nur malmulte pli bone ol 1/4. Sed nun ne eblas ke la tuta probableco estas pli ol 1/3.
Ĉu mi eraris?
Sed la solvo vere ekzistas!
Fakte jam ĉi tio:
fizikisto:La unua malfermos la kestojn 1...50, ĉar komence ĉiuj kestoj estas samaj.ne estas tute vera. La unua malfermas la kestojn laŭ algoritmo, por kiu ne egalas kiujn kestojn malfermi. Sed certe ni povos poste renumeri tiel la kestojn
Sxak (نمایش مشخصات) 20 نوامبر 2009، 15:04:03
Sxak (نمایش مشخصات) 20 نوامبر 2009، 15:20:45
fizikisto:Ekzemple en tiu temo Bert kaj Graf montris strategion, kiu permesos al la unuaj 2 travivi la teston kun la probableco 3/8:
Tial, la probableco estas 1/2 * 50/99, kio estas nur malmulte pli bone ol 1/4. Sed nun ne eblas ke la tuta probableco estas pli ol 1/3.
Ĉu mi eraris?
la unua malfermas la kestojn 1,2,3... Se li renkontas la keston kun la numero 2, do li daŭrigas 100,99,98
LA 2a komencas de 100: 100,99,98 kaj se li vidas la nomon de la unua, do li daŭrigas 1,2,3,..
Sed tiu strategio eĉ ne similas al tiu plej efika
fizikisto (نمایش مشخصات) 20 نوامبر 2009، 17:46:44
Mi proponas la sekvan procedon: La k-a malliberulo komencu malfermi la k-an keston. Ĉiam kiam li legas nombron n, li daŭrigu ĉe la kesto n. Li gajnas kiam li revenas al la komencpunkto k antaŭ la 50-a movo.
Por ĉiu komencpunkto oni nepre revenas, ĉar ne eblas la vico ekz. A,B,C,D,...K,C, ĉar la nombroj en la kesto B kaj K estas malsamaj. Do, komencante je iu ajn komencpunkto oni revenas post kelkaj movoj. Se la longeco de tiu cirklo estas L (L malpli ol 50), tio ankaŭ veras por ĉiuj komencpunktoj sur la cirklo.
Do, la malliberuloj gajnas, se la nombroj ne enhavas ciklon pli longan ol 50.
Mi provis la algoritmon per kelkaj paperetoj kaj trovis, ke oni gajnas ofte. Nun temas "nur"
pri pruvo, ke la probableco, ke permutaĵo el 100 elementoj ne enhavas ciklon pli longan ol 50, estas pli ol 30%. Sxak (نمایش مشخصات) 20 نوامبر 2009، 17:58:42
fizikisto:JES! TIO estas solvo! GRatulon!
Mi proponas la sekvan procedon: La k-a malliberulo komencu malfermi la k-an keston. Ĉiam kiam li legas nombron n, li daŭrigu ĉe la kesto n. Li gajnas kiam li revenas al la komencpunkto k antaŭ la 50-a movo.
fizikisto:Fakte trovi kaj pruvi formulon por tio ne estas tiom malfacila tasko, kiel trovi tiun algoritmon.
Nun temas "nur"
Miland (نمایش مشخصات) 20 نوامبر 2009، 19:58:49