Baltic Way 2016 - kombinatorikk

[stensrud]

La $n$ tall, alle lik $1$, være skrevet på en tavle. Et trekk består i å erstatte to tall som står på tavlen med to kopier av deres sum. Etter $h$ trekk viser det seg at de $n$ tallene på tavlen alle er lik $m$. Vis at $h\leqslant \frac12n \log_2m$.

[Gustav]

Skal vel være $h\leq \frac12 n\log_2 m$ ?

[stensrud]

Hadde det ikke vært kult om $n$ var irrelevant da? Takk for at du påpekte det, har retta det opp.

[Gustav]

Hadde det ikke vært kult om $n$ var irrelevant da? Takk for at du påpekte det, har retta det opp.

Var inne å sjekka resultatene deres. Svært bra på kombinatorikken(!) og bra på geometri, men hva skjedde på algebradelen? Bare ikke prioritert, eller?

[stensrud]

Var inne å sjekka resultatene deres. Svært bra på kombinatorikken(!) og bra på geometri, men hva skjedde på algebradelen? Bare ikke prioritert, eller?

Husker ikke helt hva som ble gjort under prøven, men planen var å ta starte med favorittområdene våre og deretter hoppe litt rundt, som ga mening siden kompetansen var godt fordelt. Selv startet jeg med geometri og kom godt i gang, men fant ut at jeg hadde en fakesolve jeg ikke klarte å rette opp igjen. Kombinatorikkgutta var på hugget og vi løste mye der selv om det ble kastet bort litt mye tid på oppgave 15. På flyet hjem gjorde jeg algebra- og tallteorioppgavene sammen med Pål (vår deputy), og vi lo/gråt over hvor mange poeng vi enkelt kunne fått om vi hadde skiftet fokuset over til andre oppgaver under prøven.

Oppgaven jeg la ut over var vi ganske heldige med: Jeg hadde gjort IMO Shortlist 2014 C2 før, så da tok det ikke mer enn ett minutt før løsningen til denne oppgaven var skrevet ned

[Gustav]

Ok, så produktet av tallene øker med minst en faktor 4 for hvert trekk. Etter $h$ trekk er produktet minst $4^h$. Fra AM-GM er dermed summen av tallene større enn $n\sqrt[n]{4^h}$. Siden summen er $mn$, får vi ulikheten $m\geq \sqrt[n]{4^h}$, som er ekvivalent med $\log_2 m\geq \frac1n \log_2 4^h=\frac{2h}{n}$, så $h\leq \frac{n}{2}\log_2 m$.

Godt eksempel på en oppgave hvor riktig idé gjør problemet trivielt, men der det ikke nødvendigvis er så lett å komme på ideen:D Fin teknikk å gå mellom sum og produkt da! Den skal jeg merke meg til senere anledninger. Skal vel ikke se bort fra at denne ideen kan brukes også i andre kombinatorikkproblemer.

[stensrud]

Ok, så produktet av tallene øker med minst en faktor 4 for hvert trekk. Etter $h$ trekk er produktet minst $4^h$. Fra AM-GM er dermed summen av tallene større enn $n\sqrt[n]{4^h}$. Siden summen er $mn$, får vi ulikheten $m\geq \sqrt[n]{4^h}$, som er ekvivalent med $\log_2 m\geq \frac1n \log_2 4^h=\frac{2h}{n}$, så $h\leq \frac{n}{2}\log_2 m$.

Bra Mer direkte kan du vel bare sammenlikne produktet på minst $4^h$ og produktet vi er gitt, $m^n$, men det blir vel omtrent det samme.

Godt eksempel på en oppgave hvor riktig idé gjør problemet trivielt, men der det ikke nødvendigvis er så lett å komme på ideen:D Fin teknikk å gå mellom sum og produkt da! Den skal jeg merke meg til senere anledninger. Skal vel ikke se bort fra at denne ideen kan brukes også i andre kombinatorikkproblemer.

Konkurransematematikk i et nøtteskall... Sum-produkt trikset er veldig nyttig, og det kan brukes blant annet på ulikheter hvor den ene siden er produkt: Man tar logaritmen av begge sider, og gjør produktet om til en sum som man kan bruke Jensen på, for eksempel. En av lederne til det svenske laget mener trikset er så nyttig at han bruker det som sitt mantra: "You have product? Always take log, always".