ProbleMATEMATICAmente - Dicembre 2001

Il problema di dicembre era:

Presi 51 numeri distinti tra 1 e 100 inclusi, mostra che almeno uno di essi ne divide un altro.

Sono arrivate due risposte entrambe purtroppo sbagliate, da parte di

  1. Marco Zaro, 3A pni, LS Leonardo da Vinci, Gallarate (VA)
  2. Enrico Tombetti, 4C, LS Leonardo da Vinci, Gallarate (VA).

A differenza del solito, abbiamo deciso di analizzarle lo stesso, dal momento che presentano elementi di interesse.

 Tombetti parte da un insieme di 50 elementi nel quale nessuno ne divide nessun altro e tenta di far vedere che è impossibile costruirne uno di 51 elementi. La costruzione che propone (sostituire k elementi con altri k+1) permette di avere tutti i possibili sottoinsiemi richiesti.

Purtroppo, fa vedere solo in un caso particolare che questa sostituzione immette forzatamente nell'insieme un divisore. Ci sembra che cercare di generalizzare l'analisi porti a un'esplosione di casi particolari non gestibili.

Quanto a Zaro, anche il suo approccio sembra interessante. Suddivide i numeri primi e i numeri non primi in gruppi separati: il numero 1 che se è presente risolve tutti i problemi; i 16 primi che hanno multipli minori di 100; gli altri 10 primi; i 33 nonprimi che hanno multipli; e i 40 rimanenti.

Zaro ritiene erroneamente che analizzare i casi estremi sia sufficiente. In realtà, sono proprio quelli intermedi a presentare le maggiori difficoltà. E, nuovamente, il numero di casi particolari è enorme.

Veniamo ora alla soluzione. Come giustamente ha osservato Tombetti, il problema vale più in generale: è sempre vero che presi n+1 numeri tra i primi 2n, almeno uno di questi ne divide un altro. Come spesso succede, era molto più facile dimostrare il risultato generale, rispetto al problema con i 100 numeri.

Una possibile soluzione del problema generale viene ottenuta ragionando per induzione su n. La base è vera: infatti se n = 1, si hanno i due interi 1 e 2, e il problema è soddisfatto in quanto 1 divide 2.

Adesso, l'ipotesi induttiva ci assicura che comunque prendiamo n+1 numeri minori di 2n, almeno uno di questi ne divide un altro.

Consideriamo ora k+2 numeri interi tra 1 e 2n+2, e diciamo che formano l'insieme A. Se A non contiene né 2n+1 né 2n+2, allora l'ipotesi induttiva ci garantisce che A ha la proprietà richiesta.

Se A contiene uno solo tra 2n+1 e 2n+2, allora per l'insieme A privato di questo numero vale l'ipotesi induttiva, e quindi A ha la proprietà richiesta.

L'ultimo caso è che A contenga sia 2n+1 che 2n+2. Consideriamo allora l'insieme A' in cui 2n+2 viene sostituito da n+1 (che non sta in A, perché se no il problema è già risolto). Per A' vale il caso precedente: cioè esistono due elementi a e b, tali che a divide b. Se b=n+1, allora a divide anche 2n+2 e la proprietà è vera anche per A. Altrimenti a e b sono contenuti anche in A.

Un'ulteriore soluzione è la seguente.

Siano x(0) … x(n), n+1 numeri minori di 2n. Possiamo scriverli tutti come x(i) = 2h(i) y(i), dove h(i) può anche essere uguale a 0, e y(i) è sempre dispari. Detto altrimenti, se x(i) è dispari si ha x(i) = y(i). Se invece è pari, lo dividiamo per 2 tante volte quante possiamo, e y(i) è il risultato finale di tutte queste divisioni.

Tra 1 e 2n ci sono solo n numeri dispari. D'altra parte gli y(i) sono n+1, quindi due di loro devono essere uguali. Diciamo che sia y(j) = y(k). Allora, se h(j)<h(k), si ha che x(j) divide x(k). Altrimenti vale il viceversa.