Pubblichiamo in tre pdf separati (e scaricabili) le risposte pervenuteci ai questi di Archimede EUREKA del numero di Archimede 2/2016, a cura di Massimo Gobbino.

Problema 405.

Questo problema, tradotto nel linguaggio della teoria dei grafi, equivale a determinare il massimo numero di lati che può avere un grafo su n punti. La risposta è che la configurazione ottimale consiste nel suddividere i punti del grafo in due gruppi con lo stesso numero k di elementi (se n=2k è pari), oppure con k e k+1 elementi (se n=2k+1 è dispari), e poi collegare tutti gli elementi di un gruppo con tutti e soli gli elementi dell’altro. Non è difficile mostrare che in questa configurazione non vi sono triangoli (almeno due vertici devono appartenere allo stesso gruppo).

Molto meno facile è mostrare che questa è la configurazione ottimale, cioè che non esistono configurazioni con più lati e senza triangoli. Questo si può fare sia prendendo in esame il vertice con il maggior numero di collegamenti, sia con un argomento di double counting. Per entrambe gli approcci rimandiamo alle soluzioni allegate.

Come notato da alcuni solutori, questo fatto è noto in letteratura come teorema di Mantel, ed è a sua volta un caso speciale di un risultato molto più generale, e cioè il teorema di Turán.

Segnalo infine un errore logico abbastanza comune in questo tipo di problemi. Esibire una configurazione senza triangoli, con la proprietà che aggiungendo un qualunque lato mancante si forma un triangolo, non costituisce una dimostrazione dell’ottimalità di quella configurazione. Nessuno esclude infatti che la configurazione mostrata sia un vicolo cieco e che invece ne esista un’altra, completamente diversa, con più lati ma ancora senza triangoli.

https://maddmaths.simai.eu/wp-content/uploads/2016/10/p405_soluzioni.pdf
Problema 406.

Questo problema vuole richiamare l’attenzione su una sorprendente proprietà dei polinomi a coefficienti interi: se l’iterata k-esima del polinomio ha un punto fisso intero, allora quello stesso punto è fisso anche per il polinomio iterato 2 sole volte. In altre parole, o un intero ritorna su se stesso dopo 1 o 2 iterazioni, oppure non ci torna più.

La dimostrazione è quella spiegata chiaramente nella soluzione allegata di Giuseppe Fera, e si basa fortemente su una proprietà fondamentale dei polinomi a coefficienti interi, che possiamo riassumere dicendo che $$b-a$$ divide $$P(b)-P(a)$$.

 

https://maddmaths.simai.eu/wp-content/uploads/2016/10/p406_soluzioni.pdf

 

Problema 407.

Si tratta di un classico problema di geometria sintetica risolvibile mediante un semplice “angle chasing”, cioè di soli angoli. Una possibile idea è mostrare che le rette AD ed EK sono parallele considerando gli angoli che formano con la trasversale AC. L’unica piccola cautela che bisogna avere consiste nel rendersi conto che ci sono dei problemi di configurazione, a seconda che i punti D ed E stiano sui lati o sui loro prolungamenti.

Se E sta sul lato AC, allora gli angoli KEC e BAC sono uguali, in quanto entrambi uguali a metà dell’angolo BOC. L’altro caso si tratta in maniera del tutto analoga. La figura allegata alla soluzione di Roberto Ambrosini dovrebbe chiarire questa uguaglianza.

 

 

https://maddmaths.simai.eu/wp-content/uploads/2016/10/p407_soluzioni.pdf