officiele vraagstelling EGMO Q3
Opgave - EGMO 2023 dag 1 vraag 3
Laat $k$ een (strikt) positief geheel getal. Lexi heeft een woordenboek $\mathcal W$
dat bestaat uit een aantal woorden van lengte $k$ die alleen de letters $A$ en $B$ bevatten. Lexi wil graag in elk vakje van een $k \times k$ bord een letter $A$ of een letter $B$ schrijven, zodat elke kolom (van boven naar beneden) een woord uit het woordenboek $\mathcal W$ is en elk rij (van links naar rechts) ook een woord uit het woordenboek $\mathcal W$ is.
Wat is het kleinste gehele getal $m$ zodat als $\mathcal W$ ten minste $m$ verschillende woorden bevat, Lexi altijd op deze manier haar bord kan invullen onafhankelijk van de woorden in het woordenboek $\mathcal W$?
- login om te reageren
Oplossing
Het antwoord is $2^{n-1}$:
Bewijs dat $2^{n-1}-1$ niet werkt:
Laat het woordenboek alle strings die eindigen op $B$ buiten de string die enkel $B$'s bevat. Veronderstel dat er wel een constructie bestaat met dit woordenboek. In dit geval zal de onderste rij uitsluitend B's bevatten waardoor je gedwongen wordt om de string met enkel B's in je woordenboek te hebben, maar dit is niet zo. Contradictie.
Bewijs dat $2^{n-1}$ werkt:
Als het woordenboek de string met enkel $A$'s of enkel $B$'s bevat, dan ben je klaar. Neem in dit geval gewoon een vierkant met enkel $A$'s of enkel $B$'s. Als ze beide ontbreken, zullen vanwege d.h.p. 2 complementaire strings zijn. Hier betekent complementair dat elke index verschillend is, bijvoorbeeld $BAAB$ en $ABBA$.
We gaan nu aantonen dat je met 2 complementaire $k_1$, $k_2$ strings altijd een bord kan invullen.
Constructie:
Vul $k_1$ in de eerste rij. Stel WLOG dat $k_1$ met $A$ begint, vul dan in alle kolommen beginnend met $A$ ook $k_1$ in en in de resterende kolommen, beginnend met $B$, $k_2$.
Dit werkt aangezien de rijen nu enkel uit $k_1$ of $k_2$ bestaan. Veronderstel van niet, neem dan $2$ rijen die niet complementair of gelijk zijn. Dan zijn er 2 kolommen van beide strings in horizontale vorm waar ze allebei een gelijke letter hebben en eentje waar ze een verschillende letters hebben. Dit is echter een tegenspraak met de constructie want je kolommen zijn door de constructie enkel gelijk of elkaars complementaire.
Wetende dat de rijen uit paarsgewijs gelijke of complementaire strings bestaan en dat de eerste rij $k_1$ is, is de constructie dus voltooid.