---

Hej

Jeg skal holde foredrag om tankesport og kom til at tænke på flg. logiske
opgave :

Spillet foregår på et stort skakbræt (med uendelig antal rækker og søjler).
Brættet deles på midten i to lejre - vennelejren og fjendelejren.
Brikker kan nu placeres valgfrit i vennelejren - i første omgang er
fjendelejren tom.
Opgaven går nu ud på at trænge så langt ind i fjendelejren med så få brikker
som muligt.
Brikker må kun bevæges horisontalt og vertikalt, og kan kun flyttes, hvis de
kan hoppe over en brik - denne fjernes så.

Flg. ses nemt :
1) Man kan komme en række ind i fjendelejren med 2 brikker - disse placeres
lige op til grænsen, og med ét hop er man inde ved fjenden.
2) Man kan komme to rækker ind med 5 brikker. De 3 placeres lige ved grænsen
og de 2 sidste bag ved disse i næste række. Med 4 hop er man i mål - altså
således :


fjendeland
---------------
X X X
X X

De 2 bageste hopper over, og er en række inde i fjendeland. Dernæst hoppes
til højre, og den sidste i venneland hopper over denne, så den når ind til
2. række i fjendeland.

3 ) 3 rækker kan opnås med 9 brikker og 8 hop.
4) 4 og 5 rækker kan også opnås.

Så vidt jeg husker, er 5 rækker ind i fjendeland det maximale man kan opnå -
6 rækker er umuligt; selv med et udendeligt stort skakbræt og uendelig mange
brikker.

Spørgsmål : Hvad hedder spillet - og er tesen om umuligheden af 6 rækkers
indtrængen bevist.
Man kan starte med at finde antal brikker og træk (min.) for at trænge 4 og
5 rækker ind - svar gerne her i gruppen.

--
Hilsen
Regnar Simonsen

---

"Regnar Simonsen" <regnar.simo@image.dk> writes:

> Hej
>
> Jeg skal holde foredrag om tankesport og kom til at tænke på flg. logiske
> opgave :
>
> Spillet foregår på et stort skakbræt (med uendelig antal rækker og søjler).
> Brættet deles på midten i to lejre - vennelejren og fjendelejren.

(midten af noget uendeligt? Ok :))

> Flg. ses nemt :
> 1) Man kan komme en række ind i fjendelejren med 2 brikker - disse placeres
> lige op til grænsen, og med ét hop er man inde ved fjenden.

Ok, det er en række ind at få en lige over grænsen.

> 2) Man kan komme to rækker ind med 5 brikker. De 3 placeres lige ved grænsen
> og de 2 sidste bag ved disse i næste række. Med 4 hop er man i mål - altså
> således :

Det kan gøres med tre brikker og to hop:

+---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | A |
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | | B | | | | | |
+===+===+===+ +===+===+===+ +===+===+===+
| A | C | | | A | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
| | B | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+

Det du beskriver er faktisk tre rækker ind, ikke to.

> 3 ) 3 rækker kan opnås med 9 brikker og 8 hop.

Og det er fire rækker ind. Det kan også klares
med 8 brikker og 7 hop.

Startposition:

+===+===+===+===+===+===+===+
2| | X | X | X | X | X | |
+---+---+---+---+---+---+---+
1| X | X | | | | | X |
+---+---+---+---+---+---+---+
A B C D E F G

Trækkene er:

A1-C3
B1-D3
D2-D4
C3-E5
G1-E3
E2-E4
E4-E6!

Generelt kan man se hvor få træk man teoretisk set behøver for at
få en brik til række n. For at få en brik til række n skal man have
brikker i række n-1 og n-2. I praksis kan det kræve flere fordi man
ikke kan placere alle brikker på passende startpositioner.

n antal træk til række n =
1 1 1
2 1 + antal træk til række 1 2
3 1 + antæl træk til række 1 + antal træk til række 2 4
4 1 + antæl træk til række 2 + antal træk til række 3 7
5 1 + antæl træk til række 3 + antal træk til række 4 12
6 1 + antæl træk til række 4 + antal træk til række 5 22

Det er iøvrigt Fibonacci(n+1) - 1.

> 4) 4 og 5 rækker kan også opnås.

fem og seks rækker kan også opnås :)

Fem kan jeg se kan gøres på 12 træk. Det passer også med det
teoretiske minimum ovenfor.

Startposition
+===+===+===+===+===+===+===+===+===+
2| X | X | X | X | X | X | X | X | |
+---+---+---+---+---+---+---+---+---+
1| | | | X | X | X | | X | X |
+---+---+---+---+---+---+---+---+---+
A B C D E F G H O

Træk:

D1-B3
A2-C4
E1-C3
B2-D4
F1-D3
D3-D5
C4-E6
H1-F3
F2-F4
I1-G3
G3-E5
E5-E7!

> Så vidt jeg husker, er 5 rækker ind i fjendeland det maximale man kan opnå -
> 6 rækker er umuligt; selv med et udendeligt stort skakbræt og uendelig mange
> brikker.

Jeg tror som sagt du tæller forkert, hvilket lidt ødelægger min
skadefryd over at kunne komme seks rækker ind (28 træk, 28+1 brik).
Når jeg kigger på min løsning er der også netop seks (spild)træk der
foregår helt bagved grænsen.

> Spørgsmål : Hvad hedder spillet - og er tesen om umuligheden af 6 rækkers
> indtrængen bevist.

Kender det ikke, men det er sødt.

> Man kan starte med at finde antal brikker og træk (min.) for at trænge 4 og
> 5 rækker ind - svar gerne her i gruppen.

Jeg har ikke bevist at ovenstående teoretisk underste grænse virkelig
holder, men et bevis ville være (skitseret) at hvis to brikker er på
banen samtidigt, så har ingen af deres tidligere flyt haft noget med
hinanden at gøre (evt. ved ikke at fjerne den brik der hoppes over,
men istedet stable brikkerne oven på hinanden, så man kan se hvilke
brikker der har påvirket hinanden). For at få en brik til række
n må der være en brik i rækkerne n-1 og n-2, og disse er flyttet
dertil uafhængigt af hinanden.

Hvis man tror på dette "proof by handwaving", så er ovenstående en
underste grænse, og indtil femte række kan jeg ramme grænsen skarpt.
For sjette række går jeg seks over. Jeg har flere gange været ved
at tro at jeg kunne nå syvende række, men det har ikke virket når det
kom til stykket.

Håber det kan bruges til noget.
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

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

> 6 1 + antæl træk til række 4 + antal træk til række 5 22

Og jeg kan ikke regne. Der 22 skulle være 20.

> Det er iøvrigt Fibonacci(n+1) - 1.

fordi så passer det!


> For sjette række går jeg seks over.

Og her skal det så være otte, hvilket det også er ved eftertælning.

Ikke flere postings idag!
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

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

> "Regnar Simonsen" <regnar.simo@image.dk> writes:
>
> > 2) Man kan komme to rækker ind med 5 brikker. De 3 placeres lige ved
> > grænsen og de 2 sidste bag ved disse i næste række. Med 4 hop er man
> > i mål - altså således :
>
> Det kan gøres med tre brikker og to hop:
>
> +---+---+---+ +---+---+---+ +---+---+---+
> | | | | | | | | | | | A |
> +---+---+---+ +---+---+---+ +---+---+---+
> | | | | | | B | | | | | |
> +===+===+===+ +===+===+===+ +===+===+===+
> | A | C | | | A | | | | | | |
> +---+---+---+ +---+---+---+ +---+---+---+
> | | B | | | | | | | | | |
> +---+---+---+ +---+---+---+ +---+---+---+

Beklager, men

> > Brikker må kun bevæges horisontalt og vertikalt, og kan kun flyttes,
> > hvis de kan hoppe over en brik - denne fjernes så.

> > Så vidt jeg husker, er 5 rækker ind i fjendeland det maximale man
> > kan opnå - 6 rækker er umuligt; selv med et udendeligt stort
> > skakbræt og uendelig mange brikker.

Grænsen ligger lige omkring de fem.

> > Spørgsmål : Hvad hedder spillet - og er tesen om umuligheden af 6 rækkers
> > indtrængen bevist.

Jeg kan ikke huske hvad spillet hedder, men det er bevist at der er en
grænse for hvor langt man kan nå. Jeg kan ikke huske ret meget af
beviset, men det er vist noget med at tildele brikkerne en "potentiel
energi" afhængig af dens position. Et træk skal så bevare den samlede
"energi", og så skal man bare regne ud at en brik ikke kan opnå en
potentiel energi der vil svare til en position "langt" inde i
fjendeland.

..Henrik

--
"Det er fundamentalt noget humanistisk vås, at der er noget,
der hedder blød matematik."
--- citat Henrik Jeppesen, dekan for det naturvidenskabelige fakultet

---

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

> Lasse Reichstein Nielsen <lrn@hotpop.com> writes:
>
> > "Regnar Simonsen" <regnar.simo@image.dk> writes:

> Beklager, men
>
> > > Brikker må kun bevæges horisontalt og vertikalt, og kan kun flyttes,
> > > hvis de kan hoppe over en brik - denne fjernes så.

Ups. Hvordan det lykkedes mig at læse vertikalt som diagonalt skal jeg
ikke kunne svare på. Blot undskylde mig med at det åbenbart var sent :)

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Regnar Simonsen wrote:

> Spillet foregår på et stort skakbræt (med uendelig antal
> rækker og søjler). Brættet deles på midten i to lejre -
> vennelejren og fjendelejren. Brikker kan nu placeres
> valgfrit i vennelejren - i første omgang er fjendelejren
> tom. Opgaven går nu ud på at trænge så langt ind i
> fjendelejren med så få brikker som muligt.
> Brikker må kun bevæges horisontalt og vertikalt, og kan
> kun flyttes, hvis de kan hoppe over en brik - denne
> fjernes så.

Spillet er omtalt Scientific American (marts 1991).
Det er sidst i bladet under Mathematical Recreations,
hvor A.K.Dewdney skriver om en forelæsning af Ross Hornberger.

I nedenstående tabel er d nummeret på fjenderækken.

d | antal
1 2
2 4
3 8
4 20
5 ?

Ross spørger publikum, hvad der skal skrives under ved ?.
Der gættes livligt.

Det viser sig, at en million ikke er nok.

John Conway har vist, at det er umuligt uanset, hvor mange
brikker man bruger.

I artiklen gives ikke et bevis, men man kan mellem linjerne
læse, at det er ikke er helt simpelt.

Artiklen afsluttes med disse henvisninger: Mathematical Gems,
Mathematical Morsels og Mathematical Plums alle af Ross Hornsberger.

En Googlesøgning på John Conway og checkers finder denne side:

http://www.cut-the-knot.com/proofs/checker.shtml

Her kan man lege med dam-brikkerne i en Java-applet -
og sandelig så - der er også et bevis for umuligheden af d=5.


http://www.cut-the-knot.com/proofs/checker.shtml

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" wrote:
>
> En Googlesøgning på John Conway og checkers finder denne side:
>
> http://www.cut-the-knot.com/proofs/checker.shtml
>
> Her kan man lege med dam-brikkerne i en Java-applet -
> og sandelig så - der er også et bevis for umuligheden af d=5.

God side om emnet. Den besvarer sikkert Regnars spørgsmål.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:
> "Jens Axel Søgaard" wrote:

>> http://www.cut-the-knot.com/proofs/checker.shtml

> God side om emnet. Den besvarer sikkert Regnars spørgsmål.

Cut-the-knot er generelt et sted, der er nemt bruge tid på.

Han har forresten også en side omhandlende sommeremnet
Monty Hall-problemet:

http://www.cut-the-knot.com/hall.shtml

--
Jens Axel Søgaard

---

Jeppe Stig Nielsen :
> God side om emnet. Den besvarer sikkert Regnars spørgsmål.

Så sandelig - og tak for det !!
Det er dog stadig umiddelbart overraskende, at man ikke kan komme mere end 4
rækker over grænsen.


--
Hilsen
Regnar Simonsen