\require{AMSmath}

Oneindig schaakbord

De Opdracht is:
Op een naar rechts en naar boven oneindig doorlopend schaakbord worden gehele getallen groter of gelijk aan 0 in de velden gezet, zo dat het getal in veld (m,n) het kleinste is dat nog niet is gebruikt is op de velden (m,i) met in en (j,n) met jm. Welk getal staat er op (1000,100)?
Ik dacht eerst dat het antwoord 1998 was, maar dat bleek niet goed. Nu heb ik het idee dat het als volgt werkt:

[9]   8   9  10  11  12  13  14  15
[8]   7   6   5   4   3   2   1   0
[7]   6   7   4   5   2   3   0   1
[6]   5   4   7   6   1   0   3   2
[5]   4   5   6   7   0   1   2   3 
[4]   3   2   1   0   7   6   5   4 
[3]   2   3   0   1   6   7   4   5
[2]   1   0   3   2   5   4   7   6 
[1]   0   1   2   3   4   5   6   7 
     [1] [2] [3] [4] [5] [6] [7] [8]

(de getallen tussen [ ] zijn m of n)
Hier in zag ik allemaal regelmatige kubussen die zich op een bepaalde manier herhaalde bijv: 01
10 , Deze loopt over de diagonaal
Maar deze kan ik groter maken tot 4 bij 4
3210
2301
1032
0123
Ook deze loopt over de diagonaal. Zo kan ik elke keer die kubussen vergroten. 8 bij 8, 16 bij 16. Daarnaast is het zo als ik bijvoorbeeld de 4 bij 4kubus links onder in neemt, staat daarboven een 4bij 4 kubus die ook links van de eerst genoemde staat.
Ik denk dat op (1000,100) het getal 900 staat. Mijn vraag is hoe verklaar ik al die regelmaat, hoe weet ik zo zeker dat dat overal opgaat, waar komt het vandaan. Ik hoop dat je mij daar me kunt helpen.
Alvast bedankt, Tiene

tiene
Student universiteit - maandag 15 november 2004

Antwoord

dag Tiene, Jantine, Janneke

Anneke verontschuldigt zich voor het foute antwoord op deze al eerder gestelde vraag.
In dat antwoord werd onterecht uitgegaan van de voorwaarde:
Het getal in (m,n) is het kleinste dat nog niet gebruikt is in de velden (i,j) waarbij i$<$m en j$<$n.

Het probleem is veel ingewikkelder.

·Onmiddellijk is wel duidelijk dat er symmetrie is rond de diagonaal met nullen, in de definitie kan de rol van m en n omgewisseld worden.

·De periodiciteit die je opmerkte is er volgens mij inderdaad.

Neem bvb het 2 x 2-vierkant linksonder. Omdat daar alle getallen kleiner dan 2 in voorkomen, in alle kolommen en rijen, staat erboven en ernaast hetzelfde 2 x 2-vierkant modulo 2 maar met representanten 2 hoger, dus met 2 en 3.
In het vierde deel van het grotere 4 x 4-vierkant staat dan weer hetzelfde dan linksonder, omdat die getallen nu juist niet meer voorkomen ter hoogte van die rijen/kolommen.

Per inductie kan je dit systeem voortzetten: het exacte bewijs wordt gegeven per inductie op n $\in$ $\mathbf{N}$, voor een 2ⁿ x 2ⁿ-vierkant.
We willen bewijzen dat
(1) in elk 2ⁿ x 2ⁿ-vierkant in elke rij en kolom alle getallen van 0 t.e.m. 2ⁿ-1 staan
(2) wanneer we het vierkant in 4 gelijke delen verdelen (horizontaal en verticaal doormidden) in de vierkanten linksonder en rechtsboven de getallen 0 t.e.m. 2^n-1-1 staan en in de andere twee vierkanten de getallen 2^n-1 t.e.m. 2ⁿ-1
(3) de 4 deelvierkanten gelijk zijn modulo 2^n-1

bewijs:

·start n=1: het 2 x 2-vierkant linksonder: triviaal OK
·veronderstel OK voor n-1 (3 puntjes dus)
TB: OK voor n
bew:
-verdeel het 2ⁿ x 2ⁿ-vierkant is de vier gelijke delen.
-linksonder staat volgens de inductiehypothese een 2^n-1 x 2^n-1-vierkant met in elke rij en kolom de getallen 0 t.e.m. 2^n-1-1.
Omdat in elke rij of kolom al die getallen voorkomen, kunnen in de deelvierkanten erboven en ernaast die getallen niet meer voorkomen.
Verder is daar echter de opbouw van het deelvierkant (uit de manier waarop we het schaakbord vullen) net hetzelfde als linksonder, maar dus met alle getallen 2^n-1 hoger. Het is dus hetzelfde modulo 2^n-1.
Eveneens staan er in elke rij en kolom alle getallen, nu 2^n-1 hoger, dus 2^n-1 t.e.m. 2ⁿ-1.
Omdat in de 2 vorig besproken vierkanten de getallen 0 t.e.m. 2^n-1-1 niet voorkomen, kan in het laatste vierkant rechtsboven nu hetzelfde geplaatst worden als linksonder (de opbouw van het schaakbord maakt dat dit hetzelfde is).
Het is dus duidelijk uit het voorgaande dat de puntjes OK zijn.

Het bewijs is dus eigenlijk een constructie, een figuur kan het misschien duidelijker maken.

·Voor het vervolg zal ik de rijen en kolommen in de matrix niet nummeren vanaf 1, maar vanaf 0 omdat dat gemakkelijker zal uitkomen.
Om de waarde op plaats (m,n) te zoeken, vb (999,99) (dit is eigenlijk de gezochte (1000,100), tellen vanaf 0):
-grootste vierkant 1024 x 1024, verdeel dit in 4, we zitten in het deel linksboven want 999 is groter dan of gelijk aan 512 en 99 is kleiner dan 512, dus oplossingen 512 tot 1023 zijn mogelijk.
-zo ga je steeds verder, nu in het kleinere vierkant...
-Om gemakkelijker het getal te bepalen: schrijf 999 en 99 binair! Begin nu links te kijken in de rij nullen en eentjes die je krijgt.
Staat er 2 keer hetzelfde (0 of 1), dan behoort het getal tot de kleinste helft van de overgebleven getallen; 2 verschillende: tot de grootste helft (denk na..., vergeet mijn aangepaste nummering 'tellen vanaf 0' niet)
of: als 'som' van die digit in 999-binair en 99-binair 1 is (=2 verschillende), dan grootste helft, als 'som' 0 is (2=0, binair tellen), dan kleinste helft;
of: als 'som' 1: oplossing+2^n-1 (als het deel van de getallen in een n x n-vierkant gezocht wordt), als 'som' 0:tel niets erbij op;
of: maak de binaire 'som'! (maar dus zonder 'overzetten' naar de volgende rang).

jouw vb: op plaats (1000,100) (wordt (999,99) bij mij):
binair: 999=1111100111 binair 'optellen' bij 99=0001100011 levert 1110000100 of decimaal: 900.

Joeri
dinsdag 16 november 2004

©2001-2024 WisFaq