CanMO 2023

Dag 1

Vraag 1

William denkt aan een geheel getal tussen 1 en 50, inclusief. Victor kan een positief geheel getal $m$ kiezen en aan William vragen: "deelt $m$ jouw getal?", waarop William eerlijk moet antwoorden. Victor blijft deze vragen stellen totdat hij het getal van William heeft bepaald. Wat is het minimum aantal vragen dat Victor nodig heeft om dit te garanderen?

Vraag 2

Er zijn 20 studenten in een klas op de middelbare school, en elke student heeft precies drie goede vrienden in de klas. Vijf van de studenten hebben kaartjes gekocht voor een aankomend concert. Als een student ziet dat minstens twee van zijn goede vrienden kaartjes hebben gekocht, dan zal hij ook een kaartje kopen.

Is het mogelijk dat de hele klas kaartjes koopt voor het concert?

(Aanname: vriendschap is wederzijds; als student $A$ goede vrienden is met student $B$, dan is $B$ goede vrienden met $A$.)

Vraag 3

Een acute driehoek is een driehoek waarvan alle hoeken kleiner zijn dan $90^\circ$ ($90^\circ$ is een rechte hoek). Laat $ABC$ een acute driehoek zijn met hoogtelijnen $AD$, $BE$ en $CF$ die samenkomen in $H$. De cirkel die door de punten $D$, $E$ en $F$ gaat, snijdt $AD$, $BE$ en $CF$ opnieuw bij $X$, $Y$ en $Z$ respectievelijk. Bewijs de volgende ongelijkheid:

$$\frac{AH}{DX} + \frac{BH}{EY} + \frac{CH}{FZ} \geq 3.$$

Vraag 4

Laat $f(x)$ een niet-constante veelterm zijn met gehele coëfficiënten zodanig dat $f(1) \neq 1$. Voor een positief geheel getal $n$ definiëren we $\text{divs}(n)$ als de verzameling van positieve delers van $n$.

Een positief geheel getal $m$ is $f$-cool als er een positief geheel getal $n$ bestaat waarvoor geldt

$$f[\text{divs}(m)] = \text{divs}(n).$$

Bewijs dat voor een dergelijke functie $f$ er slechts eindig veel $f$-coole getallen zijn.

(De notatie $f[S]$ voor een verzameling $S$ geeft de verzameling $\{f(s) \colon s \in S\}$ aan.)

Vraag 5

Een land met $n$ steden heeft bepaalde tweewegwegen die bepaalde steden met elkaar verbinden. Iemand merkt op dat als het land op enige manier in twee delen wordt gesplitst, er hoogstens $kn$ wegen tussen de twee delen zijn (waarbij $k$ een vaste positieve integer is). Wat is het grootste gehele getal $m$ (in termen van $n$ en $k$) zodat er gegarandeerd een set van $m$ steden is, waarbij geen van de twee direct met elkaar verbonden is door een weg?