OliForum Matematico

$60^{60}=2^{120}3^{60}5^{60}$. Costruisco $61^2$ cassetti tali che nel cassetto determinato dalla coppia $a, b$ metto i codici che hanno come fattorizzazione $2^x3^a5^b$. Un cassetto per ogni possibile coppia $a, b$ tali che $0 \le a, b \le 60$.
Se prendessi $61^2+1$ codici per pigeonhole due finiscono nello stesso cassetto, quindi sono della forma $2^x3^a5^b, 2^y3^a5^b$ per gli stessi $a, b$.
WLOG $x \le y \Rightarrow 2^x3^a5^b \mid 2^y3^a5^b$, il che non va bene e dunque il numero cercato è $\le 61^2$.
Mostriamo una configurazione che funzioni con $61^2$ codici (viene messo un codice per ogni cassetto usato nel precedente pigeonhole e al cassetto $a, b$ verrà assegnato un numero $x_{a, b}$ che sarà l'esponente di 2). Affinché un numero non divida un altro e viceversa deve avere l'esponente di almeno un primo maggiore e l'esponente di almeno un primo minore.
Dato un numero contenuto nel cassetto $a, b$ posso dunque ignorare i cassetti $c, d$ con $c>a, d<b$ o $c<a, d>b$.
Al cassetto $a, b$ devo dunque assegnare un numero $x_{a, b}$ che andrà a essere l'esponente di 2 in maniera tale che $0 \le x_{a, b} \le 120$ per ogni $a, b$ e
$x_{a, b} > x_{c, d}$ se $c>a, d \ge b \lor c \ge a, d>b$.
Notiamo che $x_{a, b}=120-(a+b)$ funziona.
Innanzitutto è minimo quando $a$ e $b$ sono massimi, cioè $a=b=60 \Rightarrow 120-(a+b)=0$ ed è massimo quando $a$ e $b$ sono minimi, cioè
$a=b=0 \Rightarrow 120-(a+b)=120$, quindi $0 \le x_{a, b} \le 120$ come voluto.
Inoltre $x_{c, d}=120-(c+d) < 120-(a+b)=x_{a, b}$ se $c>a, d \ge b \lor c \ge a, d>b$, come voluto.
Dunque è possibile per $61^2$ stagisti ma non per $61^2+1$, quindi il massimo numero di stagisti che potrà partecipare al prossimo Stage Senior è $61^2$.