---

Her er lige tre opgaver som man kan fornøje sig med i sommervarmen:

Nummer 1) Den er næsten klassisk, og findes i mange varianter: 100
fanger bliver stillet op på en række, og hver af dem får en kasket på,
som er enten sort eller hvid. En fange kan ikke se farven på sin egen
kasket, men kun farven på dem der står foran (dvs. den forreste kan
intet se; fangen bagved kan se farven på den forrestes kasket, og den
bageste kan se de øvrige 99 kasketter). Nu bliver fangerne én efter
én, bageste mand først, spurgt, hvilken farve deres kasket har, og
hvis de svarer rigtigt får de lov og gå; hvis ikke bliver de skudt på
stedet. Man kan antage, at alle de foranstående fanger hører svaret,
og også det evt. efterfølgende skud.

Før alt dette har fangerne lov til at aftale en strategi;
dvs. fangerne ved de bliver stillet op på en række, og at de alle får
en kasket på, og de ved hvad det handler om når de bliver spurgt... De
ved derimod intet om hvilken rækkefølge de kommer til at stå i, og
heller intet om hvor mange sorte og hvide hatte der bliver i
alt. Spørgsmålet er nu: Hvor mange fanger kan _højst_ reddes (med 100%
sikkerhed); dvs. hvad er fangernes optimale strategi?

Nederst har jeg skrevet nogle småting som man nok hurtigt selv finder
ud af, men løsningen kommer senere...


Nummer 2) En del sværere, men til gengæld meget imponerende at udføre
i praksis: Vi har et helt almindeligt sæt af spillekort med 52
kort. To personer, A og B, skal aftale en strategi således, at

- En person C giver A 5 tilfældigt valgte kort fra bunken
- A vælger nu fire af disse kort, som bliver givet en efter en til B
- B skal nu, udelukkende ud fra denne information, kunne fortælle
hvilket kort A sidder tilbage med.

Der behøver selvfølgelig ikke være en person C involveret; hvis man
bare tager de øverste fem kort fra et sæt velblandede kort er det jo
det samme; pointen er blot at den aftalte strategi skal virke _uanset_
hvilke fem kort A får. Det siger sig selv at A ikke må blinke, hoste
eller lign. for at videregive anden information.

For de virkelig hardcore kan man jo spørge, om der er noget specielt
ved 52 kort: Lad os sige vi har en bunke med N kort. For hvor stort et
N findes der en strategi som beskrevet ovenfor (stadig med 4+1 kort
til A). Eksistensen (som jeg indtil videre påstår) af strategien
ovenfor viser at N >= 52, men hvor stor? Man bliver overrasket...


Nummer 3) Knap så svær, meeen...
_____
| |
O _ _ _ | |
/|\ |*| |*| |*| | o|
| |_| |_| |_| | |
/ \ | |

Nå, nok ASCII-grafik. Ovenstående skulle forestille en mand, tre
alm. lyskontakter og en lukket dør. Bag døren (som der ikke kan sive
lys igennem) befinder sig en pære, som er forbundet til én af
kontakterne. Hvis nu vi siger, at manden kun må betjene kontakterne
når døren er lukket, hvordan skal han så finde ud af hvilken af
kontakterne der er sluttet til pæren ved kun at åbne og lukke døren én
gang?


Med venlig hilsen

Rasmus




Ang. fangerne:

Først og fremmest er det klart, at "strategien" bestående i at hver
fange blot siger en tilfældig farve og dermed overlever med 50%
sandsynlig er ret dårlig, for på denne måde vil netop 0 overleve med
100% sandsynlighed. En bedre strategi er, at fangerne rent faktisk
videregiver information. En strategi kunne være, at bageste mand siger
farven på den foranstående kasket; denne vil så med sikkerhed kunne
sige hvilken farve hans kasket har, og dermed redde sig. Det hjælper
dog ikke tredje mand, men han kunne jo så hjælpe fjerde mand og så
fremdeles, så denne strategi redder 50 af fangerne (med sikkerhed;
hver af resten med 50% sandsynlighed). Omvendt kan man sige, at den
bageste mand absoult ikke har nogen information til rådighed, så han
vil, uanset strategi, aldrig kunne reddes med sikkerhed. Der er derfor
et teoretisk maksimum på 99 fanger; det rigtige svar ligger så mellem
50 og 99.

--
http://home.imf.au.dk/burner/
"Jeg er aldrig blevet testet positiv" -- Bjarne Riis, på spørgsmålet
om han nogensinde har taget doping.
(Jeg ku' ik' la' vær', nu når der er Tour igenigen i TV).

---

Rasmus Villemoes skrev:

>Her er lige tre opgaver som man kan fornøje sig med i sommervarmen:

Jeg har nogle forslag til løsninger (brug ROT13):

>Nummer 1) Den er næsten klassisk, og findes i mange varianter: 100
>fanger bliver stillet op på en række, og hver af dem får en kasket på,
>som er enten sort eller hvid.

Snatrear nsgnyre ng ylf fgrzzr orglqre uivq bt zøex fgrzzr
orglqre fbeg. Qre re 50 % punapr sbe ng qra ontrfgr znaq qøe,
erfgra bireyrire sbeqv qr xna fvtr qra evtgvtr sneir bt zrq
fgrzzrserxirafra sbegæyyr aæfgr znaq uinq sneir unaf xnfxrg une.

>Nummer 2) En del sværere, men til gengæld meget imponerende at udføre
>i praksis: Vi har et helt almindeligt sæt af spillekort med 52
>kort. To personer, A og B, skal aftale en strategi

Zna fvtanyrere irq qra zåqr xbegrg iraqre cå: ybqerg, inaqerg bt
gb fxeå cbfvgvbare, bt ovyyrqfvqra bc ryyre arq. Qrg tvire 8
zhyvturqre. Zna xna zrq søefgr xbeg zrqqryr xhyøera bt zrq qr gb
aæfgr hqcrtr iæeqvra: søefgr xbeg tvire 1-8 bt naqrg xbeg 1-5 (6,
7 bt 8 orglqre få 0).

>Nummer 3) Knap så svær, meeen...
>Nå, nok ASCII-grafik. Ovenstående skulle forestille en mand, tre
>alm. lyskontakter og en lukket dør.

Una gvyxnyqre ra uwæycre qre tåe vaq ont qøera bt yhxxre qra.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:

> Rasmus Villemoes skrev:
>
>>Her er lige tre opgaver som man kan fornøje sig med i sommervarmen:
>
> Jeg har nogle forslag til løsninger (brug ROT13):
>
>>Nummer 1) Den er næsten klassisk, og findes i mange varianter: 100
>>fanger bliver stillet op på en række, og hver af dem får en kasket på,
>>som er enten sort eller hvid.
>
> Snatrear nsgnyre ng ylf fgrzzr orglqre uivq bt zøex fgrzzr
> orglqre fbeg. Qre re 50 % punapr sbe ng qra ontrfgr znaq qøe,
> erfgra bireyrire sbeqv qr xna fvtr qra evtgvtr sneir bt zrq
> fgrzzrserxirafra sbegæyyr aæfgr znaq uinq sneir unaf xnfxrg une.
>
>>Nummer 2) En del sværere, men til gengæld meget imponerende at udføre
>>i praksis: Vi har et helt almindeligt sæt af spillekort med 52
>>kort. To personer, A og B, skal aftale en strategi
>
> Zna fvtanyrere irq qra zåqr xbegrg iraqre cå: ybqerg, inaqerg bt
> gb fxeå cbfvgvbare, bt ovyyrqfvqra bc ryyre arq. Qrg tvire 8
> zhyvturqre. Zna xna zrq søefgr xbeg zrqqryr xhyøera bt zrq qr gb
> aæfgr hqcrtr iæeqvra: søefgr xbeg tvire 1-8 bt naqrg xbeg 1-5 (6,
> 7 bt 8 orglqre få 0).
>
>>Nummer 3) Knap så svær, meeen...
>>Nå, nok ASCII-grafik. Ovenstående skulle forestille en mand, tre
>>alm. lyskontakter og en lukket dør.
>
> Una gvyxnyqre ra uwæycre qre tåe vaq ont qøera bt yhxxre qra.
>

Vqrra v 1 re, ng qre vxxr xna ivqrertvirf naqra vasbezngvba raq qra
qre yvttre v qr sneire(*) qr ontirqfgåraqr fntqr, bt erfhygngrear
urens. Qrg re nygfå uryyre vxxr gvyynqg snatrear ng fcnexr qra
sbenafgåraqr v irafger ryyre uøwer xaæunfr ryyre yvtaraqr; ceøi bz qh
xna svaqr ra fgengrtv fbz vxxr oehtre 'vxxr-fgnaqneq' zrgbqre.

Gvyfineraqr v 2 sbeføtgr wrt ng tøer glqryvtg bczæexfbz cå, ng _vatra_
naqra vasbezngvba raq qr sver xbeg bt qra eæxxrsøytr qr oyvire tvirg v
re gvyynqg. Sberfgvy qvt ng N bt O orsvaqre fvt v uireg fvg ehz, bt P
eraqre serz bt gvyontr zryyrz qr gb ehz sbe ng fvxer, ng qre vxxr
falqrf. (Vtra, N bt O une fryisøytryvt vxxr nqtnat gvy zbovygryrsbare
rgp.).

V 3'rera ivy wrt tbqg zrqtvir ng zna vxxr uryg xna xyner qra hqra ng
ivqr zrer bz ireqra raq qre yvtr yvttre sbe uåaqra, zra ng gvyxnyqr ra
uwæycre re abx vxxr uryg npprcgnoryg. Qrfhqra fxhyyr uwæycrera xhaar
eåor erg uøwg uivf una fxhyyr fvtr gvy aåe qra evtgvtr xbagnxg oyri
fyårg gvy. V qra bevtvanyr irefvba re ceboyrzrg snxgvfx ra znaq qre
fgåe arqr v xæyqrera zrq ger yrqavatre; ra ns qvffr re sbeohaqrg gvy
ra cæer cå ybsgrg, bt una fxny svaqr hq ns uivyxra; una une
angheyvtivf vxxr ylfg gvy ng fcæar zrer bc bt arq raq uøwfg
aøqiraqvtg. (Qraar irefvba tnq wrt vxxr grtar v NFPVV-tensvx). Fr
rig. zvg naqrg fine.

Overordnet: Kreative løsningsforslag, men ikke just dem jeg havde i
tankerne. I opgaver som disse hvor det kan være svært helt præcist fra
starten at specificere hvad der er tilladt og hvad der ikke er, er der
sjældent kun én rigtig løsning. Jeg tror dog du vil blive positivt
overrasket over "mine" løsninger.

(*) Her er det ikke meningen der skal opstå en lang diskussion om
hvorvidt sort og hvid er farver eller ej.


Mvh Rasmus

--

---

> Nå, nok ASCII-grafik. Ovenstående skulle forestille en mand, tre
> alm. lyskontakter og en lukket dør. Bag døren (som der ikke kan sive
> lys igennem) befinder sig en pære, som er forbundet til én af
> kontakterne. Hvis nu vi siger, at manden kun må betjene kontakterne
> når døren er lukket, hvordan skal han så finde ud af hvilken af
> kontakterne der er sluttet til pæren ved kun at åbne og lukke døren én
> gang?

Frem for at rotere bertels svar tilbage til læsbar form vil jeg bare komme
med et forslag.
Han tænder kontakt 1 i ti minutter. Slukker den så og tænder kontakt to og
åbner med det samme døren.

Hvis det var kontakt 1 der kontrolerede pæren så er den slukket men varm.
Var det kontakt 2 så er pæren tændt.
Var det kontakt 3 er pæren slukket og kold.

Det forudsætter godt nok at det er en pære som bliver varm, men med
betegnelsen "pære" menes vel en alm glødetrådspære eller ligende og ikke en
diode.

---

"Jakop Nielsen" <jn@home.mail.dk> writes:

[korrekt løsning snippet]
>
> Det forudsætter godt nok at det er en pære som bliver varm, men med
> betegnelsen "pære" menes vel en alm glødetrådspære eller ligende og ikke en
> diode.
>

Jep, den tredje falder lidt uden for kategori, idet den forudsætter at
man ved lidt mere om den virkelige verden end den information man ved
man må bruge.

Mvh Rasmus
--

---

"Rasmus Villemoes" <burner+usenet@imf.au.dk> skrev i en meddelelse news:u0ln0fo328w.fsf@imf.au.dk...
> Her er lige tre opgaver som man kan fornøje sig med i sommervarmen:
>
> Nummer 2) En del sværere, men til gengæld meget imponerende at udføre
> i praksis: Vi har et helt almindeligt sæt af spillekort med 52
> kort. To personer, A og B, skal aftale en strategi således, at
>
Spørgsmålet er om intervallerne de 4 kort udstikker, kan vise hvor
det 5. lå. Mon ikke det kan ske hvis man aftaler at det 5. har ligget
nederst i det højeste interval.

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> Spørgsmålet er om intervallerne de 4 kort udstikker, kan vise hvor
> det 5. lå. Mon ikke det kan ske hvis man aftaler at det 5. har ligget
> nederst i det højeste interval.

Nej. Hvis de fem kort var en toer, en firer, en sekser, en otter og en
tier, så er der ingen af dem der ligger i bunden af noget interval,
afgrænset af de andre. Desuden skal du også gætte kuløren på det femte
kort.

..Henrik

PS: Jeg har en nedre grænse for svaret på Rasmus' spørgsmål om hvor
stort N kan blive, og han har ganske ret i at det kan være lidt
overraskende. (Og den kan findes på nettet, men jeg siger ikke hvor -
endnu i hvert fald).

--
"Gud har skabt de hele tal, alt andet er menneskeværk" - Kronecker
"Gud har 'INTET' skabt. Alt andet er menneskeværk" - Flemming Topsøe

---

"Henrik Christian Grove" <grove@sslug.dk> skrev i en meddelelse news:7gu19w7yfr.fsf@serena.fsr.ku.dk...
> "Martin Larsen" <mlarsen@post7.tele.dk> writes:
>
> > Spørgsmålet er om intervallerne de 4 kort udstikker, kan vise hvor
> > det 5. lå. Mon ikke det kan ske hvis man aftaler at det 5. har ligget
> > nederst i det højeste interval.
>
> Nej. Hvis de fem kort var en toer, en firer, en sekser, en otter og en
> tier, så er der ingen af dem der ligger i bunden af noget interval,
> afgrænset af de andre. Desuden skal du også gætte kuløren på det femte
> kort.
>
Jo, det gør tieren (nederst er jo nederste halvdel). Iøvrigt regner jeg 1-52.

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> skrev i en meddelelse news:begt8b$liq$1@sunsite.dk...
> >
> Jo, det gør tieren (nederst er jo nederste halvdel). Iøvrigt regner jeg 1-52.
>
Jeg skal vist forklare lidt mere præcist for ikke at generere for mange
unødvendige indlæg. Der skulle have stået største og ikke højeste
interval. Intervallet er cirkulært og 4! = 24

Mvh
Martin

---

Henrik Christian Grove <grove@sslug.dk> writes:

> PS: Jeg har en nedre grænse for svaret på Rasmus' spørgsmål om hvor
> stort N kan blive, og han har ganske ret i at det kan være lidt
> overraskende. (Og den kan findes på nettet, men jeg siger ikke hvor -
> endnu i hvert fald).
>

Hmm, jeg gav også en nedre grænse (52), men du har måske en større?
Jeg vil umiddelbart sige, at en _øvre_ grænse er nemmere at
finde. Svar gerne via mail.

Mvh Rasmus

--

---

Rasmus Villemoes <burner+usenet@imf.au.dk> writes:


> Hmm, jeg gav også en nedre grænse (52), men du har måske en større?

En del større, men jeg skal måske lige præcisere, at jeg ikke ved om den
strategi man skal bruge for at nå den grænse jeg taler om, overhovedet
minder om den strategi jeg kender for at løse problemet med 52 kort.

> Jeg vil umiddelbart sige, at en _øvre_ grænse er nemmere at
> finde. Svar gerne via mail.

Jeg har sendt Rasmus en reference til hvor jeg har set korttricket
beskrevet.

I andre skal nok få den senere.

..Henrik

--
Jacob: Because the theoreticians told me.
Prof. Vassilicos: Why do you believe theoreticians?

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>

> Der er derfor et teoretisk maksimum på 99 fanger;

Ontrfgr snatr fvtre "uivq" uivf qre re rg _yvtr_ nagny uivqr unggr
sbena unz. Nyyr qr naqer finere xbeerxg.

--
Henning Makholm "Monsieur, vous êtes fou."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
>
>> Der er derfor et teoretisk maksimum på 99 fanger;
>
> Ontrfgr snatr fvtre "uivq" uivf qre re rg _yvtr_ nagny uivqr unggr
> sbena unz. Nyyr qr naqer finere xbeerxg.
>

Netop. Når man når hertil, er det ikke svært at generalisere
problemet: Hvad er strategien, hvis der er n forskellige farver (vi
kan antage at n ikke er større end at det faktisk er muligt at skelne
farverne med det blotte øje) og N fanger? Kan man så stadig redde de
fleste?

Mvh Rasmus

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>

> Hvad er strategien, hvis der er n forskellige farver (vi
> kan antage at n ikke er større end at det faktisk er muligt at skelne
> farverne med det blotte øje) og N fanger?

Den samme - man skal blot bruge addition modulo n i stedet for xor.

Problemet er bare at strategien ikke længere er robust overfor om en
fange i midten af rækken regner galt (aåe qre xha re gb sneire såe zna
wb shyq ivqra bz qr ontirqfgåraqrf uhre irq ng ylggr rsgre oåqr fine
bt fxhq).

Hvad gør man så ved det? Det der er lettest at huske er nok at aftale
at HVIS en fange som ifølge systemet skulle have været reddet, bliver
skudt, begynder man helt forfra med næste fange som om han var den
bageste. Desværre fører det til at den nye bagmand kan risikere at
skulle sige en farve som han VED han ikke har, og så heroisk er han
nok ikke...

--
Henning Makholm "The great secret, known to internists and
learned early in marriage by internists' wives, but
still hidden from the general public, is that most things get
better by themselves. Most things, in fact, are better by morning."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
>
>> Hvad er strategien, hvis der er n forskellige farver (vi
>> kan antage at n ikke er større end at det faktisk er muligt at skelne
>> farverne med det blotte øje) og N fanger?
>
> Den samme - man skal blot bruge addition modulo n i stedet for xor.
>

Jep.

>
> Problemet er bare at strategien ikke længere er robust overfor om en
>fange i midten af rækken regner galt (aåe qre xha re gb sneire såe
>zna wb shyq ivqra bz qr ontirqfgåraqrf uhre irq ng ylggr rsgre oåqr
>fine bt fxhq).
>

Så har du jo lige selv svaret på dit spørgsmål i det andet indlæg.

>
> Hvad gør man så ved det? Det der er lettest at huske er nok at
>aftale at HVIS en fange som ifølge systemet skulle have været reddet,
>bliver skudt, begynder man helt forfra med næste fange som om han var
>den bageste. Desværre fører det til at den nye bagmand kan risikere
>at skulle sige en farve som han VED han ikke har, og så heroisk er
>han nok ikke...
>

Hvis der er er to farver skal man blot tælle skuddet med, og så kan
alle stadig reddes; hvis der er flere farver kan jeg heller ikke se
der er andet at gøre end at ny bageste mand starter forfra. Men hvis
der har været et skud og der er mere end tre farver kan jeg ikke se
hvorledes han kan være _sikker_ på at den farve han siger ikke er den
rigtige?

/Rasmus

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
> Henning Makholm <henning@makholm.net> writes:

[Fangernes problem for n>2]

> > (aåe qre xha re gb sneire såe zna wb shyq ivqra bz qr ontirqfgåraqrf
> > uhre irq ng ylggr rsgre oåqr fine bt fxhq).

> Så har du jo lige selv svaret på dit spørgsmål i det andet indlæg.

Ja, men det var først senere at jeg kom i tanke om det.

> > Desværre fører det til at den nye bagmand kan risikere at skulle
> > sige en farve som han VED han ikke har, og så heroisk er han nok
> > ikke...

> Men hvis der har været et skud og der er mere end tre farver kan jeg
> ikke se hvorledes han kan være _sikker_ på at den farve han siger
> ikke er den rigtige?

Forestil dig at du er nummer 50 og systemet indtil videre har virket
fint. Fange 48 er lige blevet løsladt, og du har regnet i forvejen
og ved nu at

Hvis nummer 49 er hvid, er du hvid
Hvis nummer 49 er rød, er du blå
Hvis nummer 49 er grøn, er du grøn
Hvis nummer 49 er blå, er du rød

Bagfra hører du nummer 49 sige

øh... mumlemumle, og 2 i mente... årh, fuck... blå?

Men så bliver han skudt! Nu ved du at nummer 49 var enten rød, grøn
eller hvid, så du må være enten blå, grøn eller hvid.

Du er nu ny bagmand, og tæller igen huerne foran dig. De summer sammen
til 69, så det korrekte bagmandssvar for dig er rød. Men rød er den
eneste farve du ved du IKKE har - ellers skulle fangerne 1 til 48 alle
sammen have regnet forkert på samme måde!

Du har nu valget mellem

a) at sige "rød" og ofre livet for de foranstående

b) at skyde vildt på en af de tre andre farver. Så er nummer 51 (som
stoler på dig) dødsens, men du har selv (subjektivt) 33% chance
for at overleve - måske lidt større hvis du har lagt mærke til at
der synes at være flest blå huer.

--
Henning Makholm "Det er jo svært at vide noget når man ikke ved det, ikke?"

---

Henning Makholm skrev:

>Ontrfgr snatr fvtre "uivq" uivf qre re rg _yvtr_ nagny uivqr unggr
>sbena unz. Nyyr qr naqer finere xbeerxg.

Jeg forstår det ikke, og mon ikke vi kan snakke klar tekst nu?

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

"Bertel Lund Hansen" <nospamfor@lundhansen.dk> skrev i en meddelelse news:q4oogvc0mspnc4f9351de6uo8cp6gl2huh@news.stofanet.dk...
> Henning Makholm skrev:
>
> >Ontrfgr snatr fvtre "uivq" uivf qre re rg _yvtr_ nagny uivqr unggr
> >sbena unz. Nyyr qr naqer finere xbeerxg.
>
> Jeg forstår det ikke, og mon ikke vi kan snakke klar tekst nu?
>
Den næste mand kan regne ud om hans hat er hvid ved at se om
der er et lige eller ulige antal hatte foran ham. Hvis den første
sagde hvid, og den næste ser et lige antal hvide hatte, må hans
hat være sort.

Mvh
Martin

---

Scripsit Bertel Lund Hansen <nospamfor@lundhansen.dk>
> Henning Makholm skrev:

> >Ontrfgr snatr fvtre "uivq" uivf qre re rg _yvtr_ nagny uivqr unggr
> >sbena unz. Nyyr qr naqer finere xbeerxg.

> Jeg forstår det ikke, og mon ikke vi kan snakke klar tekst nu?

Her er en anden forklaring end Martins:

Vi ser helt bort fra fange nummer 1's hat. Men enhver anden fange
ved, når det bliver hans tur:

a) Om der er et lige eller ulige antal hvide hatte blandt nummer 2
til 100.
b) Farverne på alle hatte *foran* ham (for dem kan han se).
c) Farverne på alle hatte *bag* ham (for han har hørt godt efter).

Fra (b) og (c) kender han alle andre hatte end sin egen, og kan derfor
regne ud om hans egen skal være hvid for at få oplysning (a) til at
stemme.

Resultat: Alle andre end første fange overlever med sikkerhed,
medmindre nogen kludrer i systemet.

--
Henning Makholm "Ambiguous cases are defined as those for which the
compiler being used finds a legitimate interpretation
which is different from that which the user had in mind."

---

Henning Makholm <henning@makholm.net> writes:

>
> øh... mumlemumle, og 2 i mente... årh, fuck... blå?
>

That's a good vending; maybe I can use that in another usenet-indlæg!

Har du noget imod jeg smider den på min citatside
(home.imf.au.dk/burner/citat.xhtml), enten tilskrevet dig eller det
mystiske "Fange nr. 49"? Undskyld det store OT-spring.

Mvh Rasmus

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
> Henning Makholm <henning@makholm.net> writes:

> > øh... mumlemumle, og 2 i mente... årh, fuck... blå?

> Har du noget imod jeg smider den på min citatside
> (home.imf.au.dk/burner/citat.xhtml), enten tilskrevet dig eller det
> mystiske "Fange nr. 49"? Undskyld det store OT-spring.

For min skyld ingen alarm. Jeg tror ikke den er lang nok til at at
være ophavsretsbeskyttet, og over halvdelen er alligevel tyvstjålet
fra politimester Bastian...

--
Henning Makholm "We will discuss your youth another time."

---

Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

> Her er lige tre opgaver som man kan fornøje sig med i sommervarmen:
>
> Nummer 1) Den er næsten klassisk, og findes i mange varianter: 100
> fanger bliver stillet op på en række, og hver af dem får en kasket på,
> som er enten sort eller hvid.
....
> Man kan antage, at alle de foranstående fanger hører svaret,
> og også det evt. efterfølgende skud.

luftballons!

> Nummer 2) En del sværere, men til gengæld meget imponerende at udføre
> i praksis: Vi har et helt almindeligt sæt af spillekort med 52
> kort. To personer, A og B, skal aftale en strategi således, at
>
> - En person C giver A 5 tilfældigt valgte kort fra bunken
> - A vælger nu fire af disse kort, som bliver givet en efter en til B
> - B skal nu, udelukkende ud fra denne information, kunne fortælle
> hvilket kort A sidder tilbage med.

Den er sværere!

> Nummer 3) Knap så svær, meeen...
> _____
> | |
> O _ _ _ | |
> /|\ |*| |*| |*| | o|
> | |_| |_| |_| | |
> / \ | |

Er det en glødepære?

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
Art D'HTML: <URL:http://www.infimum.dk/HTML/randomArtSplit.html>
'Faith without judgement merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen <lrn@hotpop.com> writes:

>
> luftballons!
>

Ja, og hvis der var 1002 fanger kunne man sige "nats eventyr".

> Er det en glødepære?
>

Ja. Opgaven er vistnok noget ældre end de hersens moderne sparepærer.

Mvh Rasmus

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>

> Man kan antage, at alle de foranstående fanger hører svaret,
> og også det evt. efterfølgende skud.

Hm, kan man overhovedet udnytte muligheden for at høre det eventuelle
skud til noget?

--
Henning Makholm "I have seen men with a *fraction* of
your trauma pray to their deity for death's
release. And when death doesn't arrive immediately,
they reject their deity and begin to beg to another."

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>

> - En person C giver A 5 tilfældigt valgte kort fra bunken
> - A vælger nu fire af disse kort, som bliver givet en efter en til B
> - B skal nu, udelukkende ud fra denne information, kunne fortælle
> hvilket kort A sidder tilbage med.

Følgende er temmelig indviklet, men det bedste jeg lige kan finde på:

Når A har bestemt *hvilke* kort han vil give B, kan han vælge mellem
24 forskellige *rækkefølger* at give disse kort. På en passende måde
kan man aftale en oversættelse fra et tal k mellem 1 og 24 til en
rækkefølge af fire kort (i forhold til at give dem i en eller anden
aftalt stigende orden).

Hvilke kort A vælger afhænger af farvefordelingen blandt hans fem
kort:

a) Alle fem kort har samme farve. A vælger at beholde et vilkårligt
af kortene og signalerer dets valør som k.

b) Der er kort af netop to farver blandt kortene, fx Hj,Hj,Hj,Sp,Sp
eller Hj,Hj,Hj,Hj,Sp.
A videregiver de tre højeste Hj og den højeste Sp.
Tallet k vælges som nummeret på det skjulte kort i rækkefølgen
Hj1,Hj2,...,Hj10,Sp1,...,SpD

c) Der er kort af tre farver blandt kortene, og den ene farve
forekommer tre gange, fx Hj,Hj,Hj,Sp,Kl.
A videregiver de to højeste Hj samt Sp og Kl.
Tallet k vælges som 13 + valøren af det skjulte kort
(14<=k<=24 idet det skjulte kort ikke kan være en dame eller konge)

d) Der er kort af tre farver, hvor af to forekommer to gange, fx
Hj,Hj,Sp,Sp,Kl.
d1) Hvis den enlige Kl *ikke* er en konge, beholder A den, og
signalerer k som nummeret på det skjulte kort i rækkefølgen
Kl1, Kl2, ... KlD, Ru1, Ru2, ... RuD
(hvor man i forvejen har aftalt hvilken rækkefølge man tager
de to farver i dette tilfælde)
d2) Hvis den enlige Kl *er* en konge, beholder A i stedet den
højeste Hj (eller Sp) og videregiver Hj,Sp,Sp,KlK. I så fald
vælges k som valøren af det skjulte kort.

e) Der er kort af alle fire farver, fx Hj,Hj,Sp,Kl,Ru. A vælger
at beholde en af singletonerne, således at de to singletoner
B får, enten begge er konger eller ingen af dem er. Så signaleres
k som valøren af det skjulte kort.

Når B skal afkode beskeden, er der følgende muligheder:

*) Alle fire B-kort har samme farve.
Så er vi i tilfælde (a) og alt er let.

*) Tre af kortene har samme farve, men det fjerde har en anden.
Så er vi i tilfælde (b).

*) De fire kort har samme farve to og to.
Så er vi i tilfælde (d1).

*) Der er to kort af samme farve og to singletons.
Hvis k >= 14, er vi i tilfælde (c), og det skjulte kort har samme
farve som de to partnere i Bs hånd.
Ellers: Hvis netop én af singletonerne er en konge, er vi i
tilfælde (d2). Det skjulte kort har valør k og farve som det af
de enlige kort der ikke er en konge.
Ellers er vi i tilfælde (e). Det skjulte kort har valør k og den
farve der ikke er repræsenteret i Bs hånd.

Det kan nu sikkert gøres lettere...

> For de virkelig hardcore kan man jo spørge, om der er noget specielt
> ved 52 kort: Lad os sige vi har en bunke med N kort. For hvor stort et
> N findes der en strategi som beskrevet ovenfor (stadig med 4+1 kort
> til A). Eksistensen (som jeg indtil videre påstår) af strategien
> ovenfor viser at N >= 52, men hvor stor? Man bliver overrasket...

Tja, der ser umiddelbart ud til at være en del ubrugt plads i skemaet
ovenfor. Det ser umiddelbart ud som om man godt kan pusle ihvertfald
én joker med, men så begynder det at blive rigtig svært at huske
systemet. Mon overraskelsen er at man kan nå op på meget store N?

--
Henning Makholm "Uh ... a picture of me with my hair pinned up
in a towel and standing in front of a grid without a
trace of makeup? *Are you out of your rock-happy mind?*"

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
>
> > - En person C giver A 5 tilfældigt valgte kort fra bunken
> > - A vælger nu fire af disse kort, som bliver givet en efter en til B
> > - B skal nu, udelukkende ud fra denne information, kunne fortælle
> > hvilket kort A sidder tilbage med.
>
> Følgende er temmelig indviklet, men det bedste jeg lige kan finde på:

Det er unødvendigt indviklet.

Jeg vil give et vink, til en mulig løsning. Med 5 kort vil der altid
mindst to af samme kulør. Det ene (men hvilket?) af disse vælger A at
beholde på hånden, det andet lægger han ned som det første, og har
dermed signaleret kuløren på det kort han holder tilbage (men også lidt
mere end det).

> Når A har bestemt *hvilke* kort han vil give B, kan han vælge mellem
> 24 forskellige *rækkefølger* at give disse kort. På en passende måde
> kan man aftale en oversættelse fra et tal k mellem 1 og 24 til en
> rækkefølge af fire kort (i forhold til at give dem i en eller anden
> aftalt stigende orden).

Du er på sporet af noget brugbart.

> > For de virkelig hardcore kan man jo spørge, om der er noget specielt
> > ved 52 kort: Lad os sige vi har en bunke med N kort. For hvor stort et
> > N findes der en strategi som beskrevet ovenfor (stadig med 4+1 kort
> > til A). Eksistensen (som jeg indtil videre påstår) af strategien
> > ovenfor viser at N >= 52, men hvor stor? Man bliver overrasket...
>
> Tja, der ser umiddelbart ud til at være en del ubrugt plads i skemaet
> ovenfor. Det ser umiddelbart ud som om man godt kan pusle ihvertfald
> én joker med, men så begynder det at blive rigtig svært at huske
> systemet. Mon overraskelsen er at man kan nå op på meget store N?

Jeg må heller lige indrømme at jeg ikke kan læse, det tal jeg talte om
tidligere er en øvre grænse for N, men den er stadigvæk en del større
end 52. Den strategi jeg har givet et vink til, virker dog ikke med mere
end 52 kort.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Scripsit Henrik Christian Grove <grove@sslug.dk>
> Henning Makholm <henning@makholm.net> writes:

> > Følgende er temmelig indviklet, men det bedste jeg lige kan finde på:

> Det er unødvendigt indviklet.

Det tænkte jeg nok

> Jeg vil give et vink, til en mulig løsning. Med 5 kort vil der altid
> mindst to af samme kulør. Det ene (men hvilket?) af disse vælger A at
> beholde på hånden, det andet lægger han ned som det første, og har
> dermed signaleret kuløren på det kort han holder tilbage (men også lidt
> mere end det).

Årh, ja selvfølgelig. Forskellen mellem de to korts valør er et eller
andet tal modulo 13. Ved om nødvendigt at bytte om på kortene kan man
opnå at afstanden er mellem 1 og 6 (inklusive), idet 7 til 12 er lig
-6 til -1 modulo 13. Den søgte afstand kan man så passende signalere
ved hjælp af den indbyrdes rækkefølge af de tre sidste kort.

Let nok når først man tør stole på at dit vink ovenfor kan lykkes (det
var et af mine første forsøg, men jeg opgav det for hurtigt fordi jeg
ikke i første omgang mente at 3!=6 muligheder var information nok til
at vælge blandt de 12 mulige kort i farven).

> Jeg må heller lige indrømme at jeg ikke kan læse, det tal jeg talte om
> tidligere er en øvre grænse for N, men den er stadigvæk en del større
> end 52.

For at der er noget håb overhovedet skal der jo tydeligvis (ved et
rent tælleargument) gælde at

N!/(N-4)! >= K(N,5)

<=> N(N-1)(N-2)(N-3) >= N(N-1)(N-2)(N-3)(N-4)/120

<=> 120 >= N-4

så 124 er et hårdt maksimum. Men deraf følger der jo ingenlunde at der
faktisk findes en strategi for 124 kort. Umiddelbart synes jeg det
virker intuitivt sandsynligt på grund af symmetrien i problemet, men
derfra til en konkret konstruktion er der jo et stykke vej.

[Hm, det var sjovt nok også hvad der stod i decembernummeret af Famøs
- som jeg med skam at melde først nu fandt, da jeg forsøgte at google
lidt efter videre spor...

[Endnu mere sjovt nok var det jeg googlede efter faktisk "Bernstein
Topsøe site:www.math.ku.dk", fordi jeg et kort øjeblik havde en
forvirret ide om at man kunne bruge ækvivalenssætningen til et
ikke-konstruktivt eksistensbevis (nej, det kan man ikke) og lige ville
tjekke om der ikke hænger en anden guts efternavn (Cantor? Skolem?)
på sætningen også. Det Famøsnummer hvor opgaven blev gennemgået
dukkede så op helt af sig selv, fordi Topsøe var eksempel i en artikel
om anagrammer og Bernstein har rund førdselsdag i 2006. Verden er
lille...]]

> Den strategi jeg har givet et vink til, virker dog ikke med mere end
> 52 kort.

Måske ville det skabe mere indsigt at prøve at konstruere eksplicitte
strategier for det maksimale N for mindre værdier af 5? Med fx 3 kort
(hvoraf 2 gives videre) giver tælleargumentet N<=8; det burde være
lettere at overskue og evt søge brutalt med en computer.

--
Henning Makholm "Vi skal nok ikke begynde at undervise hinanden i
den store regnekunst her, men jeg vil foreslå, at vi fra
Kulturministeriets side sørger for at fremsende tallene og også
give en beskrivelse af, hvordan man læser tallene. Tak for i dag!"

---

Scripsit Henning Makholm <henning@makholm.net>

> så 124 er et hårdt maksimum. Men deraf følger der jo ingenlunde at der
> faktisk findes en strategi for 124 kort. Umiddelbart synes jeg det
> virker intuitivt sandsynligt på grund af symmetrien i problemet, men
> derfra til en konkret konstruktion er der jo et stykke vej.

OK, nu har jeg et eksistensbevis for at der altid er strategier med
det antal kort tælleargumentet giver (også for andre værdier af 5, fx
725 kort hvor der gives 6 kort i første omgang eller 5046 kort hvor
der gives 7 i første omgang). Det er ikke videre konstruktivt, og det
er langt over min sengetid, så jeg vil ikke skrive detaljer ned nu,
men den rigtige symmetriegenskab er

LEMMA: Enhver endelig regulær bipartit graf kan udtyndes til en bijektion.

Bevishint til lemmaet: Betragt det som et flowmaksimeringsproblem.
(Det var ihvertfald hvad der fik det til at falde i hak for mig.
Senere fik jeg simplificeret ideen til et mere direkte bevis).
Mere i morgen. Måske.

--
Henning Makholm "Nej, hvor er vi altså heldige! Længe
leve vor Buxgører Sansibar Bastelvel!"

---

Henning Makholm <henning@makholm.net> writes:

> LEMMA: Enhver endelig regulær bipartit graf kan udtyndes til en bijektion.

Det kommer an på hvordan man definerer tvedelt (det normale danske ord
for bipartite). I "Discrete Mathematics for new technology"
(DisMat-bogen af Garnier og Taylor, hvis det siger nogen noget),
defineres:

A *bipartite graph* is a graph where the vertex set has a partition
{V_1,V_2} such that every edge joins a vertex of V_1 to a vertex of
V_2.

Det betyder at følgende graf er tvedelt:

*---*

* *

(der er endda 4 måder at lave V_1 og V_2 på).

Hvis du tilføjer sammenhængende (enten til forudsætningerne eller til
definitionen af tvedelt), begynder jeg at tro på lemmaet.

> Bevishint til lemmaet: Betragt det som et flowmaksimeringsproblem.
> (Det var ihvertfald hvad der fik det til at falde i hak for mig.
> Senere fik jeg simplificeret ideen til et mere direkte bevis).
> Mere i morgen. Måske.

Jeg vil tænke lidt over det, men glæder mig ellers til at se mere.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Henrik Christian Grove <grove@sslug.dk> writes:

> Hvis du tilføjer sammenhængende (enten til forudsætningerne eller til
> definitionen af tvedelt), begynder jeg at tro på lemmaet.

Men det er jo et alt, alt for skarpt krav. Det må være nok at alle
knuder er forbundne med mindst én anden knude.

..Henrik

--
Jacob: Because the theoreticians told me.
Prof. Vassilicos: Why do you believe theoreticians?

---

Scripsit Henrik Christian Grove <grove@sslug.dk>
> Henrik Christian Grove <grove@sslug.dk> writes:

> > Hvis du tilføjer sammenhængende (enten til forudsætningerne eller til
> > definitionen af tvedelt), begynder jeg at tro på lemmaet.

> Men det er jo et alt, alt for skarpt krav. Det må være nok at alle
> knuder er forbundne med mindst én anden knude.

Ja, og så skal den også være regulær (alle knuder har samme
grad). Ellers kan man komme ud for

* * *
|\ \ |
| \ \|
* * *

som det ikke er let at udtynde til en bijektion. Dit modeksempel viste
at særtilfældet "0-regulær" nok også skal undtages.

--
Henning Makholm "De kan rejse hid og did i verden nok så flot
Og er helt fortrolig med alverdens militær"

---

Scripsit Henrik Christian Grove <grove@sslug.dk>
> Henning Makholm <henning@makholm.net> writes:

> > LEMMA: Enhver endelig regulær bipartit graf kan udtyndes til en bijektion.

> Det kommer an på hvordan man definerer tvedelt (det normale danske ord
> for bipartite).

Det ord overvejede jeg også, men umiddelbart syntes jeg mere at det
antød at grafen havde netop to sammenhængskomponenter. Det begreb vi
her snakker om, er naturligvis ulige mere nyttigt, så hvis du siger at
det er normalt på dansk, tror jeg på dig.

Nå, men jeg skylder et bevis -- det kan nu læses på
http://www.diku.dk/~makholm/misc/korttrick.pdf

> > Bevishint til lemmaet: Betragt det som et flowmaksimeringsproblem.

Ved fornyet googling viser det sig at problemet kaldes "matching" og
er et af de klassiske områder af grafteori. Forbindelsen til
flowmaksimering er velkendt og mit lemma tilskrives Denes König (1916).

--
Henning Makholm "Nemo enim fere saltat sobrius, nisi forte insanit."

---

Henning Makholm <henning@makholm.net> writes:

> [Hm, det var sjovt nok også hvad der stod i decembernummeret af Famøs
> - som jeg med skam at melde først nu fandt, da jeg forsøgte at google
> lidt efter videre spor...

Og det var præcis hvor jeg kendte opgaven fra.

> [Endnu mere sjovt nok var det jeg googlede efter faktisk "Bernstein
> Topsøe site:www.math.ku.dk", fordi jeg et kort øjeblik havde en
> forvirret ide om at man kunne bruge ækvivalenssætningen til et
> ikke-konstruktivt eksistensbevis (nej, det kan man ikke) og lige ville
> tjekke om der ikke hænger en anden guts efternavn (Cantor? Skolem?)

I Bergs 3GT-noter hedder den "Felix Bernsteins Ækvivalenssætning", og
det gør den også der hvor jeg lige fandt den i Topsøes MatY-noter, men
jeg mener Topsøe kaldte den "Schröder-Bernsteins Ækvivalens sætning".

> Måske ville det skabe mere indsigt at prøve at konstruere eksplicitte
> strategier for det maksimale N for mindre værdier af 5? Med fx 3 kort
> (hvoraf 2 gives videre) giver tælleargumentet N<=8; det burde være
> lettere at overskue og evt søge brutalt med en computer.

I Famøs-artiklen skriver Mikkel at han uden større besvær kunne lave
eksplicitte strategier for 1, 2 og 3.

Og til dem der ikke ved hvor de finder Famøs:
http://www.math.ku.dk/famos/16-2/alt.ps
eller
http://www.math.ku.dk/famos/16-2/alt.pdf

..Henrik

--
"The ultimate goal of mathematics is to eliminate all need for
intelligent though" - Graffiti af ukendt i 'Concrete Mathematics'

---

"Henrik Christian Grove" <grove@sslug.dk> skrev i en meddelelse news:7g7k6r8h8p.fsf@serena.fsr.ku.dk...
>
> Jeg vil give et vink, til en mulig løsning.

Hm, jeg kommer nu i tvivl om du forstod min løsning som jo
var ret nem at forklare, men som kræver lidt regnearbejde af
udøverne. Desværre også en "stram" løsning, men den kan måske
ved et lidt mere kompliceret valg af intervaller udvides til ca 75
kort.

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> "Henrik Christian Grove" <grove@sslug.dk> skrev i en meddelelse news:7g7k6r8h8p.fsf@serena.fsr.ku.dk...
> >
> > Jeg vil give et vink, til en mulig løsning.
>
> Hm, jeg kommer nu i tvivl om du forstod min løsning som jo
> var ret nem at forklare,

Det har du ganske ret i at jeg ikke har. Du gav alt for få detaljer til
at jeg gad beskæftige mig mere med den.

> men som kræver lidt regnearbejde af
> udøverne.

Det gør den løsning Rasmus og Henning har præsenteret (og jeg har talt
om) også.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

"Henrik Christian Grove" <grove@sslug.dk> skrev i en meddelelse news:7ghe5u7nej.fsf@serena.fsr.ku.dk...
> "Martin Larsen" <mlarsen@post7.tele.dk> writes:
>
> > Hm, jeg kommer nu i tvivl om du forstod min løsning som jo
> > var ret nem at forklare,
>
> Det har du ganske ret i at jeg ikke har. Du gav alt for få detaljer til
> at jeg gad beskæftige mig mere med den.
>
Du milde.
Der er nogle der kun vil have hints til de afgørende punkter, og så
er der dem der vil have alle detaljer.

Vi har selvfølgelig informationen 4!=24, altså et tal mellem 1 og 24,
konventionelt kaldet k, hvilket er for lidt til at angive et tal mellem 1
og 48 (ikke 52, overvej selv). Der mangler 1 bit

I det følgende anvendes et cirkulært interval, hvilket blot betyder at
vi fortsætter vi med 1, når vi kommer til 52.

A finder nu største interval mellem de 5 kort og kortet i bunden af
dette interval holdes tilbage. Intervallet er nu stadig det største, da
det herved blev endnu større.

B finder nu dette interval og lægger k til.

Hvorfor der højest bliver brug for at lægge 24 til, giver for meget
ævle bævle for min smag. Men det er ganske nemt at tænke igennem.

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> Hvorfor der højest bliver brug for at lægge 24 til, giver for meget
> ævle bævle for min smag. Men det er ganske nemt at tænke igennem.

Det er ikke så slemt.
A har fem tal, ordnet i det cykliske interval [1-52].
Vi vælger et af de fem tal med maksimal afstand til det næste af dem.

Vi ser så på dets afstand til det foregående tal. Hvis den afstand
er 25 eller derover (mindst 24 elementer imellem), så er der også
mindst 24 elementer imellem det valgte tal og det næste.

Hvis vi fjerner det valgte tal, så har vi tilbage et hul mellem det
foregående og det næste tal af længde mindst 49.

Det er en modstrid med at der kun mangler 48 tal.


Til gengæld kan man se at 52 kort er det maksimale antal denne strategi
virker med.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
Art D'HTML: <URL:http://www.infimum.dk/HTML/randomArtSplit.html>
'Faith without judgement merely degrades the spirit divine.'

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> Du milde.
> Der er nogle der kun vil have hints til de afgørende punkter, og så
> er der dem der vil have alle detaljer.

Jeg har ikke brug for alle detaljer, bare så mange at jeg kan forstå
hvad du mener. I første omgang talte du om at ligge nederst i et
interval, så gav jeg et eksempel der viste at det ikke gav mening. Så
"præcisere" du at du bare mente nederste halvdel, uden at sige noget om
hvordan du ville afgøre præcis hvilket kort i dette interval der var
tale om. Det er altså ikke nok til mig.

> I det følgende anvendes et cirkulært interval, hvilket blot betyder at
> vi fortsætter vi med 1, når vi kommer til 52.
>
> A finder nu største interval mellem de 5 kort og kortet i bunden af
> dette interval holdes tilbage. Intervallet er nu stadig det største, da
> det herved blev endnu større.
>
> B finder nu dette interval og lægger k til.

Det kommer til at virke, ja. Princippet er dog præcis det samme som i
den anden løsning, det kræver bare mere at gennemføre tricket på denne
måde.

..Henrik

--
"The ultimate goal of mathematics is to eliminate all need for
intelligent though" - Graffiti af ukendt i 'Concrete Mathematics'

---

Scripsit "Martin Larsen" <mlarsen@post7.tele.dk>

> A finder nu største interval mellem de 5 kort og kortet i bunden af
> dette interval holdes tilbage. Intervallet er nu stadig det største, da
> det herved blev endnu større.

Ah.. smart!

--
Henning Makholm "Ligger Öresund stadig i Middelfart?"

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
>
>> - En person C giver A 5 tilfældigt valgte kort fra bunken
>> - A vælger nu fire af disse kort, som bliver givet en efter en til B
>> - B skal nu, udelukkende ud fra denne information, kunne fortælle
>> hvilket kort A sidder tilbage med.
>
> Følgende er temmelig indviklet, men det bedste jeg lige kan finde på:
>
[snip]
>
> Det kan nu sikkert gøres lettere...
>

Ja, nu tror jeg det må være på tide at afsløre hvad jeg havde i
tankerne. Jeg har ikke tjekket Hennings forslag igennem, men det er
sikkert korrekt.

Først indfører vi lige noget notation; i mangel af de rigtige symboler
vil H betyde hjerter, K klør, S spar og R ruder, og et spillekort vil
blive refereret til som fx H12 (hjerter dame).

Første observation man skal gøre sig er, at blandt fem givne
spillekort vil der være to som har samme farve(*). Med, lad os sige,
det første af de fire kort kan vi altså meddele B hvilken farve det
tilbageholdte kort har (bemærk her at vi har 2 af samme farve, så vi
kan vælge hvilket af de to vi giver, og hvilket vi beholder; dette
bliver vigtigt!). Når vi har valgt to kort af samme farve, og lagt os
fast på hvilket vi beholder og hvilket vi giver som det første, har vi
tre kort tilbage, som skal gives til B i en eller anden
rækkefølge. Med disse kort skal vi fortælle B hvilke af de 12
tilbageværende muligheder der er tale om (B ved jo det ikke er det
13'e i farven...). Lad os sige, at A og B har aftalt en totalordning
på de 52 kort, fx denne

H1 < H2 < ... < H13 < K1 < ... < K13 < S1 < ... < S13 < R1 < ... < R13

Lad os yderligere sige, at de har aftalt en ordning på S_3 (gruppen af
permutationer af en mængde af tre elementer, som her hedder l, m og
s ['lille', 'mellem', 'stor']), fx

(l)(m)(s) = Id < (lm)(s) < (ls)(m) < (l)(ms) < (lms) < (lsm)

Folk der ikke er bekendt med algebra får lige en kortfattet
forklaring: En 'permutation' af et antal elementer er en ombytning af
den rækkefølge de står i; fx er 23154 en permutation af
12345. Permutationerne af lms er altså de seks rækkefølger

1 lms
2 mls
3 sml
4 lsm
5 msl
6 slm

Tallene har jeg tilføjet med henblik på nedenstående. Når vi giver de
tre resterende kort, kan B kalde et af disse kort for "l", et andet
for "m" og det sidste for "s"; alt efter hvilket der er mindst,
mellemst og størst i henhold til den aftalte totalordning. Men så kan
B ud fra rækkefølgen han modtog kortene i derudfra finde ud af,
hvilket af tallene 1-6 A vil meddele ham; hvis fx B modtog det mindst
først, derefter det største og til sidst det mellemste, har vi
permutationen lsm, og dermed tallet 4. Nu tager B så talværdien af det
først modtagne kort, og hertil lægger han det tal han lige har regnet
ud (hvis han får mere end 13 trækker han 13 fra). Det tal B så når
frem til er talværdien af det kort som A sidder med, og farven kender
B fra det første kort. Her ser vi grunden til, at A skal vælge ét
fremfor et andet af de to kort med ens farve; han skal nemlig vælge at
sidde tilbage med et kort, så man ved at lægge højst 6 til det han
giver væk, får tilværdien af det han beholder (hvilket naturligvis
altid kan lade sig gøre når der er 13 kort i en farve).

Et eksempel er nok på sin plads nu:

Lad os sige A får kortene

K7 K12 H2 R9 S5

Den eneste farve som A har to af er klør. A vælger at beholde klør
dame, fordi man ved at lægge 5 til 7 får 12. Det første kort han giver
til B er altså klør 7. Med de resterende kort, H2, R9 og S5 skal A
altså nu meddele B tallet 5. Først skal vi finde ud af hvad der er
mindst og størst af disse. Da den vedtagne ordning på de 52 kort
foreskriver at hjerter altid er mindre end de andre farver, og ruder
er størst, får vi i dette tilfælde at

l = H2
m = S5
s = R9

Tallet 5 meddeles ved at give disse kort i rækkefølgen msl; altså
får B S5 som det andet kort, R9 som det tredje kort og H2 som det
fjerde og sidste kort.

B husker på den rækkefølge han fik de tre sidste kort i, og kan altså
nu rekonstruere A's tankegang, dvs. finde ud af hvad der er l, m og s,
finde det relevante tal, og stolt proklamere at A sidder tilbage med
Klør Dame.

Umiddelbart, synes jeg, er det utroligt at det virker for netop 52
spillekort; hvis man kigger lidt på strategien bygger den netop på den
fantastiske ligning

52 - 4 = 48 = 4·2·6

(4-tallet kommer fra, at vi med det første kort kan meddele hvilken af
4 farver der er tale om; 2-tallet kommer fra at vi har to
frihedsgrader i valget af meddelerkort/beholdt kort, og 6-tallet
kommer simpelthen fra antal elementer i S_3).


(*) Jeg bruger 'farve' om de fire H, K, S og R; de to typer rød og
sort kalder jeg kulører. Er det den korrekte terminologi, eller hvad
er det korrekte danske ord for "suit"?

>
>> For de virkelig hardcore kan man jo spørge, om der er noget specielt
>> ved 52 kort: Lad os sige vi har en bunke med N kort. For hvor stort et
>> N findes der en strategi som beskrevet ovenfor (stadig med 4+1 kort
>> til A). Eksistensen (som jeg indtil videre påstår) af strategien
>> ovenfor viser at N >= 52, men hvor stor? Man bliver overrasket...
>
> Tja, der ser umiddelbart ud til at være en del ubrugt plads i skemaet
> ovenfor. Det ser umiddelbart ud som om man godt kan pusle ihvertfald
> én joker med, men så begynder det at blive rigtig svært at huske
> systemet. Mon overraskelsen er at man kan nå op på meget store N?
>

I den løsning jeg beskriver ovenfor er der også i visse tilfælde noget
redundans (når der er 2 farver hvor der er mere end et kort, og når
der er mere end 2 kort af én farve). Der er absolut plads til
"forbedringer". Dog indser man let at 124 er den maksimale størrelse
for kortbunken (givet fem kort kan man vælge 120 måder at behandle dem
på, og da B kan udelukke 4 af de N forskellige kort, kan der ikke være
mere end 120+4 kort i bunken). Overraskelsen består i, at der faktisk
findes en strategi der virker for 124 kort, men jeg har aldrig set den
beskrevet.

Med venlig hilsen

Rasmus

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>

> Dog indser man let at 124 er den maksimale størrelse for kortbunken
> (givet fem kort kan man vælge 120 måder at behandle dem på, og da B
> kan udelukke 4 af de N forskellige kort, kan der ikke være mere end
> 120+4 kort i bunken).

Jeg er enig i facit, men kan ikke gennemskue dit argument. Gider du
uddybe?

--
Henning Makholm "The compile-time type checker for this
language has proved to be a valuable filter which
traps a significant proportion of programming errors."

---

Henning Makholm skrev:

>> Dog indser man let at 124 er den maksimale størrelse for kortbunken
>> (givet fem kort kan man vælge 120 måder at behandle dem på, og da B
>> kan udelukke 4 af de N forskellige kort, kan der ikke være mere end
>> 120+4 kort i bunken).

>Jeg er enig i facit, men kan ikke gennemskue dit argument. Gider du
>uddybe?

Hvis ikke jeg tager fejl, har jeg gennemskuet Rasmus' ræsonnement
*samt* fundet en strategi for 124 kort.

120 er naturligvis 5!. Hvis man ordner permutationerne af 5 kort
i rækkefølge, kan man altså meddele 120 forskellige talværdier.
Hvis vi tænker os et kortspil med 124 kort i 4 kulører,
nummererer man dem bare fra 1 til 124: 1-31 er klør, 32-62 er
ruder, 63-93 er hjerter og 94-124 er spar.

Når man skal meddele B nummeret, springer man bare over de kort
han skal have.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Rasmus Villemoes skrev:

>(*) Jeg bruger 'farve' om de fire H, K, S og R; de to typer rød og
>sort kalder jeg kulører. Er det den korrekte terminologi, eller hvad
>er det korrekte danske ord for "suit"?

Et kortspil har kort i fire kulører og to farver. Du kan huske
det på at der er noget der hedder "kulørsvigt" (ikke
"farvesvigt").

(Bridgespillere vil sætte pris på at man rangerer kulørerne fra
mindst mod størst: klør, ruder, hjerter, spar)

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

> Ja, nu tror jeg det må være på tide at afsløre hvad jeg havde i
> tankerne. Jeg har ikke tjekket Hennings forslag igennem, men det er
> sikkert korrekt.

Bortset fra at Henning er mindre eksplicit med hensyn til hvordan man
signaler de 6 muligheder med tre kort, er det præcis samme strategi.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Scripsit Henrik Christian Grove <grove@sslug.dk>
> Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

> > Jeg har ikke tjekket Hennings forslag igennem, men det er
> > sikkert korrekt.

> Bortset fra at Henning er mindre eksplicit med hensyn til hvordan man
> signaler de 6 muligheder med tre kort, er det præcis samme strategi.

Det var vist min første, meget indviklede, løsning Rasmus udtalte sig
om her.

--
Henning Makholm "We will discuss your youth another time."

---

Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:

> Rasmus Villemoes skrev:
>
>>(*) Jeg bruger 'farve' om de fire H, K, S og R; de to typer rød og
>>sort kalder jeg kulører. Er det den korrekte terminologi, eller hvad
>>er det korrekte danske ord for "suit"?
>
> Et kortspil har kort i fire kulører og to farver. Du kan huske
> det på at der er noget der hedder "kulørsvigt" (ikke
> "farvesvigt").
>

Tak. Jeg må lige få min hjerne til at holde flyttedag for de to
begreber. Nu kender jeg ikke bridge, men jeg tror jeg vil forsøge at
huske det på udtrykket "bekende kulør".

>
> (Bridgespillere vil sætte pris på at man rangerer kulørerne fra
>mindst mod størst: klør, ruder, hjerter, spar)
>

Jeg synes nok at kunne huske, at der fandtes en vedtagen ordning af
farv^H^H^H^H kulørerne, men jeg kunne ikke huske den, og "opfandt"
derfor min egen.

Mvh Rasmus

--

---

Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:

> Henning Makholm skrev:
>
>>> Dog indser man let at 124 er den maksimale størrelse for kortbunken
>>> (givet fem kort kan man vælge 120 måder at behandle dem på, og da B
>>> kan udelukke 4 af de N forskellige kort, kan der ikke være mere end
>>> 120+4 kort i bunken).
>
>>Jeg er enig i facit, men kan ikke gennemskue dit argument. Gider du
>>uddybe?
>
> Hvis ikke jeg tager fejl, har jeg gennemskuet Rasmus' ræsonnement
> *samt* fundet en strategi for 124 kort.
>
> 120 er naturligvis 5!. Hvis man ordner permutationerne af 5 kort
> i rækkefølge, kan man altså meddele 120 forskellige talværdier.
> Hvis vi tænker os et kortspil med 124 kort i 4 kulører,
> nummererer man dem bare fra 1 til 124: 1-31 er klør, 32-62 er
> ruder, 63-93 er hjerter og 94-124 er spar.
>
> Når man skal meddele B nummeret, springer man bare over de kort
> han skal have.
>

Glemmer du ikke, at B ikke ser alle 5 kort? A har 120 muligheder, men
kan kun umiddelbart meddele 4! = 24 forskellige talværdier.

Mvh Rasmus

--

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
>
>> Dog indser man let at 124 er den maksimale størrelse for kortbunken
>> (givet fem kort kan man vælge 120 måder at behandle dem på, og da B
>> kan udelukke 4 af de N forskellige kort, kan der ikke være mere end
>> 120+4 kort i bunken).
>
> Jeg er enig i facit, men kan ikke gennemskue dit argument. Gider du
> uddybe?
>

Hmm, det er blevet sent. Da jeg tænkte det igennem i sin tid var
argumentet vandsikkert og skudtæt [nej, de holder ikke på skrift. Jeg
skulle bare lige prøve]. Mon jeg har glemt en lille detalje som jeg
kan huske efter en nats søvn? Jeg tror jeg vil give det en chance, og
derfor tage hjem. Godnat; eller god arbejdslyst til natteravnene.

Mvh Rasmus

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
> Henning Makholm <henning@makholm.net> writes:
> > Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>

> >> Dog indser man let at 124 er den maksimale størrelse for kortbunken
> >> (givet fem kort kan man vælge 120 måder at behandle dem på, og da B
> >> kan udelukke 4 af de N forskellige kort, kan der ikke være mere end
> >> 120+4 kort i bunken).

> > Jeg er enig i facit, men kan ikke gennemskue dit argument. Gider du
> > uddybe?

> Hmm, det er blevet sent. Da jeg tænkte det igennem i sin tid var
> argumentet vandsikkert og skudtæt [nej, de holder ikke på skrift. Jeg
> skulle bare lige prøve].

Nu tror jeg godt jeg kan se pointen: Det maksimale antal kort er netop
det hvor A har lige så mange beskeder at vælge imellem som B har svar
at skulle skelne mellem i hvert tilfælde. Se nemlig på samtlige
kombinationer af formen

({x1,x2,x3,x4,x5},<x1,x2,x3,x4>)

hvor x1,x2,x3,x4,x5 er fem forskellige kort, og <...> er en ordnet
følge af fire af kortene. Vi kan klassedele mængden af alle
kombinationer efter enten "samme 4 kort i rækkefølge" eller "samme 5
oprindelige kort". Hvis B har flere valgmuligheder end A må det være
fordi der er færre klasser af "samme 4 kort i rækkefølge" end "samme 5
oprindelige kort" - og det betyder at der ikke er nok beskeder at give
B til at hans strategi giver mulighed for at rekonstruere enhver
mængde af 5 oprindelige kort.

--
Henning Makholm "What a hideous colour khaki is."

---

Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

> Overraskelsen består i, at der faktisk findes en strategi der virker
> for 124 kort, men jeg har aldrig set den beskrevet.

Hmm, min kontormakker lavede engang en strategi som virker for 124
kort. Vi genererede en liste med tilfældige sæt af 5 tal mellem 0 og
123 og blev ret gode til at udføre strategien. Den krævede en del
regnearbejde og gik ret galt da vi forsøgte at optræde med den til en
julefrokost... Jeg skal lige tænke mig lidt om inden jeg kommer i
tanker om hvordan vores strategi var.

Søren

---

In <aj4u19o7lda.fsf@durin.imf.au.dk> galatius+usenet@imf.au.dk (=?iso-8859-1?q?S=F8ren_Galatius_Smith?=) writes:

>Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

>> Overraskelsen består i, at der faktisk findes en strategi der virker
>> for 124 kort, men jeg har aldrig set den beskrevet.

>Hmm, min kontormakker lavede engang en strategi som virker for 124
>kort. Vi genererede en liste med tilfældige sæt af 5 tal mellem 0 og
>123 og blev ret gode til at udføre strategien. Den krævede en del
>regnearbejde og gik ret galt da vi forsøgte at optræde med den til en
>julefrokost... Jeg skal lige tænke mig lidt om inden jeg kommer i
>tanker om hvordan vores strategi var.

>Søren

Der er en strategi for 124 kort her.
Artiklen giver også den oprindelige opgavestiller mm.
Jeg ville nødigt skulle lære den, men der er jo folk, der har
memoreret de første mange decimaler i pi og det er jo endnu
mindre nyttigt.

http://math.berkeley.edu/~tsh/Papers/cardTrick.pdf

Kort fortalt, så sorterer A de 5 tal, summerer dem modulo 5 og
beholder det tilsvarende kort. Fx 23 27 59 87 93 giver 289
dvs 4 modulo 5, dvs det er 93 der bliver gemt. Udfra
tallene 23 27 59 87 kan man så regne tilbage at hvis tallet
er før 23 må summen have været 0 modulo 5 dvs det manglende
tal må være 4 modulo 5 dvs 4, 9, 14 eller 19. Mellem 23 og 27
.... osv. Vi har nu stadig alle 24 permutationer til rådighed
til at vælge mellem disse mulige tal.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:bf0aro$4ia$1@news.net.uni-c.dk...

> ... osv. Vi har nu stadig alle 24 permutationer til rådighed
> til at vælge mellem disse mulige tal.

Meget fikst. Og man ser at det "værste" tilfælde opstår ved
119, 120, 121, 122, 123
hvilket nemt giver sammenhæng mellem k og n : k!+k-1

Man ser også en simpel huskeregel for de ukendte kort : Start med
modulus af summen og hop k+1 når der kommer et af de k-1 kort.

Mvh
Martin

---

Her er et stykke perlkode til dem, der mangler et
øveredskab til at terpe strategien

Eksempel på output:
$ perl trick 119 120 121 122 123
Input er 5 forskellige tal fra 0 til 123.
(119,120,121,122,123)
Vi beholder 119 fordi det er tal nr (119+120+121+122+123) modulo 5 dvs
tal nr 0 når vi nummererer 0,1,2,3,4
og koder dette valg som permutation nr 23 af 120,121,122,123
fordi 119 er nr 23 af de tal, det kan være,
når vi har udvalgt det efter modulo 5 måden.

Indkodning : 123,122,121,120
Udkodning : 119






#!/usr/local/bin/perl -w
use strict;
my(@tupel) = (24,27,59,87,90);
@tupel = @ARGV;
my($tupel) = join(",",@tupel);
print "Input er 5 forskellige tal fra 0 til 123.\n";
print "($tupel)\n";
my $kodning = indkod($tupel);
print "Indkodning : $kodning\n";
print "Udkodning : ".udkod($kodning)."\n";

sub indkod {
my(@tupel) = sort(split(/,/,$_[0]));
my($sum,$a,$i)= (0,0,0);
for $a (@tupel) {
$sum+=$a;
}
my($tokeep) = $tupel[$sum % 5];
print "Vi beholder $tokeep fordi det er tal nr ($tupel[0]+".
"$tupel[1]+$tupel[2]+$tupel[3]+$tupel[4]) modulo 5 dvs\n".
"tal nr ".($sum%5)." når vi nummererer 0,1,2,3,4\n";
splice(@tupel,$sum%5,1);
my($thisnr,$nr) = (0,0);
for $i (0..123) {
$thisnr = $nr if $i == $tokeep;
$nr++ if $i < $tupel[0] && ($sum-$tokeep+$i) % 5 == 0;
$nr++ if $tupel[0] < $i && $i < $tupel[1] && ($sum-$tokeep+$i) % 5 == 1;
$nr++ if $tupel[1] < $i && $i < $tupel[2] && ($sum-$tokeep+$i) % 5 == 2;
$nr++ if $tupel[2] < $i && $i < $tupel[3] && ($sum-$tokeep+$i) % 5 == 3;
$nr++ if $tupel[3] < $i && ($sum-$tokeep+$i) % 5 == 4;
}
print "og koder dette valg som permutation nr $thisnr af ".
join(",",@tupel)."\n";
print "fordi $tokeep er nr $thisnr af de tal, det kan være,\n";
print "når vi har udvalgt det efter modulo 5 måden.\n\n";
my @pat = pos2lex($thisnr,4);
my @perm = @tupel[@pat];
return join(",",@perm);
}

sub udkod {
my($tupel) = $_[0];
my(@tupel) = sort(split(/,/,$_[0]));
my($sum,$a,$i)= (0,0,0);
for $a (@tupel) {
$sum+=$a;
}
my($thisnr) = lex2pos(split(/,/,$tupel));
my($nr) = (0);
my(%kept) = ();
for $i (0..123) {
$kept{$nr} = $i if $i < $tupel[0] && ($sum+$i) % 5 == 0;
$kept{$nr} = $i if $tupel[0] < $i && $i < $tupel[1] && ($sum+$i) % 5 == 1;
$kept{$nr} = $i if $tupel[1] < $i && $i < $tupel[2] && ($sum+$i) % 5 == 2;
$kept{$nr} = $i if $tupel[2] < $i && $i < $tupel[3] && ($sum+$i) % 5 == 3;
$kept{$nr} = $i if $tupel[3] < $i && ($sum+$i) % 5 == 4;
$nr++ if $i < $tupel[0] && ($sum+$i) % 5 == 0;
$nr++ if $tupel[0] < $i && $i < $tupel[1] && ($sum+$i) % 5 == 1;
$nr++ if $tupel[1] < $i && $i < $tupel[2] && ($sum+$i) % 5 == 2;
$nr++ if $tupel[2] < $i && $i < $tupel[3] && ($sum+$i) % 5 == 3;
$nr++ if $tupel[3] < $i && ($sum+$i) % 5 == 4;
}
return "$kept{$thisnr}\n";
}

sub lex2pos {
my(@a) = @_;
my($nr,$n,$f,$s) = (0,0,1,0);
my($i,$j);
for $i (0..$#a) {
$f = ($i==0)?1:$f*$i;
$n = $#a-$i;
$s = 0;
for $j ($n..$#a) {
$s++ if $a[$j] < $a[$n];
}
$nr += $s*$f;
}
return $nr;
}

sub pos2lex {
my($n,$len) = ($_[0],$_[1]);
my($i) = 1;
my(@pat) = ();
while ($i <= $len) {
push @pat, ($n % $i);
$n = int ($n/$i);
$i++;
}
my @source = (0..$#pat);
my @perm = ();
push @perm, splice(@source, (pop @pat), 1) while @pat;
return (@perm);
}

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

"Kai Birger Nielsen" <bnielsen@daimi.au.dk> skrev i en meddelelse news:bf0aro$4ia$1@news.net.uni-c.dk...

>
> Der er en strategi for 124 kort her.
> Artiklen giver også den oprindelige opgavestiller mm.
> Jeg ville nødigt skulle lære den, men der er jo folk, der har
> memoreret de første mange decimaler i pi og det er jo endnu
> mindre nyttigt.
>
> http://math.berkeley.edu/~tsh/Papers/cardTrick.pdf
>
En artikel med megen vægt på det pædagogiske aspekt.
I artiklens referencer fandt jeg en lækker side hvor tingene
beskrives meget overskueligt.
http://www.stonehill.edu/compsci/Japan.htm

Mvh
Martin