Blokken bepaald door de grootste frequentie

Geplaatst op 31 augustus 2026 door admin

De eerste 2026 functiewaarden mogen volledig willekeurig zijn. Toch dwingt het voorschrift daarna steeds langere blokken van gelijke waarden af. De lengte van zo’n blok levert precies de afstand die in de gevraagde gelijkheid voorkomt.

Infobox

Onderwerpen: Functies, combinatoriek, rijen
Probleemoplossingstechnieken: Kleine gevallen onderzoeken, frequenties tellen, blokken herkennen, invariant gebruiken
Moeilijkheid: Moeilijk
Competitie: Indian National Mathematical Olympiad, finale
Jaar: 2026
Opgavenummer: 2

Opgave

Laat $f:\mathbb N\to\mathbb N$ een functie zijn met de volgende eigenschap: voor elke $k>2026$ is $f(k)$ gelijk aan het grootste aantal keer dat een getal voorkomt in de lijst

$f(1),f(2),\ldots,f(k-1).$

Bewijs dat voor oneindig veel $n\in\mathbb N$ geldt

$f(n)=f(n+f(n)).$

Hierbij is $\mathbb N=\{1,2,3,\ldots\}$ de verzameling van de positieve gehele getallen.

Eerste idee

Vervang $2026$ eerst door $4$ . Na vier willekeurige beginwaarden wordt telkens de huidige grootste frequentie toegevoegd. Zodra die frequentie $m$ is, blijft de waarde $m$ verschijnen totdat de grootste frequentie $m+1$ wordt. Voor alle voldoende grote $m$ levert dit een blok van precies $m+1$ gelijke waarden op.

Observatieronde

Een kleine versie met drempel 4

De eerste $2026$ functiewaarden mogen willekeurig zijn. Om het voorschrift zichtbaar te maken, vervangen we $2026$ tijdelijk door $4$ en kiezen we bijvoorbeeld

$f(1),f(2),f(3),f(4)=2,1,2,7.$

In deze lijst komt $2$ tweemaal voor; geen enkel getal komt vaker voor. Daarom is $f(5)=2$ . Nu komt $2$ driemaal voor, zodat $f(6)=3$ . Het getal $3$ kwam nog niet voor en moet vervolgens viermaal worden toegevoegd voordat zijn frequentie $4$ wordt. Daarna wordt $4$ vijfmaal toegevoegd en $5$ zesmaal. De vier beginwaarden zijn zwart; alle waarden die het voorschrift daarna toevoegt, zijn rood:

$2,1,2,7\mid$
$2\mid \underbrace{3,3,3,3}_{4\text{ keer}}\mid \underbrace{4,4,4,4,4}_{5\text{ keer}}\mid \underbrace{5,5,5,5,5,5}_{6\text{ keer}}\mid \underbrace{6,6,6,6,6,6,6}_{7\text{ keer}}\mid\cdots$

In het blok met vier drieën werkt de eerste positie $n=6$ :

$f(6)=3=f(9)=f(6+f(6)).$

In het volgende blok werkt de eerste positie $n=10$ , want $f(10)=4=f(14)$ . Ook $n=15$ en $n=21$ werken. De beginwaarde $7$ zorgt later voor een uitzondering: het blok met zevens loopt van positie $28$ tot en met $34$ en is dus één plaats te kort. Het volledige blok met achten begint op positie $35$ . Elk volgend volledig blok met waarde $m$ begint $m$ plaatsen na het begin van het vorige blok; daaruit volgt dat zijn beginpositie $\frac{m(m+1)}2-1$ is. In dit voorbeeld zijn alle oplossingen daarom

$\boxed{n\in\{1,3,6,10,15,21\}\ \text{ of }\ n=\frac{m(m+1)}2-1\text{ voor }m\geq8.}$

De waarden $n=1$ en $n=3$ komen toevallig uit de gekozen beginwaarden. Het algemene bewijs hoeft zulke vroege toevalligheden niet te beschrijven: het moet aantonen dat er na willekeurige beginwaarden altijd oneindig veel volledige blokken ontstaan.

Twee voorbeelden met drempel 5

Eerst nemen we vijf verschillende beginwaarden: $1,2,3,4,5$ .

Posities	Waarden	Wat gebeurt er?
$1$ – $5$	$1,2,3,4,5$	vijf verschillende beginwaarden
$6$ – $20$	$1,2,2,3,3,3,4,4,4,4,5,5,5,5,5$	elk getal $1$ tot en met $5$ kwam al eenmaal voor; zijn rode blok is daardoor te kort
$21$ – $27$	$6,6,6,6,6,6,6$	$6$ is nieuw, dus dit is een volledig blok van $7$ zessen

Hier werkt $n=21$ , want $f(21)=6=f(27)=f(21+6)$ . Daarna zijn ook alle volgende blokken volledig.

Neem nu als beginwaarden $2,2,2,5,6$ .

Posities	Waarden	Wat gebeurt er?
$1$ – $5$	$2,2,2,5,6$	de grootste frequentie is $3$
$6$ – $9$	$3,3,3,3$	volledig blok; $n=6$ werkt
$10$ – $14$	$4,4,4,4,4$	volledig blok; $n=10$ werkt
$15$ – $19$	$5,5,5,5,5$	te kort, want er stond al een $5$ bij de beginwaarden
$20$ – $25$	$6,6,6,6,6,6$	te kort, want er stond al een $6$ bij de beginwaarden
$26$ – $33$	$7,7,7,7,7,7,7,7$	weer een volledig blok; $n=26$ werkt

Dit voorbeeld toont waarom we in het algemene bewijs alleen naar waarden kijken die groter zijn dan alle beginwaarden.

De juiste grootheid

Voor $k\geq1$ en $a\in\mathbb N$ noteren we met

$c_k(a)=\bigl|\{i\in\{1,\ldots,k\}:f(i)=a\}\bigr|$

het aantal voorkomens van $a$ onder de eerste $k$ functiewaarden. Verder stellen we

$M_k=\max_{a\in\mathbb N}c_k(a).$

Dit maximum bestaat, want in een eindige lijst komen slechts eindig veel verschillende waarden voor. Het gegeven voorschrift wordt nu

$f(k+1)=M_k\qquad(k\geq2026).$

Uitwerking

Stap 1: de grootste frequentie loopt door alle volgende getallen

Wanneer één nieuwe functiewaarde aan de lijst wordt toegevoegd, neemt precies één frequentie met $1$ toe. Daarom geldt voor iedere $k\geq1$

$M_k\leq M_{k+1}\leq M_k+1.$

Stel nu dat $k\geq2026$ en $M_k=m$ . Zolang het maximum gelijk blijft aan $m$ , schrijft het voorschrift telkens opnieuw de waarde $m$ voor. De frequentie van $m$ neemt dus bij elke volgende stap met $1$ toe.

Op het tijdstip $k$ komt het getal $m$ hoogstens $m$ keer voor. Door telkens opnieuw $m$ toe te voegen, komt $m$ na precies

$m+1-c_k(m)$

nieuwe stappen voor het eerst $m+1$ keer voor. Dan wordt de grootste frequentie $m+1$ . Zo gaat de grootste frequentie na een eindig aantal stappen van $m$ naar $m+1$ , zonder een getal over te slaan.

Stap 2: alle voldoende grote waarden vormen volledige blokken

Stel

$r=M_{2026}$

en laat $B$ de grootste waarde onder $f(1),\ldots,f(2026)$ zijn. Uit stap 1 volgt dat de maximale frequentie vanaf $r$ achtereenvolgens de waarden

$r,r+1,r+2,\ldots$

aanneemt.

Neem een geheel getal $m>\max\{B,r\}$ , en laat $t_m$ de eerste index $k\geq2026$ zijn waarvoor $M_k=m$ . Het getal $m$ is dan nog nooit als functiewaarde voorgekomen:

het kwam niet onder de eerste $2026$ waarden voor, want $m>B$ ;
na de eerste $2026$ posities werden vóór het bereiken van maximale frequentie $m$ alleen de waarden $r,r+1,\ldots,m-1$ toegevoegd.

Dus $c_{t_m}(m)=0$ . Vanaf de volgende positie schrijft het voorschrift steeds $m$ . Pas na $m+1$ kopieën komt $m$ precies $m+1$ keer voor en stijgt de grootste frequentie. We krijgen dus het volledige blok

$f(t_m+1)=f(t_m+2)=\cdots=f(t_m+m+1)=m.$

Stap 3: kies de eerste positie van elk volledig blok

Voor ieder $m>\max\{B,r\}$ kiezen we

$n=t_m+1.$

Deze $n$ is de eerste positie van het blok. De laatste positie ligt $m$ plaatsen verder. Omdat $f(n)=m$ , is

$n+f(n)=t_m+1+m=t_m+m+1,$

de laatste positie van hetzelfde blok. Daarom geldt

$f(n)=m=f(n+f(n)).$

Er zijn oneindig veel gehele getallen $m>\max\{B,r\}$ , en hun blokken hebben verschillende eerste posities. We vinden zo oneindig veel verschillende positieve gehele getallen $n$ waarvoor

$\boxed{f(n)=f(n+f(n))}.$

Probleemoplossingstechnieken

Kleine gevallen onderzoeken: De drempel $4$ toont hoe opeenvolgende blokken ontstaan.
Frequenties tellen: De aantallen $c_k(a)$ vertalen het voorschrift naar precieze notatie.
Blokken herkennen: Zodra het maximum $m$ is, wordt uitsluitend $m$ toegevoegd totdat de maximale frequentie stijgt.
Invariant gebruiken: De maximale frequentie daalt nooit en stijgt per stap met hoogstens $1$ .

Bron

40th Indian National Mathematical Olympiad, 18 januari 2026. © Indian National Mathematical Olympiad.

Wanneer belandt de rij op een kwadraat?

Geplaatst op 24 augustus 2026 door admin

Een rij groeit telkens met het gehele deel van de vierkantswortel van haar laatste term. Door eerst veel termen uit te rekenen, wordt zichtbaar waarom sommige kwadraten wel worden geraakt en andere net worden overgeslagen. Daarna bewijzen we het patroon stap voor stap.

Infobox

Onderwerpen: Rijen, getaltheorie
Probleemoplossingstechnieken: Beginwaarden berekenen, regelmaat zoeken, werken met intervallen, hulpvariabele invoeren, inductie
Moeilijkheid: Moeilijk
Competitie: Indian National Mathematical Olympiad, finale
Jaar: 2026
Opgavenummer: 1

Opgave

Laat $x_1,x_2,x_3,\ldots$ een rij van positieve gehele getallen zijn, als volgt gedefinieerd: $x_1=1$ en voor elke $n\geq 1$ geldt

$x_{n+1}=x_n+\lfloor\sqrt{x_n}\rfloor.$

Bepaal alle positieve gehele getallen $m$ waarvoor $x_n=m^2$ voor een zekere $n\geq 1$ . Hierbij stelt $\lfloor x\rfloor$ voor elk reëel getal $x$ het grootste gehele getal voor dat kleiner dan of gelijk aan $x$ is.

Eerste idee

Tussen $k^2$ en $(k+1)^2$ neemt de rij telkens met $k$ toe. Om precies op $k^2$ te belanden, moet daarom eerst de term $k^2-(k-1)$ voorkomen. De beginwaarden tonen dat dit bij $k=1,2,4,8,16,\ldots$ lukt. We meten vervolgens bij elk kwadraat hoeveel de rij dat kwadraat heeft overschreden.

Observatieronde

De eerste termen

We berekenen eerst een stuk van de rij. De kwadraten zijn rood weergegeven:

$1$ , $2$ , $3$ , $4$ , $6$ , $8$ , $10$ , $13$ , $16$ , $20$ , $24$ , $28$ , $33$ , $38$ , $44$ , $50$ , $57$ , $64$ , $72$ , $80$ , $88$ , $97$ , $106$ , $116$ , $126$ , $137$ , $148$ , $160$ , $172$ , $185$ , $198$ , $212$ , $226$ , $241$ , $256$ , $272$ , $288$ , $304$ , $321$ , $338$ , $356$ , $374$ , $393$ , $412$ , $432$ , $452$ , $473$ , $494$ , $516$ , $538$ , $561$ , $584$ , $608$ , $632$ , $657$ , $682$ , $708$ , $734$ , $761$ , $788$ , $816$ , $844$ , $873$ , $902$ , $932$ , $962$ , $993$ , $1024$ , $\ldots$

De eerste kwadraten in de rij zijn

$1=1^2,\qquad4=2^2,\qquad16=4^2,\qquad64=8^2,\qquad256=16^2,\qquad1024=32^2.$

Eerste vaststellingen

Tussen twee opeenvolgende kwadraten is de stapgrootte constant. Als $k^2\leq x_n<(k+1)^2$ , neemt de rij telkens met $k$ toe. Tussen $16$ en $25$ zien we $16,20,24,28$ . Tussen $25$ en $36$ zien we $28,33,38$ .
Om op $k^2$ te belanden, moet de juiste term vlak ervoor voorkomen. Die term is $k^2-(k-1)$ . Voor $16$ is dat $13$ , en die term komt voor. Voor $25$ zou $21$ moeten voorkomen, maar de rij gaat van $20$ naar $24$ en dan naar $28$ . Voor $36$ zou $31$ nodig zijn, maar de rij gaat van $28$ naar $33$ en dan naar $38$ .
Bij machten van $2$ lukt dit, bij de andere waarden niet. Voor $k=4$ staat $13=16-3$ in de rij en voor $k=8$ staat $57=64-7$ in de rij. Voor $k=5,6,7$ ontbreken respectievelijk $21,31,43$ , zodat $25,36,49$ niet voorkomen.

Nu bewijzen we deze waarnemingen.

Uitwerking

Stap 1: de rij bereikt elk interval tussen twee kwadraten

De rij is strikt stijgend, want elke stap is minstens $1$ . Ze is daardoor ook onbegrensd.

Neem $k\geq2$ en kijk naar de eerste rijterm die minstens $k^2$ is. De term vlak ervoor is kleiner dan $k^2$ , zodat de stap vanuit die term hoogstens $k-1$ bedraagt. De eerste term die minstens $k^2$ is, is dus hoogstens

$(k^2-1)+(k-1)=k^2+k-2<(k+1)^2.$

Er ligt bijgevolg minstens één rijterm in elk interval $[k^2,(k+1)^2)$ .

Stap 2: binnen zo’n interval zijn alle stappen gelijk

Als $k^2\leq x_n<(k+1)^2$ , dan is $k\leq\sqrt{x_n}<k+1$ . Dus $\lfloor\sqrt{x_n}\rfloor=k$ , en $x_{n+1}=x_n+k$ .

Stap 3: wanneer wordt een kwadraat bereikt?

De term vlak vóór $k^2$ ligt volgens stap 1 in $[(k-1)^2,k^2)$ . Volgens stap 2 is de volgende stap dan $k-1$ . Daarom kan $k^2$ alleen worden bereikt vanuit $k^2-(k-1)$ . Omgekeerd: als deze term voorkomt, is de volgende term inderdaad $k^2$ .

Stap 4: de eerste term na elk kwadraat volgen

Schrijf de eerste rijterm in $[k^2,(k+1)^2)$ als $k^2+a_k$ . De waarde $a_k$ meet hoeveel de rij $k^2$ heeft overschreden. We hebben $a_1=0$ , en voor $k\geq2$

$0\leq a_k\leq k-2.$

Er zijn twee gevallen.

Geval 1: $a_k=0$ . Vanuit $k^2$ zijn drie stappen van grootte $k$ nodig om voor het eerst minstens $(k+1)^2=k^2+2k+1$ te bereiken:

$k^2,\quad k^2+k,\quad k^2+2k,\quad k^2+3k.$

Omdat $k^2+3k=(k+1)^2+(k-1)$ , geldt $a_{k+1}=k-1$ . Zo krijgen we vanuit $16$ de termen $20,24,28$ , en dus $a_5=3$ .

Geval 2: $a_k>0$ . Omdat $1\leq a_k\leq k-2$ , is één stap niet genoeg om $(k+1)^2$ te bereiken, maar zijn twee stappen wel genoeg. De eerste term in het volgende interval is

$k^2+a_k+2k=(k+1)^2+(a_k-1).$

Daarom geldt $a_{k+1}=a_k-1$ . In het voorbeeld:

$a_5=3,\qquad a_6=2,\qquad a_7=1,\qquad a_8=0.$

Dit correspondeert met $28=25+3$ , $38=36+2$ , $50=49+1$ en $64=64+0$ . Samengevat:

$a_{k+1}=\begin{cases} k-1,&\text{als }a_k=0,\\ a_k-1,&\text{als }a_k>0. \end{cases}$

Stap 5: de nulwaarden zijn precies de machten van twee

We bewijzen met inductie dat $a_{2^r}=0$ voor elk geheel getal $r\geq0$ , en dat tussen $2^r$ en $2^{r+1}$ geen andere nulwaarde ligt.

We beginnen met $a_1=0$ . Stel dat $a_{2^r}=0$ . Dan is $a_{2^r+1}=2^r-1$ . Daarna daalt de waarde bij elke volgende stap met $1$ , zolang ze positief is. Voor $2^r+1\leq k\leq2^{r+1}$ geldt dus

$a_k=2^{r+1}-k.$

Deze waarde is positief als $2^r<k<2^{r+1}$ , en wordt voor het eerst opnieuw $0$ als $k=2^{r+1}$ . Daarmee is de inductie voltooid.

De rij bevat $k^2$ precies wanneer $a_k=0$ . Dat gebeurt exact voor machten van $2$ . Alle gezochte positieve gehele getallen zijn daarom

$\boxed{m=2^r\quad(r=0,1,2,\ldots)}.$

Probleemoplossingstechnieken

Beginwaarden berekenen: De eerste termen maken zichtbaar welke kwadraten voorkomen.
Regelmaat zoeken: De stapgrootte blijft tussen opeenvolgende kwadraten constant.
Werken met intervallen: De rij wordt verdeeld in stukken met een vaste stapgrootte.
Hulpvariabele invoeren: De overschrijding $a_k$ meet de afstand tot het vorige kwadraat.
Inductie: De nulwaarden zijn precies $1,2,4,8,\ldots$ .

Wiskunde is leuk

Tag archieven: INMO

Blokken bepaald door de grootste frequentie

Infobox

Opgave

Eerste idee

Observatieronde

Een kleine versie met drempel 4

Twee voorbeelden met drempel 5

De juiste grootheid

Uitwerking

Stap 1: de grootste frequentie loopt door alle volgende getallen

Stap 2: alle voldoende grote waarden vormen volledige blokken

Stap 3: kies de eerste positie van elk volledig blok

Probleemoplossingstechnieken

Bron

Wanneer belandt de rij op een kwadraat?

Infobox

Opgave

Eerste idee

Observatieronde

De eerste termen

Eerste vaststellingen

Uitwerking

Stap 1: de rij bereikt elk interval tussen twee kwadraten

Stap 2: binnen zo’n interval zijn alle stappen gelijk

Stap 3: wanneer wordt een kwadraat bereikt?

Stap 4: de eerste term na elk kwadraat volgen

Stap 5: de nulwaarden zijn precies de machten van twee

Probleemoplossingstechnieken

Bron