---

Her er et par stykker, som jeg selv har fundet på gennen tiderne (men
det skulle ikke undre mig om andre også har fundet de samme):

1. Trekanten

Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
som muligt (dog mere end en) ligebenede retvinklede trekanter, der
alle har forskelligt areal.


2. Kodelåsen

Direktøren for en af de store banker i Zurich dør pludselig af
hjerteslag, og det giver et problem for hans bank. Han er nemlig den
eneste, der kendte kodelåsen til bankens boks.

Banken kontakter firmaet, der har lavet boksens lås. De får at vide at
kodelåsen er konstrueret på følgende måde:

Pengeskabet er udstyret med fem knapper, markeret ``reset'', ``A'',
``B'', ``C'' og ``D''. ``reset'' knappen nulstiller en kodeindtasting
og koden tastes ind ved en sekvnes af tryk på de resterende knapper.

Inde i låsen er der to hulstrimler, I og II. ``reset'' knappen spoler
begge strimler frem og klipper af, så man starter med to blanke
strimler. De andre knapper skriver forskellige sekvenser af 0'er og
1'er på de to strimler. Når de to strimler er hullet med den _samme_
sekvens, går låsen op. Når låsen er åben, kan man ændre på de
sekvenser knapperne ``A'' til ``D'' skriver på strimlerne, og på den
måde omprogrammere låsens kode.

Låsefirmaet kan ikke hjælpe banken, med mindre de ved, hvordan låsen
er programmeret.

I bankdirektørens lomme finder man en seddel med følgende tekst:

A: I: 001 II: 0
B: I: 01 II: 011
C: I: 10 II: 001
D: I: 01 II: 101

Man gætter på, at det er låsens indstilling, og sender sedlen til
låsefirmaet med kurer. Kureren vender efter nogen tid tilbage med en
seddel, hvorpå der er skrevet en sekvens af bogstaverne ``A'', ``B'',
``C'' og ``D''. Den nye bankdirektør taster denne sekvens ind på
låsens tastatur, og døren til boksen går op.

Hvad var den kode, som åbnede låsen?


   Torben

---

On 27 Apr 2004 11:20:48 +0200 Torben Ægidius Mogensen wrote:

> 2. Kodelåsen
>
> Direktøren for en af de store banker i Zurich dør pludselig af
> hjerteslag, og det giver et problem for hans bank. Han er nemlig den
> eneste, der kendte kodelåsen til bankens boks.
>
> Banken kontakter firmaet, der har lavet boksens lås. De får at vide at
> kodelåsen er konstrueret på følgende måde:
>
> Pengeskabet er udstyret med fem knapper, markeret ``reset'', ``A'',
> ``B'', ``C'' og ``D''. ``reset'' knappen nulstiller en kodeindtasting
> og koden tastes ind ved en sekvnes af tryk på de resterende knapper.
>
> Inde i låsen er der to hulstrimler, I og II. ``reset'' knappen spoler
> begge strimler frem og klipper af, så man starter med to blanke
> strimler. De andre knapper skriver forskellige sekvenser af 0'er og
> 1'er på de to strimler. Når de to strimler er hullet med den _samme_
> sekvens, går låsen op. Når låsen er åben, kan man ændre på de
> sekvenser knapperne ``A'' til ``D'' skriver på strimlerne, og på den
> måde omprogrammere låsens kode.

Det var da et kedelig pengeskab. Når strimlerne er tomme, indeholder de
vel den samme sekvens.

> Låsefirmaet kan ikke hjælpe banken, med mindre de ved, hvordan låsen
> er programmeret.
>
> I bankdirektørens lomme finder man en seddel med følgende tekst:
>
> A: I: 001 II: 0
> B: I: 01 II: 011
> C: I: 10 II: 001
> D: I: 01 II: 101
>
> Man gætter på, at det er låsens indstilling, og sender sedlen til
> låsefirmaet med kurer. Kureren vender efter nogen tid tilbage med en
> seddel, hvorpå der er skrevet en sekvens af bogstaverne ``A'', ``B'',
> ``C'' og ``D''. Den nye bankdirektør taster denne sekvens ind på
> låsens tastatur, og døren til boksen går op.
>
> Hvad var den kode, som åbnede låsen?

Jeg forsøgte at nå frem til en løsning, ved at vende sekvenserne om. Så
er det klart, at det sidste bogstav må være D. Herefter er det klart at
det næstsidste må være A, osv. osv. og enten laver jeg en fejl et sted,
eller også er koden ret lang (eller har længde 0).

--
41 6E 64 65 72 73

---

Scripsit Anders Bo Rasmussen <fuzz01@spamfilter.dk>

> Herefter er det klart at det næstsidste må være A, osv. osv. og
> enten laver jeg en fejl et sted, eller også er koden ret lang (eller
> har længde 0).

Jeg blev stædigt ved, indtil overskuddet på strimmel I begyndte at
krympe. Så nåede jeg frem til sekvensen

BCDCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABACAAD

Men sandsynligheden for at jeg har begået en fejl undervejs er stor.
Hm, vi må hellere regne efter på computer:

$_ = "0" ; $sekvens = "AD" ;
ydre: do{
indre: for $linje ( "A:001:0",
"B:01:011",
"C:10:001",
"D:01:101",
"BC::^01") {
($bogstav,$I,$II) = split /:/, $linje ;
next indre unless s/$II$// ;
s/^/$I/ ;
$sekvens = $bogstav.$sekvens ;
goto ydre ;
}
} while (0) ;
print $_ , "\n", $sekvens, "\n" ;

Minsandten! Den giver mig ret!

BCDCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABACAAD

--
Henning Makholm "Det er du nok fandens ene om at
mene. For det ligger i Australien!"

---

Henning Makholm wrote:
>
> Jeg blev stædigt ved, indtil overskuddet på strimmel I begyndte at
> krympe. Så nåede jeg frem til sekvensen
>
> BCDCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABACAAD

Jeg synes jeg har en valgmulighed:

BC{DCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABAC}AAD

eller

BC{DCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABAC}
DA{DCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABAC}AAD

med et vilkårligt antal gentagelser af stykket "DA{...}".

> Hm, vi må hellere regne efter på computer:
> [snip program]

Spændende - hvilket sprog? Jeg går ud fra at "BC::^01"
(og initialiseringen $sekvens = "AD") er fordi du har
regnet noget af det i hånden?

Anders.

---

Scripsit Anders Nygaard <dnygaard@post.tele.dk>
> Henning Makholm wrote:

> > BCDCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABACAAD

> Jeg synes jeg har en valgmulighed:

> BC{DCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABAC}AAD

> eller

> BC{DCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABAC}
> DA{DCCBABCDCDCCDCCBACCBADCAADCCCBABAAADCDCABACCBACAADCAADAADABAC}AAD

> med et vilkårligt antal gentagelser af stykket "DA{...}".

Ja, det viste min håndregning også. Men der er jo ingen grund til at
gå rundt og huske på en dobbelt så lang kode.

> > Hm, vi må hellere regne efter på computer:
> > [snip program]

> Spændende - hvilket sprog?

Perl.

> Jeg går ud fra at "BC::^01" (og initialiseringen $sekvens = "AD") er
> fordi du har regnet noget af det i hånden?

Ja. Det er jo velkendt at den generelle problemtype er uafgørlig.

--
Henning Makholm "Jeg forstår mig på at anvende sådanne midler på
folks legemer, at jeg kan varme eller afkøle dem,
som jeg vil, og få dem til at kaste op, hvis det er det,
jeg vil, eller give afføring og meget andet af den slags."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Anders Nygaard <dnygaard@post.tele.dk>

> > Jeg går ud fra at "BC::^01" (og initialiseringen $sekvens = "AD") er
> > fordi du har regnet noget af det i hånden?
>
> Ja. Det er jo velkendt at den generelle problemtype er uafgørlig.

Det forhindrer ikke, at man laver et program, der prøver at løse det
generelle problem -- man kan bare ikke være sikker på at det altid
terminerer. For PCP (Post's correspondence problem) vil en simpel
bredde-først altid finde en løsning, hvis en sådan findes. Men den
vil ikke kunne fortælle dig, at der ikke findes en løsning. Man kan
udvide programmet, så man opdager klart uproduktive grene af søgningen
og dermed i visse tilfælde kunne sige at der ikke findes løsninger.
Men der vil altid være tilfælde, hvor man ikke ved om programmet bare
skal have lidt mere tid, eller om det aldrig standser.

   Torben

---

Scripsit torbenm@diku.dk (Torben Ægidius Mogensen)

> Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
> som muligt (dog mere end en) ligebenede retvinklede trekanter, der
> alle har forskelligt areal.

Jeg har en løsning med 6 småtrekanter. De har arealerne ½, 1, 2, 4, 8 og 9.

> Han er nemlig den eneste, der kendte kodelåsen til bankens boks.

Den er fra Emil Post i Berlin.

--
Henning Makholm "Apologies if I am repeating obvious
conclusions. My only gateway onto the Net is
very expensive, and I miss many important postings...
Please write to me and tell me what you think. I don't get much mail."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit torbenm@diku.dk (Torben Ægidius Mogensen)
>
> > Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
> > som muligt (dog mere end en) ligebenede retvinklede trekanter, der
> > alle har forskelligt areal.
>
> Jeg har en løsning med 6 småtrekanter. De har arealerne ½, 1, 2, 4, 8 og 9.

Seks trekanter er også den bedste opdeling jeg har, så det er nok den
samme.

   Torben

---

torbenm@diku.dk (Torben Ægidius Mogensen) writes:

> Henning Makholm <henning@makholm.net> writes:
>
> > Scripsit torbenm@diku.dk (Torben Ægidius Mogensen)
> >
> > > Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
> > > som muligt (dog mere end en) ligebenede retvinklede trekanter, der
> > > alle har forskelligt areal.
> >
> > Jeg har en løsning med 6 småtrekanter. De har arealerne ½, 1, 2, 4, 8 og 9.
>
> Seks trekanter er også den bedste opdeling jeg har, så det er nok den
> samme.

Det mener jeg nu at kunne bevise. (Takket være Hennings oplysninger om
småtrekanternes areal kan jeg også rekonstruere hans løsning - eller i
hvert fald en hvor småtrekanterne har samme mængde af arealer).

Beviset er hverken kort eller elegant, til gengæld er det ret simpelt.

Planen er at vise at der ikke er nogen løsninger med hverken 2, 3, 4
eller 5 småtrekanter.

2: Det er trivielt at indse at der kun er en måde at dele trekanten i to
ligebenede retvinklede trekanter, og at de er lige store.

For at gøre det lettere at følge resten af beviset vil jeg anbefale at
man på dette tidspunkt finder et stykke papir og prøver at tegne de
figurer jeg forsøger at beskrive.

For de resterende tilfælde skal vi gøre den observation af vi ikke kan
dele en vinkel på 45 grader og derfor må de to spidse vinkler i den
trekant vi starter med blive til (spidse) vinkler i to af
småtrekanterne. Der er to måder at skære en spids vinkel af på,
vinkelret på hypotenusen eller vinkelret på den hosliggende
katete. Der er så tre forskellige måder at skære begge spidse vinkler af
på. Den resulterende figur er en femkant (evt. udartet), hvor to af
siderne er kateter i de afskårne småtrekanter.
Det er denne resulterende figur vi skal studere.

3: Hvis vi havde en løsning ville den resulterende figur være udartet
til en trekant, men to af siderne er kateter i de allerede afskårne
småtrekanter, og mindst en af disse to vil også være en katete i den
sidste trekant. Men to ligebenede retvinklede trekanter med kateter der
er lige lange er lige store.

4: Her skal de resulterende figur være udartet til en firkant. den kan
have tre(fire) forskellige udseender. Den kan være et rektangel
(herunder et kvadrat)
eller have to rette vinkler og to vinkler på henholdsvis 45 og 135
grader, i det sidste tilfælde kan de to rette vinkler være nabovinkler
eller "modstående".
- Rektangel: Den eneste måde at dele et rektangel i to trekanter giver
to lige store trekanter (der ikke kan være ligebenede).
- To rette vinkler: Vi skal dele vinklen på 135 grader.
- "Modstående": Det modstående hjørne til vinklen på 135 er vinklen på
45 grader som vi ikke må dele.
- Naboer: Der er to muligheder for hvilket par af sider der er kateter
i de afskårne småtrekanter, men i begge tilfælde vil en af dem være
en katete i den ene af de to nye trekanter.
Derudover er der tilfældet hvor den resulterende figur er udartet til en
trekant, men så er vi tilbage i det oprindelige problem med en grænse på
2.

5: Hvis den resulterende figur er en femkant, vil den have tre rette
vinkler og to vinkler på 135 grader.
Når en femkant skal deles i tre trekanter, kan det kun gøres ved at
trække to rette liniestykker fra ét hjørne til de to hjørner der ikke er
dets naboer.
Det er klart at to af de tre hjørner der skal deles er de to hvor
vinklen er 135 grader, og det er også klart at de hjørne der skal deles
to gange er blandt de to.
Hvis de to hjørner med en vinkel på 135 grader er naboer, kan vi ikke
dele noget af dem to gange, altså må femkanten have en ret vinkel mellem
de to vinkler på 135 grader. Der er to muligheder for hvilket par af
sider der er kateter i de afskårne småtrekanter, det kan enten være de
to parallelle sider eller den ene af de parallelle og den
ikke-tilstødende side der danner en 45 graders vinkel med denne. I begge
tilfælde vil en af de dannede trekanter have en af disse sider som
katete.
Hvis figuren er udartet til en firkant er der de samme tre muligheder
for dens udseende som under 4.
- Rektangel: Alle sider har samme længde som en katete i en af de
afskårne småtrekanter. Der er fire rette vinkler og de tre trekanter
vi skal lave, skal kun have tre, så vi skal dele mindst en af dem, af
symmetriårsager er det ligegyldigt hvilken vi vælger. For at undgå at
ende med en femkant der skal deles i to trekanter er vi nødt til at
trække delelinien hele vejen gennem figuren til vi rammer en side
(eller et hjørne hvis vores figur var et kvadrat). Vi har nu fået
lavet en trekant der deler katete med en af de afskårne trekanter og
har derudover en firkant og kan kun dele én gang til (hvis figuren var
et kvadrat har vi to trekanter der skal deles).
- To rette vinkler:
- "Modstående": Dette opstår kun hvis en af de afskårne småtrekanter
er halvdelen af den vi startede med, men det betyder at vi i den
anden halvdel prøver at lave en opdeling med kun fire småtrekanter.
- Naboer: Den lange af de parallelle sider og den skrå side er kateter i
de afskårne småtrekanter. Vinklen på 135 grader skal deles. Eftersom
den skrå side støder op til dette hjørne, må den være hypotenuse i
den trekant vi danner ved delingen, men det efterlader et rektangel
der skal deles i to, og det har vi set ikke kan gøres.
Hvis figuren er udartet til en trekant, befinder vi os atter i et
allerede behandlet tilfælde.


Så må jeg vist have ret til at stille et par spørgsmål:
- Er løsningen med seks småtrekanter entydig?
- Det er oplagt at man kan lave løsninger med 6+5*n (for alle naturlige
tal n) småtrekanter, men for hvilke andre naturlige tal er der
løsninger? (Man behøver ikke engang kende en løsning med 6 for at
kunne beskrive hvordan 6+5*n opnås, men hvis man kender Hennings
mængde af arealer kan man indse at ingen af disse konstruktioner er
entydige).

..Henrik

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

---

Scripsit Henrik Christian Grove <grove@sslug.dk>

> - Det er oplagt at man kan lave løsninger med 6+5*n (for alle naturlige
> tal n) småtrekanter, men for hvilke andre naturlige tal er der
> løsninger?

Der er løsninger for alle naturlige tal større end 6.

Start med n-6 halveringer. Så har man n-5 trekanter af forskellig
størrelse og 2 små der er ens og mindre end de n-5. Del den ene af de
to små i 6 med min konstruktion. Voila! (og doh?)

> (Man behøver ikke engang kende en løsning med 6 for at
> kunne beskrive hvordan 6+5*n opnås, men hvis man kender Hennings
> mængde af arealer kan man indse at ingen af disse konstruktioner er
> entydige).

Selv for n=7 kan ovenstående konstruktion udføres på to forskellige
måder der ikke har nogen pæn symmetri, så for n>6 er der ihvertfald
ikke nogen tal hvor løsningen er geometrisk entydig.

Det er muligt at mængden af småtrekanternes *arealer* (men ikke deres
geometriske konfiguration) er entydig for n=6 og/eller n=7. Men
allerede for n=8 har jeg to forskellige løsninger med arealerne

½, 1, 2, 4, 8, 16, 32, 49 (sum 15²/2)

½, 1, 2, 4, 8, 9, 24½, 49 (sum 14²/2)

--
Henning Makholm "Hele toget raslede imens Sjælland fór forbi."

---

"Henning Makholm" <henning@makholm.net> skrev i en meddelelse news:878yfoiiy1.fsf@kreon.lan.henning.makholm.net...

Til dem der ikke har løsningen ud fra Hennings oplysninger:
Start fra den rette vinkel og del den ene katete 1k,6h den anden
1k,2k,4k, hvor bogstavet angiver katete eller hypotenuse.

Mvh
Martin

---

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

> Beviset er hverken kort eller elegant, til gengæld er det ret simpelt.

Vi gør det lige en tand længere.

> symmetriårsager er det ligegyldigt hvilken vi vælger. For at undgå at
> ende med en femkant der skal deles i to trekanter

Der findes femkanter der kan deles i to trekanter, så det tilfælde er vi
også lige nødt til at tage os af.
Det forekommer dog kun hvis firkanten var et kvadrat, og opdelingen af
femkanten i to trekanter giver en trekant der er lige så stor som den vi
er ved at lave.

Andre sære udartede tilfælde jeg har overset?

..Henrik

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

---

Scripsit Henrik Christian Grove <grove@sslug.dk>

> Der findes femkanter der kan deles i to trekanter,

Men sådan en femkant kan da ikke være konveks?

--
Henning Makholm "He who joyfully eats soup has already earned
my contempt. He has been given teeth by mistake,
since for him the intestines would fully suffice."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Henrik Christian Grove <grove@sslug.dk>
>
> > Der findes femkanter der kan deles i to trekanter,
>
> Men sådan en femkant kan da ikke være konveks?

Korrekt, men det gør det ikke mere rimeligt at jeg i første omgang
brugte "sætningen" 'En femkant kan ikke deles i to trekanter'.

..Henrik

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

---

> 1. Trekanten
> Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
> som muligt (dog mere end en) ligebenede retvinklede trekanter, der
> alle har forskelligt areal.
>

1. Del trekanten i midten af den rette vinkel. Så rammer snittet hypotenusen
(den længste side vinkelret på og danner to nye retvinklede trekanter.
2. Vælg den ene og gentag nr. 1.

Herved opnåes tælleligt uendeligt mange trekanter med arealerne 1/(2^n),
relativt til det oprindelige areal, for alle naturlige tal n.

Morten

---

"Morten" <morten@FJERN_TEKSTENravnsborgnet.dk> writes:

>> 1. Trekanten
>> Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
>> som muligt (dog mere end en) ligebenede retvinklede trekanter, der
>> alle har forskelligt areal.
....
> Herved opnåes tælleligt uendeligt mange trekanter med arealerne 1/(2^n),
> relativt til det oprindelige areal, for alle naturlige tal n.

Det diskvalificerer vist sig selv som "så få som muligt" :)

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

---

> >> 1. Trekanten
> >> Del en ligebenet retvinklet trekant (dvs. et halvt kvadrat) op i så få
> >> som muligt

> > Herved opnåes tælleligt uendeligt mange trekanter med arealerne 1/(2^n),

> Det diskvalificerer vist sig selv som "så få som muligt" :)

Ak, ak, ak. Tænk at et så lille ord kan være så overset

Morten