kikker springt ipv sprinkhaan
Opgave - BxMO 2013 dag 1 vraag 1
Zij $n\ge3$ een geheel getal.
Een kikker beweegt al springend over de getallenlijn (getallenas).
Hij start in het punt $0$ en maakt $n$ sprongen: een van lengte $1$, een van lengte
$2,\cdots$ en een van lengte $n$.
Hij mag deze $n$ sprongen in willekeurige volgorde uitvoeren.
Als de kikker op een gegeven moment op een getal $a \le 0 $ zit, dan moet zijn volgende sprong naar rechts gaan (richting de positieve getallen).
Als de kikker op een gegeven moment op een getal $a$ > $0$ zit, dan moet zijn volgende sprong naar links gaan (richting de negatieve getallen).
Bepaal het grootste positieve gehele getal k zodanig dat de kikker zijn sprong
in zo'n volgorde kan uitvoeren dat hij nooit landt op een van de getallen $1, 2,\cdots , k.$
- login om te reageren
Oplossing
Door enkele eenvouderigere gevallen te beschouwen lijkt het erop dat de maximale $k$ die voldoet gelijk is aan $k=\lfloor \frac{n-1}{2} \rfloor$. Eerst beschouwen we een strategie waarmee het zeker lukt met deze waarde van $k$, en daarna lees je waarom dit de grootst mogelijke waarde is.
***
Stel eerst $n=2(k+1)$ zodat $n$ even is.
Laat de kikker volgende sprongen doen: eerst $k+1$ (naar rechts) en dan steeds een herhaling van sprongen met lengten $k+1+i$ en$ i$, waarbij $i$ de waarden van $1$ tot $k$ één voor één overloopt. Tenslotte doe je nog een laatste sprong naar links van de maximale spronglengte, $2k+2$. je hebt nu alle spronglengtes uitgeoefend en geen van de cijfers $1,2,...,k$ op de getallenas betreden, dus de strategie voldoet. Merk op: eigenlijk ga je over het gebied dat je niet wilt betreden met een langere sprong ($k+1+i$) en dan spring je terug met een kortere sprong ($i$) naar de grens van dat gebied dat je niet wilt betreden (naar $0$ of $k+1$)
Als $n=2k+1$ zodat $n$ oneven is, doe je exact hetzelfde als beschreven voor het even-geval maar zonder die laatste sprong naar links, zodat de laatste sprong $2k+1$ is. en deze strategie is ook volledig binnen de eisen van het gegeven.
***
Eigenlijk zijn we klaar als we kunnen bewijzen dat $k\leq \lfloor \frac{n-1}{2} \rfloor$, omdat we al mogelijke strategieën hebben besproken indien gelijkheid optreedt van deze hypothetische ongelijkheid, die we nu zullen trachten aantonen:
Opdat de 'overgeslagen' regio van de getallen van$ 1$ tot $k$ zo groot mogelijk is, moeten alle sprongen die over dit gat gaan, maximaal zijn. Merk eerst op dat de sprongen met lengten $1,2,3,...,k$ al sowieso niet over dit 'gat' gaan. De sprongen $k+1,k+2,...,n$ kunnen hier wel over gaan,. Er gaan dus maximaal $n-k$ sprongen van de kikker over het verboden gebied van $1$ tot $k$, met een totale spronglengte van $(k+1)+(k+2)+...+n=\frac12(n+k+1)(n-k)$.
Die totale spronglengte is groter dan of gelijk aan$(n-k)$ keer de lengte van het gat (die is $k+1$ breed, en die spring je maximaal $(n-k)$ over) PLUS de som van de overige spronglengten die niet over het gat gaan. Of ook: de totale spronglengte over het gat min de lengte van het gat dat je passert is groter dan/gelijk aan de lengte van de overige sprongen.
Met andere woorden, $\frac12(n+k+1)(n-k)\geq (n-k)(k+1)+\frac12k(k+1)$
en nu nog vereenvoudigen: $n^2+nk+n-kn-k^2-k\geq 2nk+2n-2k-2k^2+k^2+k$
ofte $n^2\geq 2nk+n$, maar das gewoon $\frac{n-1}{2}\geq k$
maar $k$ is geheel, dus neem de Entierfunctie van het linkerlid
$\blacksquare$