OliForum Matematico

Sia M un sottoinsieme di {1,2,3,...,15}. Trovare quanto vale al massimo |M|, se per ogni i,j,k distinti in M il prodotto ijk non e' un quadrato.

$ |M=12| : M = \{ 4,5,...,14,15 \} $ .
1,4 e 9 sono già in se quadrati perfetti quindi tutti e 3 non possono coesistere nell'insieme. Leviamo l'1. Un possibile sottoinsieme M è quello formato da tutti i numeri primi più 4 e 9, in questo caso M ha 8 elementi (2,3,4,5,7,9,11,13 ) quindi $ |M| \geq 8 $. Scriviamo la scomposizione (non necessariamente in fattori primi) dei restanti numeri sapendo che non si può utilizzare un numero 2 volte:
$ 15=3 \cdot 5 $
$ 14 = 7 \cdot 2 $
$ 12 = 6 \cdot 2 = 3 \cdot 4 $
$ 10= 5\cdot 2 $
$ 8= 4 \cdot 2 $
$ 6= 3 \cdot 2 $ .

Per poter fare un quadrato , per esempio con 14 è necessario che ci siano sia il 7 che il 2 ,e solo con questi due chiaramente può fare un quadrato. Lo stesso vale con gli altri numeri composti. Notiamo che se leviamo il 2, ben 4 numeri (6,8,10, 14 ) non potranno più formare un quadrato. Quindi dal sottoinsieme precedente leviamo il 2 e aggiungiamo i 4 numeri prima indicati. Inoltre facciamo la stessa cosa con il 3: levandolo dal sottoinsieme è possibile aggiungervi 2 numeri (15 e 12, quest'ultimo perchè abbiamo levato anche il 2). il sottoinsisme cercato ha cardinalità 12.

scusa prima non avevo letto la tua risposta

cmq se ho capito bene per M intendi 2,3,4,5,6,7,8,9,10,11,12,13,14,15..

come controesempi però ci sono (5,8,10), (5,12,15),(6,8,12),(7,8,14) ecc

io avevo pensato $|M| = 9 $, cioè $ M=[2,3,4,7,9,10,11,13,15]$ però non so se ce ne sono altri con cardinalità maggiore..

difatti, esistono controesempi all'esempio di amatrix92.. try again

Ok, proviamo. Tolgo i quadrati che non servono, dividendo. L'insieme diventa: ${1, 1, 1, 2, 2, 3, 3, 5, 7, 11, 13, 2\cdot3, 2\cdot5, 2\cdot7, 3\cdot5}$
Le terne che danno quadrati sono $(1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 3, 6), (2, 5, 10), (2, 7, 14), (3, 5, 15)$ e basta.

A questo punto vedo che togliere $1, 2, 3, 8, 12$ restituisce un insieme funzionante. Direi che non si può migliorare, dovrei togliere troppa roba. Ma ho sonno per esserne certo.

sasha™ ha scritto:Ok, proviamo. Tolgo i quadrati che non servono, dividendo. L'insieme diventa: ${1, 1, 1, 2, 2, 3, 3, 5, 7, 11, 13, 2\cdot3, 2\cdot5, 2\cdot7, 3\cdot5}$
Le terne che danno quadrati sono $(1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 3, 6), (2, 5, 10), (2, 7, 14), (3, 5, 15)$ e basta.

A questo punto vedo che togliere $1, 2, 3, 8, 12$ restituisce un insieme funzionante. Direi che non si può migliorare, dovrei togliere troppa roba. Ma ho sonno per esserne certo.

(10,15,6) ammazza l'insieme senza 1,2,3,8,12

(14 7 8 )
(5 15 3)
(1 4 9)
(2 6 12)

Queste quattro triple sono disgiunte, quindi bisogna togliere almeno quattro numeri, e la cardinalità di M è quindi compresa tra 11 e 9.. Secondo me basta trovare un esempio con 11..

exodd ha scritto:(14 7 8 )
(5 15 3)
(1 4 9)
(2 6 12)

Queste quattro triple sono disgiunte, quindi bisogna togliere almeno quattro numeri, e la cardinalità di M è quindi compresa tra 11 e 9.. Secondo me basta trovare un esempio con 11..

Adesso va già meglio
Chi va avanti?

Ok, risolto..
Esistono 6 insiemi M di cardinalità 10 che vanno bene
Un esempio è

$ M = [4, 5, 6, 7, 9, 10, 11, 12, 13, 14] $

Non ne esistono di cardinalità maggiori

La mia dimostrazione è a casi, quindi vorrei vedere se qualcuno ha una soluzione elegante prima..

exodd ha scritto:(10,15,6) ammazza l'insieme senza 1,2,3,8,12

L'ho scritto ieri a mezzanotte, chiedo venia.

Dimostro che il massimo è 10:
Divido in 2 casi:
1) M non contiene quadrati, quindi viste le terne (2,6,12), (7,14,8) e (5,15,3) devo togliere altri 3 numeri e M ha cardinalità minore di 10.
2) M contiene quadrati, date le terne ([],2,8) e ([],3,12) devo togliere 2 numeri (wlog 8 e 12). Infine date le terne (7,14,2), (5,15,3) e (1,4,9) devo eliminare altri 3 numeri e M ha cardinalità massima 10.

Dato che non ho fatto altro che copiare e assemblare le idee precedenti, lascio a Exodd l'onore e l'onere di postare il prossimo problema.

... Non mi ero reso conto che era un problema della staffetta ...