Cesenatico 2005 problema 4

[antosecret]

Determinare per quali n ≥ 3 è possibile trovare n numeri interi positivi tali che a due a due abbiano almeno un fattore in comune diverso da 1, ma a tre a tre siano primi tra loro.

Io l'ho risolto così....

E' possibile per ogni n maggiore o uguale a 3.
Ecco un algoritmo che permette di creare una n-upla di numeri che soddisfino la proprietà.
Costruiamo gli insiemi $ A_1,...,A_n $ di fattori primi che, moltiplicati fra loro, costituiranno i numeri della nostra n-upla.
Per prima cosa si pone $ A_1= { p_1,p_2,\dots,p_{n-1}} $
Poi si assegna a ciascuno degli altri insiemi della n-upla un primo che compare in n_1, usando ciascun primo una sola volta:

$ A_2 = {p_1} $
$ A_3 = {p_2} $
....
$ A_n = {p_{n-1}} $

Si ripete poi lo stesso procedimento partendo da $ A_2, A_3... A_{n-1} $ anzichè da $ A_1 $ e avendo cura di utilizzare primi diversi da quelli già assegnati.

$ A_1= { p_1,p_2,\dots,p_{n-1}} $
$ A_2 = {p_1,p_n,p_{n+1},...} $
$ A_3 = {p_2,p_n,...} $
$ A_4 = {p_3,p_{n+1},...} $
....
$ A_n = {p_{n-1},....} $


In questo modo si avrà che ogni primo distinto sarà contenuto solo in 2 insiemi e che ogni coppia di insiemi avrà un primo in comune. Quindi una n-upla siffatta soddisfa la tesi.

Va bene come dimostrazione???????
Ci sono errori o suggerimenti che potete darmi?

[fph]

EDIT: ok, quanto ho scritto di seguito è una fesseria, sorry, ho riletto il testo del problema e me ne sono accorto. Lo lascio comunque scritto perché comunque è un suggerimento valido... non pertinente per questa soluzione, ma comunque meglio dirlo una volta in più che in meno.

Beh, innanzitutto in un problema con una domanda di questo tipo la dimostrazione si compone di due passi:
1) dimostrare che per un certo insieme di numeri la risposta è sì (magari descrivendo esplicitamente la costruzione, come hai fatto tu)
2) dimostrare che per tutti gli altri numeri la risposta è no (magari provando a supporre che esista e arrivando a un assurdo).

In generale occhio alle dimostrazioni "in due pezzi": per esempio quelle in cui si chiede di determinare un luogo geometrico (i punti del luogo sono tutti e soli quelli...), le equazioni funzionali (le soluzioni sono tutte e sole...) o di dimostrare che due insiemi sono uguali (si dimostra che $ A \subseteq B $ e poi $ B \subseteq A $ ). Anche se una delle due parti davvero è banale, dimenticarla almeno un punto vi costa sempre.