WisFaq!

Rangschik de getallen 1,2,...,n op een bijzondere manier

1. Bewijs dat je de getallen 1 t/m 32 zo kunt rangschikken dat voor elk tweetal getalen geen enkel getal dat ertussen staat gelijk is aan het rekenkundig gemiddelde van die twee getallen.
2. Kun je dit ook zo doen met getallen van 1 t/m 100?

naam
8-12-2003

Antwoord

Hoi,

Deze vraag loopt op Pythagoras nog tot 15 december 2003. Daarom een kleine vertraging in de publicatie van mijn antwoord.

We noteren een rij van n gehele getallen als: {a_i:i=1..n} of verkort {a_i}. Een rij {a_i} van n gehele getallen noemen we 'goed geordend' als ze de eigenschap heeft: a_k=(a_i+a_j)/2 Þ ki of kj. Bemerk dat het niet noodzakelijk om opeenvolgende getallen gaat en dat 1 er niet per se moet inzitten.

We bekijken het probleem met n elementen {1, 2, 3,…, n} en zoeken een goed geordende rij. We denken recursief: als we een eenvoudiger probleem opgelost hebben, kunnen we dit dan uitbreiden tot een complexer probleem (verdeel en heers - divide et impera)?

Een voor de hand liggende eerste poging is om van n naar n+1 elementen te proberen te gaan. Het is hoopgevend om in te zien dat we een goed geordende rij van {1,2,..,n+1} kunnen vereenvoudigen tot een goed geordende rij van {1,2,..,n} door n+1 te schrappen. Maar omgekeerd lopen we vast: {3, 5, 4, 1, 6, 2} is goed geordend, maar we kunnen 7 nergens toevoegen om uit te breiden tot een goed geordende rij van {1, 2, .., 7}… Pech…

Daarom een andere aanpak. Om na te gaan of een rij {a_i} welgeordend is, moeten we eigenlijk enkel de koppels van even en oneven getallen vergelijkingen met de positie van hun gemiddelde (voor andere koppels is het gemiddelde niet geheel). Als we dus een welgeordende deelrij {1, 3, 5, …} van oneven getallen n en een welgeordende deelrij {2, 4, 6,…} van even getallen n hebben, dan hebben we een oplosssing voor n door ze gewoon na elkaar te zetten. Als we {a_i}={1, 2,.., k} met kn goed kunnen ordenen, dan is {2.a_i} ook goed georderend. Hetzelfde geldt voor {2.a_i-1}. Ga maar na dat aan bovenstaande definitie voldaan is. Om de rij {1, 2, .., n} wel te ordenen moeten we dus gewoon de even en oneven rijen goed ordenen en samenplakken. Omdat we het met {1} kan, kan het dus recursief voor elke rij van getallen {1,2,..,n}; of n nu 32 of 100 is.

Om het allemaal netjes op te schrijven, noteren we het resultaat van bovenstaand algoritme {b_i} = p({a_i}) waarbij {b_i} dus goed geordend is. Met {a_i} || {b_i} bedoelen we dat we de elementen van {b_i} achter die van {a_i} zetten. We noteren: k.{a_i}= {k.a_i} en {a_i}+k ={a_i+k}.

Hierboven bewezen we dus volgende eigenschappen:
p({1, 2, .., n}) = p({oneven n}) || p({even n}) (of omgekeerd)
p({2.a_i}) = 2.p({a_i})
p({2.a_i-1}) = 2.p({a_i})-1
p({1})={1}

Voorbeeld voor n=7:
p({1,2,3,4,5,6,7}) =
p({1,3,5,7}) || p({2,4,6}) =
2.p({1,2,3,4})-1 || 2.p({1,2,3}) =

p({1,2,3,4}) =
p({1,3}) || p({2,4}) =
2.p({1,2})-1 || 2.p({1,2})

p({1,2,3}) =
p({1,3}) || p({2}) =
2.p({1,2})-1 || 2.p({1}) =
2.p({1,2})-1 || {2}

p({1,2}) =
p({1}) || p({2}) =
{1} || 2.p({1}) =
{1} || {2} =
{1,2}

zodat:
p({1,2,3}) = 2.{1,2}-1 || {2} = {1,3} || {2} = {1,3,2}
p({1,2,3,4}) = 2.{1,2}-1 || 2.{1,2} = {1,3} || {2,4} = {1,3,2,4}
p({1,2,3,4,5,6,7}) = 2.{1,3,2,4}-1 || 2. {1,3,2} = {1,5,3,7} || {2,6,4} = {1,5,3,7,2,6,4}

Groetjes,
Johan

Iets anders geformuleerd, met dank aan collega CL:

Stelling 1: Als x(n) een rij is die voldoet aan de gevraagde eigenschap, dan voldoet de rij kx(n) (k niet nul) ook aan die eigenschap, aangezien ook alle gemiddelden dan met k worden vermenigvuldigd.
Stelling 2: Als x(n) een rij is die voldoet aan de gevraagde eigenschap, dan voldoet de rij
x(n)+m ook aan die eigenschap, aangezien ook alle gemiddelden dan met m worden vermeerderd.
Stelling 3: Als x(n) en y(n) twee rijen zijn die voldoen aan de gevraagde eigenschap, en de ene bestaat enkel uit even termen en de andere enkel uit oneven termen, dan voldoet ook de rij die ontstaat door die twee rijen achter elkaar te plaatsen. Immers, de koppels die bestaan uit een element van de ene rij en een element van de andere rij geven aanleiding tot een gemiddelde dat niet-geheel is en dus onmogelijk ergens in de rij kan voorkomen.
Stelling 4: Als x(n) een rij is die voldoet aan de gevraagde eigenschap, dan voldoet ook elke deelrij aan de eigenschap, aangezien het weglaten van termen niet het ineens te voorschijnkomen van een bepaald gemiddelde kan teweegbrengen.

Begin met een rij die duidelijk aan de eigenschap voldoet

1,2 - 2,4 en 1,3 (Stelling 1 (k=2) en Stelling 1+2 (m=-1)) - 2,4,1,3 (Stelling 3)

Het is duidelijk dat door m=-1 te kiezen de gaten worden opgevuld die ontstaan door het vermenigvuldigen met 2. Laten we de tussenstap weg, dan bekom je de vervolgens ook

- 4, 8, 2, 6, 3, 7, 1, 5
- 8, 16, 4, 12, 6, 14, 2, 10, 7, 15, 3, 11, 5, 13, 1, 9
- 16, 32, 8, 24, 12, 28, 4, 20, 14, 30, 6, 22, 10, 26, 2, 18, 15, 31, 7, 23, 11, 27, 3, 19, 13, 29, 5, 21, 9, 25, 1, 17

Stelling 4 geeft de oplossing op de tweede vraag: construeer op dezelfde manier een rij van 128 elementen en laat de termen 101 tot en met 128 gewoon weg.

andros
16-12-2003