CMO 2023

William is thinking of an integer between 1 and 50, inclusive. Victor can choose a positive integer $m$ and ask William: "does $m$ divide your number?", to which William must answer truthfully. Victor continues asking these questions until he determines William's number. What is the minimum number of questions that Victor needs to guarantee this?

There are 20 students in a high school class, and each student has exactly three close friends in the class. Five of the students have bought tickets to an upcoming concert. If any student sees that at least two of their close friends have bought tickets, then they will buy a ticket too.

Is it possible that the entire class buys tickets to the concert? (Assume that friendship is mutual; if student $A$ is close friends with student $B$, then $B$ is close friends with $A$.)

An acute triangle is a triangle that has all angles less than $90^{\circ}$ ( $90^{\circ}$ is a Right Angle). Let $A B C$ be an acute triangle with altitudes $A D, B E$, and $C F$ meeting at $H$. The circle passing through points $D, E$, and $F$ meets $A D, B E$, and $C F$ again at $X, Y$, and $Z$ respectively. Prove the following inequality:

$$\frac{A H}{D X}+\frac{B H}{E Y}+\frac{C H}{F Z} \geq 3$$

Let $f(x)$ be a non-constant polynomial with integer coefficients such that $f(1) \neq 1$. For a positive integer $n$, define $\operatorname{divs}(n)$ to be the set of positive divisors of $n$.

A positive integer $m$ is $f$-cool if there exists a positive integer $n$ for which

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

Prove that for any such $f$, there are finitely many $f$-cool integers. (The notation $f[S]$ for some set $S$ denotes the set $\{f(s): s \in S\}$.) Remark 1. The original problem statement was "For a fixed non-constant polynomial $f(x) \neq$ $x$, prove that there are finitely many composite $f$-cool integers." Note that this allows $f(1)=1$. Try this problem for an added challenge!

A country with $n$ cities has some two-way roads connecting certain pairs of cities. Someone notices that if the country is split into two parts in any way, then there would be at most $k n$ roads between the two parts (where $k$ is a fixed positive integer). What is the largest integer $m$ (in terms of $n$ and $k$ ) such that there is guaranteed to be a set of $m$ cities, no two of which are directly connected by a road?