---

Hvis man starter med strengen

ABCDEFGHIJKLMNOPQRSTUVWXYZ

og splitter den i to lige lange strenge, og derefter "rifler" den, således
at man tager første bogstav fra streng 1, dernæst første bogstav fra streng
2, dernæst andet bogstav fra streng 1, dernæst andet bogstav fra streng 2,
osv., og gør det samme med den nye streng, ender man med følgende sekvens af
strenge:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
ANBOCPDQERFSGTHUIVJWKXLYMZ
ATNHBUOICVPJDWQKEXRLFYSMGZ
AWTQNKHEBXUROLIFCYVSPMJGDZ
ALWITFQCNYKVHSEPBMXJUGRDOZ
ASLEWPIBTMFXQJCUNGYRKDVOHZ
AJSCLUENWGPYIRBKTDMVFOXHQZ
ARJBSKCTLDUMEVNFWOGXPHYQIZ
AVRNJFBWSOKGCXTPLHDYUQMIEZ
AXVTRPNLJHFDBYWUSQOMKIGECZ
AYXWVUTSRQPONMLKJIHGFEDCBZ
AMYLXKWJVIUHTGSFREQDPCOBNZ
AGMSYFLRXEKQWDJPVCIOUBHNTZ
ADGJMPSVYCFILORUXBEHKNQTWZ
AODRGUJXMBPESHVKYNCQFTIWLZ
AHOVDKRYGNUCJQXFMTBIPWELSZ
AQHXOFVMDTKBRIYPGWNEULCSJZ
AIQYHPXGOWFNVEMUDLTCKSBJRZ
AEIMQUYDHLPTXCGKOSWBFJNRVZ
ACEGIKMOQSUWYBDFHJLNPRTVXZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Den oprindelige streng er 26 tegn lang, og der skal 20 ombytninger til, før
vi er tilbage ved den oprindelige streng.

Nu har jeg forsøgt med strenge af forskellig længde, og herunder står
sammenhængen mellem strengens længde x og antallet af ombytninger y for at
komme tilbage til udgangspunktet:

x y

2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
30 28
32 5
34 10

Det ses, at for x = 2, 4, 8, 16, 32, ... er y = 1, 2, 3, 4, 5, ... De andre
tal synes spredt lidt mere tilfældigt. De tal, der er højest (12, 14, 20 og
30), følger alle y = x - 2.

Hvilken statistik eller fordeling er på spil her? Kan man sige noget begavet
om, hvor mange ombytninger der skal til, før man er tilbage ved
udgangspunktet, uden at skulle simulere det på en computer? Findes der en
generel formel for y(x)?

/steen

---

Hej Steen,

> Hvilken statistik eller fordeling er på spil her? Kan man sige noget begavet
> om, hvor mange ombytninger der skal til, før man er tilbage ved
> udgangspunktet, uden at skulle simulere det på en computer? Findes der en
> generel formel for y(x)?

Interessant problem du har fundet. Databasen over talfølger har denne
beskrivelse:

mindste m så 2n+1 går op i 2^m-1.

<http://www.research.att.com/~njas/sequences/?q=1%2C+2%2C+4%2C+3%2C+6%2C+10%2C+12%2C+4%2C+8&language=english&go=Search>

Der er henvisning til blandt andet:

<http://mathworld.wolfram.com/RiffleShuffle.html>

--
Jens Axel Søgaard

---

Steen wrote:
> x y
> 2 1
> 4 2
> 6 4
> 8 3
> 10 6
> 12 10
> 14 12
> 16 4
> 18 8
> 20 18
> 22 6
> 24 11
> 26 20
> 28 18
> 30 28
> 32 5
> 34 10
>
> De tal, der er højest (12, 14, 20 og 30), følger alle y = x - 2.

Hvad mener du med "de tal, der er højest" ?
- for fx 26->20 følger da ikke dit mønster?


--
mvh Kim Jensen
blog.werx @ http://kim.litewerx.dk
Port80.biz // ColorBlender.com // LiteWerx.dk

---

Steen fortalte:
>
> Hvilken statistik eller fordeling er på spil her? Kan man sige noget
> begavet om, hvor mange ombytninger der skal til, før man er tilbage
> ved udgangspunktet, uden at skulle simulere det på en computer?
> Findes der en generel formel for y(x)?

Du har vist fået et svar. Men det er jo naturligt at stille det samme
spørgsmål med 3-deling. Og det undersøgte jeg lige og fik orden af 3 mod
3*n+2, eller mindste m hvor 3*n+2 går op i 3^m-1
1,4,2,5,6,16,4,11,3,28,8,12,18,8,10
http://www.research.att.com/~njas/sequences/A003572
Det ligner et generelt mønster, men helt sikre kan vi nok ikke være uden
bevis.

Mvh
Martin
--
Den pølse revner ikke, som er åben i begge ender