/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Ombytning af bogstaver
Fra : Steen


Dato : 11-01-06 16:27

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



 
 
Jens Axel Søgaard (11-01-2006)
Kommentar
Fra : Jens Axel Søgaard


Dato : 11-01-06 17:09

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

Kim Jensen (11-01-2006)
Kommentar
Fra : Kim Jensen


Dato : 11-01-06 20:50

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

Martin Larsen (11-01-2006)
Kommentar
Fra : Martin Larsen


Dato : 11-01-06 22:37

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


Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste