Het probleem

We willen de $10$ getallen ($1$ tot en met $10$) in een cirkel plaatsen. 

1. Hoe plaats je deze getallen zodat het maximum van alle sommen van drie opeenvolgende getallen minimaal is? 
2. Hoe plaats je deze getallen zodat alle sommen van drie opeenvolgende getallen verschillend zijn en dat het verschil van de grootste en kleinste som zo klein mogelijk is?
3. Hoeveel verschillende oplossingen zijn er bij a. en b.?

 

Uiteraard is de keuze voor $10$ getallen arbitrair. Hieronder gaan we daarom uit van de getallen ($1$ tot en met $n$) in een cirkel voor verschillende waarden van $n$. Laten we eerst kijken naar $n = 3$. De som van de getallen $1$, $2$ en $3$ is $6$. Dit levert tevens het antwoord van a. en b. 

Nu kijken we naar $n = 4$. De volgorde van de getallen maakt niet zoveel uit. Door drietallen te maken wordt steeds een getal uitgesloten. De vier sommen zijn $6$, $7$, $8$ en $9$. Het maximum van a. is $9$ en de verschillende sommen lopen van $6$ tot en met $9$.

Eerste waarnemingen

We gaan nu uit van $n > 4$. Om te beginnen bepalen we het aantal volgordes dat moet worden getest. Je kunt $n$ getallen in $n!$ volgordes plaatsen, maar omdat de getallen in een cirkel staan mag één van de getallen worden gefixeerd (zeg $n$). Daarnaast heb je dezelfde sommen als je de getallen in de andere richting leest. Daarom mag je vaststellen dat er rechts van $n$ een groter getal staat dan links. Het aantal mogelijkheden dat moet worden bekeken is $(n - 1)!/2$.

Laten we de $n$ getallen eens bij elkaar optellen. De som is $n(n + 1)/2$. We kunnen deze som met $3$ vermenigvuldigen. Dit is de som van alle drietallen: $3n(n + 1)/2$. Tenslotte delen we dit aantal door $n$ om het gemiddelde te krijgen van de sommen van drie getallen: $3(n + 1)/2$. Om bij b. $n$ opeenvolgende sommen te krijgen, moeten die sommen $n + 2, n + 3, \ldots, 2n + 1$ zijn. De som van deze $n$ sommen is immers precies gelijk aan de som van alle drietallen in de cirkel. 

Laten we voor het maximum $m$ van onderdeel a. veronderstellen dat er drie getallen in de cirkel naast elkaar staan, $a$, $b$ en $c$, zó dat $a + b + c = m$. Dan is  duidelijk dat voor en achter deze drie getallen maximaal een getal kan staan zo dat de som $m - 1$ is. In dit optimale geval hebben we $c - 1$, $a$, $b$, $c$ en $a - 1$. Aan een van beide zijden kan $b + 1$ worden geplaatst, zeg rechts. Dan kan links hooguit $b - 1$ worden geplaatst (er van uitgaande dat de rij getallen lang genoeg is).
We hebben nu $b - 1$, $c - 1$, $a$, $b$, $c$, $a - 1$ en $b + 1$. De conclusie is dat je steeds meer van het gemiddelde gaat afwijken. 

Aan de slag

De programmatuur vind je hieronder onder de knop [Oplossing].

 

$\color{white}{n}$		$\color{white}{minmax}$		$\color{white}{\#opl}$		$\color{white}{voorbeeld}$		$\color{white}{sommen}$		$\color{white}{\#opl}$		$\color{white}{voorbeeld}$		$\color{white}{tijd}$
$3$		$6$		$1$		$[1,2,3]$		$6$		$1$		$[1,2,3]$		$0{,}00001$
$4$		$9$		$3$		$[1,2,3,4]$		$6 \ldots 9$$		$3$		$[1,2,3,4]$		$0{,}00005$
$5$		$10$		$2$		$[1,4,2,3,5]$		$7 \ldots 11$		$1$		$[2,4,1,3,5]$		$0{,}0002$
$6$		$11$		$1$		$[1,4,5,2,3,6]$		$8 \ldots 13$		$12$		$[1,2,5,3,4,6]$		$0{,}001$
$7$		$14$		$48$		$[1,2,5,6,3,4,7]$		$9 \ldots 15$		$9$		$[1,2,6,5,4,3,7]$		$0{,}0081$
$8$		$15$		$20$		$[1,5,6,2,7,3,4,8]$		$10 \ldots 17$		$132$		$[1,2,7,3,6,4,5,8]$		$0{,}025$
$9$		$16$		$8$		$[1,5,8,2,6,7,3,4,9]$		$11 \ldots 19$		$97$		$[1,2,8,3,5,7,6,4,9]$		$0{,}13$
$10$		$18$		$27$		$[1,4,9,5,3,7,8,2,6,10]$		$12 \ldots 21$		$824$		$[1,2,9,3,4,8,7,5,6,10]$		$1{,}64$
$11$		$20$		$806$		$[1,5,4,10,6,3,8,9,2,7,11]$		$13 \ldots 23$		$1050$		$[1,2,10,3,5,9,6,7,8,4,11]$		$12$

Bekijken we de kolom minmax, dan zien we een rij die in de On-Line Encyclopedia of Integer Sequences voorkomt. Daar kun je ook uitgebreid lezen over de origine van het probleem.

Opgave 1 Kun je inschatten hoeveel tijd het programma kwijt is voor waarden boven $n = 11$? Wat lukt nog binnen een dag rekentijd? Opgave 2 Het lijkt erop dat het altijd mogelijk is om de getallen $1$ tot en met $n$ dusdanig in een cirkel te plaatsen zo dat alle mogelijke sommen tussen $n + 2$ en $2n + 1$ gemaakt worden. Kun je bedenken hoe je het programma kunt aanpassen om ook voor grotere waarden van $n$ een oplossing te vinden, zonder alle mogelijke oplossingen te hoeven berekenen?

 

Bekijk oplossing