Het rekenspelletje diffy wordt gebruikt om kinderen te leren aftrekken, en hen tegelijkertijd te leren om logisch na te denken en patronen te herkennen. Het kan gespeeld worden met gehele getallen, breuken, reële getallen en geldbedragen, maar meestal wordt gewerkt met natuurlijke getallen.

Spelbord waarop het spelletje diffy gespeeld word.

Het spelletje begint met het invullen van vier willekeurige getallen in de vier cirkels op de buitenste hoekpunten. Daarna moeten de buitenste vierkanten ingevuld worden door telkens het kleinste getal af te trekken van het grootste getal op de twee naburige hoekpunten. Deze procedure waarbij naburige hoekpunten van elkaar afgetrokken worden en steeds naar binnen toe gewerkt wordt, moet telkens herhaald worden. Zie je een bepaald patroon ontstaan? Kan je het midden bereiken zonder een verschil te krijgen dat nul oplevert?

Volledig ingevuld voorbeeld van een spelletje diffy.

Hierboven staat een volledig ingevuld voorbeeld van een spelletje diffy. Zoals je kan zien is de speler niet gewonnen, omdat de vier cirkels die het dichtst bij het centrum gelegen zijn allemaal nullen bevatten. Is het überhaupt mogelijk om dit spelletje te winnen?

Opgave

Het spelletje diffy is een speciaal geval van een Ducci-reeks, vernoemd naar de Italiaanse wiskundige Enrico Ducci aan wie de ontdekking van de reeks wordt toegeschreven. Voor een gegeven reeks van $$n$$ natuurlijke getallen $$(a_1, a_2, \ldots, a_n)$$ wordt de volgende reeks van $$n$$ getallen gevormd door de absolute waarde te nemen van het verschil van de opeenvolgende getallen: \[(a_1, a_2, \ldots, a_n) \rightarrow (|a_1 - a_2|, |a_2 - a_3|, \ldots, |a_{n - 1} - a_n|, |a_n - a_1|)\] Hierbij wordt dus verondersteld dat het laatste getal terug gevolgd wordt door het eerste getal. De Ducci-reeks kan dus ook als volgt omschreven worden. Plaats $$n$$ natuurlijke getallen op een cirkel en maak een nieuwe cirkel door het verschil van elke twee naburige getallen te bepalen, waarbij het teken genegeerd wordt. Blijf deze procedure herhalen.

Omdat elke Ducci-reeks van natuurlijke getallen uiteindelijk zichzelf zal herhalen (een eigenschap die makkelijk kan bewezen worden), wordt gezegd dat Ducci-reeksen periodiek zijn. Een Ducci-reeks levert uiteindelijk immers een reeks van $$n$$ natuurlijke getallen op die allemaal nul zijn (periode is gelijk aan 0), of een reeks van $$n$$ natuurlijke getallen die reeds eerder in de Ducci-reeks voorkwam (periode is gelijk aan het aantal reeksen van $$n$$ natuurlijke getallen waarna terug herhaling optreedt). Beschouw bijvoorbeeld de volgende Ducci-reeks: \[\begin{matrix} (1, 2, 1, 2, 1, 1) & \rightarrow & \mathbf{(1, 1, 1, 1, 0, 0)} & \rightarrow & \mathbf{(0, 0, 0, 1, 0, 1)} & \rightarrow \\ \mathbf{(0, 0, 1, 1, 1, 1)} & \rightarrow & \mathbf{(0, 1, 0, 0, 0, 1)} & \rightarrow & \mathbf{(1, 1, 0, 0, 1, 1)} & \rightarrow \\ \mathbf{(0, 1, 0, 1, 0, 0)} & \rightarrow & (1, 1, 1, 1, 0, 0) & \rightarrow & \cdots & \\ \end{matrix}\] De eerste herhaling treedt op als het tuple $$(1, 1, 1, 1, 0, 0)$$ voor de tweede keer in de reeks opduikt. Om dit te onderstrepen hebben we alle tuples uit de Ducci-reeks die deel uitmaken van de eerste periode in het vet gezet. De periode kan dus bepaald worden als het aantal stappen die nodig zijn om vanaf het eerste voorkomen van het tuple $$(1, 1, 1, 1, 0, 0)$$ voor het eerst terug het tuple $$(1, 1, 1, 1, 0, 0)$$ te bekomen. In dit geval is de periode dus gelijk aan zes. Gevraagd wordt:

Schrijf een functie volgende waaraan een reeks (list of tuple) van $$n \in \mathbb{N}_0$$ natuurlijke getallen (int) moet doorgegeven worden. De functie moet het tuple van $$n$$ natuurlijke getallen (int) teruggeven dat in een Ducci-reeks volgt op de gegeven reeks getallen.
Schrijf een functie ducci waaraan een reeks (list of tuple) van $$n \in \mathbb{N}_0$$ natuurlijke getallen (int) moet doorgegeven worden. De functie moet een nieuwe reeks (tuple) teruggeven die begint bij het tuple dat de gegeven reeks van $$n$$ natuurlijke getallen voorstelt, en telkens gevolgd wordt door het volgende tuple van $$n$$ natuurlijke getallen uit de Ducci-reeks. De reeks eindigt wanneer het laatste tuple allemaal nullen bevat of reeds eerder in de Ducci-reeks voorkwam.
Schrijf een functie periode waaraan een reeks (list of tuple) van $$n \in \mathbb{N}_0$$ natuurlijke getallen (int) moet doorgegeven worden. De functie moet de periode (int) teruggeven van de Ducci-reeks die begint met de gegeven reeks van $$n$$ natuurlijke getallen.

Voorbeeld

>>> volgende([32, 9, 14, 3])
(23, 5, 11, 29)
>>> volgende((1, 2, 1, 2, 1, 0))
(1, 1, 1, 1, 1, 1)
>>> volgende((1, 2, 1, 2, 1, 1))
(1, 1, 1, 1, 0, 0)

>>> ducci([32, 9, 14, 3])
((32, 9, 14, 3), (23, 5, 11, 29), (18, 6, 18, 6), (12, 12, 12, 12), (0, 0, 0, 0))
>>> ducci((1, 2, 1, 2, 1, 0))
((1, 2, 1, 2, 1, 0), (1, 1, 1, 1, 1, 1), (0, 0, 0, 0, 0, 0))
>>> ducci((1, 2, 1, 2, 1, 1))
((1, 2, 1, 2, 1, 1), (1, 1, 1, 1, 0, 0), (0, 0, 0, 1, 0, 1), (0, 0, 1, 1, 1, 1), (0, 1, 0, 0, 0, 1), (1, 1, 0, 0, 1, 1), (0, 1, 0, 1, 0, 0), (1, 1, 1, 1, 0, 0))

>>> periode([32, 9, 14, 3])
0
>>> periode((1, 2, 1, 2, 1, 0))
0
>>> periode((1, 2, 1, 2, 1, 1))
6