Al la enhavo

kvizo

de Blua_Monto, 2021-marto-15

Mesaĝoj: 20

Lingvo: Esperanto

Blua_Monto (Montri la profilon) 2021-marto-15 01:03:21

Ludoviko kaj Johano ludas per 8 kartoj, sekvante suban regulon:

[regulo]
(i) Ili prenas karto(j)n alterne.
(ii) Ili rajtas preni unu, du aŭ tri karto(j)n po unu fojo, sed se unu el ili prenis tri kartojn, post tio, neniu el ili rajtas preni tri kartojn.
(iii) La persono, kiu akiris la okan karton, estas la venkanto de ĉi tiu ludo.
[/regulo]

Nun, jen estas demando: se Ludoviko estas la unua prenanto, kiom da karto(j)n Ludoviko unue devas preni, por ke Ludoviko venku malgraŭ kiel Johano prenas?

Blua_Monto (Montri la profilon) 2021-marto-15 01:04:31

Mi penis forigi ambiguecon, sed se miaj frazoj estas neklaraj, bonvolu sciigi al mi kaj mi klarigos.

StefKo (Montri la profilon) 2021-marto-15 10:17:37

Blua_Monto:L(...)
(ii) Ili rajtas preni unu, du aŭ tri karto(j)n po unu fojo, sed se unu el ili prenis tri kartojn, post tio, neniu el ili rajtas preni tri kartojn.
(...)
Pli ĝuste tiel?

(ii) Ili rajtas preni po unu, du aŭ tri karto(j)n unufoje (...)

Blua_Monto (Montri la profilon) 2021-marto-15 22:06:21

Eble. La vorto po estas iom malfacila por mi…

Metsis (Montri la profilon) 2021-marto-16 08:26:59

Tio estas konata ludo ene de la fako de la ludoteorio (ofte kun splitetoj aŭ ŝtonetoj anstataŭ kartoj). Temas pri tio, ke ambaŭ ludantoj havas kompletan informon pri la situacio aŭ la stato de la ludo kaj la nombro de alternativaj statoj en la ludo estas tre malalta. Do estas facile krei t.n. decidan arbon (decision tree) kun ĉiuj alternativoj. Ĉi tial eblas krei perfektan strategion, laŭ kiu unu el la ludantoj ĉiam venkas.

La konata solvo por tiaj ludoj estas, ke la dua ludanto ĉiam prenas komplementan amason de kartoj kaj tiel ĉiam venkas. Jen oni rajtas preni maksimume tri kartojn, do la komplementa amaso estas 4 minus kiom multajn kartojn la unua ludanto prenis. Tiel la dua ludanto ĉiam venkas. Sed via demando temas pri tio, kiel la unua ludanto povas venki. Alivorte vi serĉas la komplementon al tiu perfekta strategio.

La ŝlosilo estas la regulo "se unu el ili prenis tri kartojn, post tio, neniu el ili rajtas preni tri kartojn". Tio eblas al la unua ludanto fari tian movon, kiun la dua ludanto ne povas kontraŭi.

Lasu ni ekzameni la alternativojn.

Ludoviko komencas per preni unu karton

Laŭ la perfekta strategio Johano prenas 4-1=3 kartojn. Restas 4. Pro la aldona regulo Ludoviko povas preni nur unu aŭ du kartojn. Se li prenos unu, restos 3 kaj Johano ne povos preni ĉiujn. Do Ludoviko venkos. Se anstataŭe Ludoviko prenos du kartojn, restos 2 kaj Johano venkos.

Ludoviko komencas per preni du kartojn

Laŭ la perfekta strategio Johano prenas 4-2=2 kartojn. Restas 4, kaj vi povas vidi, ke iun ajn nombron Ludoviko nun prenos, Johano venkos.

Ludoviko komencas per preni tri kartojn

Laŭ la perfekta strategio Johano prenas 4-3=1 karton. Restas 4. Nun per preni nur unu karton Ludoviko restos 3 kartoj, kiujn Johano ne povos preni per unu movo laŭ la aldona, limiganta regulo. Do Ludoviko venkos.

Ĉu estas aliaj alternativoj?

Eble vi demandas vin, kio okazos, se Johano faros movon, kiu ne estas laŭ la perfekta strategio. Do la rolojn de la ludantoj inversigas, kaj Ludoviko povas fari movon laŭ la perfekta strategio kaj venkos.

Ekzemple

vico 1: Ludoviko prenas unu karton. Restas 7 kartoj.
vico 2: Johano prenas unu karton. Restas 6 kartoj.
vico 3: Ludoviko ludas laŭ la perfekta strategio kaj prenas 4-1=3 kartojn. Restas 3 kartoj, kaj vi povas vidi, ke iun ajn nombron Johano nun prenos, Ludoviko venkos.

Blua_Monto (Montri la profilon) 2021-marto-16 08:49:31

Tio estas perfekta respondo, tre organizita kaj facile legebla.
Ne, mi ne intencis neperfektan movon. Mi forgesis mencii pri tio…

sergejm (Montri la profilon) 2021-marto-16 14:10:32

Estas erareto en la respondo de Metsis.
Se Ludoviko prenas unu karton kaj Johano tri, tiam Ludoviko prenas unu.
Johano ne povos preni tri pro escepta regulo: li jam prenis tri pasintfoje kaj Ludoviko venkas.

Metsis (Montri la profilon) 2021-marto-17 07:14:53

sergejm:Estas erareto en la respondo de Metsis.
Se Ludoviko prenas unu karton kaj Johano tri, tiam Ludoviko prenas unu.
Johano ne povos preni tri pro escepta regulo: li jam prenis tri pasintfoje kaj Ludoviko venkas.
Bona observo, dankon. Mi korektis mian respondon.

Metsis (Montri la profilon) 2021-marto-17 08:54:11

Mi daŭris pripensi la ludon kaj kreis la decidan arbon, al kiu mi ŝanĝis la nomojn al Sofia resp. Adamo. Vi povas elŝuti la arbon en PDF-formo el mia Dropbox (la elŝutado tuj komencas, ne bezonas registriĝi).

La aldona regulo ŝanĝas la ludon rimarkinde:
 
  • la ludo ne plu estas komplete determinisma, alivorte ne plu estas vojo kun perfektaj movoj, kiuj garantios venkon al iu ajn ludanto
  • ambaŭ ludantoj ne plu havas egalan ŝancon venki, sed la komencanto havas 38 vojojn al venko kontraŭ 35 de la dua ludanto (se mi kalkulis ĝuste)
Mi lasas kiel ekzerco kalkuli la mini-maks -valorojn de la nodoj.

sergejm (Montri la profilon) 2021-marto-17 17:07:26

Vi povas fari simplan memlernantan aŭtomaton por ĉi tiu ludo.
Certe, se vi scipovas programi, vi povas uzi komputilan programon anstataŭe.
Prenu saketoj kun nombroj 1, 2, 3, 3', 4, 4', 5, 5', 6, 7, 8 kaj enmetu en ili ĵetonojn kun numbroj 1, 2 kaj 3. En saketoj 2, 3', 4' kaj 5' metu nur 1 kaj 2, en 1 - nur 1.
Se restas N kartojn kaj vi rajtas preni tri kartojn, uzu saketon N. Se vi ne rajtas preni tri kartojn, uzu saketon N'. Elprenu el la saketo hazardan ĵetonon kaj prenu tiom da kartoj, kiom estas skribita sur la ĵetono. Metu la ĵetonon apud la saketo.
Se vi venkas, metu la ĵetonojn reen en la saketojn kaj aldonu po unu la saman.
Se vi malvenkas, forigu malvenkajn ĵetonojn.

Reen al la supro