Sia $A$ l'insieme composto dai numeri naturali dall'$1$ al $20$ compresi.
Sia $B$ un suo sottoinsieme composto esattamente da nove elementi e tale che, presi tre suoi elementi qualsiasi fra questi nove, essi NON formino una progressione aritmetica.
Supponiamo che la distanza tra i due più piccoli numeri di \(B\) sia \(1\).
Supponiamo \(1 \in B \).
La presenza del \(1\) e del \(2\) vietano la presenza del \(3\) altrimenti sarebbero 3 termini in progressione aritmetica. Il \(4\) va bene perché non crea una progressione aritmetica con i numeri 1 e 2.
Il \(5\) pure va bene perché non crea una progressione aritmetica con nessuno dei 3 precedenti. Quindi al momento abbiamo i numeri \(1,2,4,5 \).
Questi numeri ci tolgono già molti numeri disponibili. Infatti il \(6\) non può essere elemento di \(B\) altrimenti \(4,5,6\) è una AP. Il \(7 \) pure non può esserci altrimenti \(1,4,7 \) creerebbe una AP. Il numero \(8\) non può esserci poiché creerebbe la AP seguente \( 2,5,8 \). E il \(9\) non può essere dentro a \(B\) poiché altrimenti \(1,5,9 \) sarebbe una progressione aritmetica.
Il \(10\) è disponibile invece poiché la media tra 10 e \(b=1,2,4,5 \) non appartiene a \(\{1,2,4,5\} \).
Quindi \( 1,2,4,5,10 \in B\). In modo analogo il numero \(11\) è disponibile per lo stesso motivo.
Ora il numero \(12 \) non può essere dentro poiché sarebbe in AP con \(10,11,12 \). Il numero \(13 \) è disponibile poiché la media tra \(13\) e \(b=1,2,4,5,10,11 \) non appartiene a \( \{1,2,4,5,10,11\} \)
Il \(14 \) è disponibile per un ragionamento del tutto analogo al \(13 \).
Quindi \( 1,2,4,5,10,11,13,14 \in B \). Ci resta ancora un numero da determinare.
Vediamo ora però che il \(15 \) non è disponibile poiché \(5,10,15 \) sarebbe una progressione aritmetica.
\( 16 \) non è disponibile poiché \( 10,13,16 \) sarebbe una progressione aritmetica. Il \(17 \) non è disponibile poiché \(11,14,17 \) sarebbe una progressione aritmetica. Il \(18 \) non è disponibile altrimenti \(10,14,18 \) sarebbe una progressione aritmetica. Il \(19 \) non è disponibile poiché altrimenti \( 1,10,19 \) sarebbe una progressione aritmetica. E pure \(20 \) non è disponibile.... quindi se \(1 \in B \) allora \(2 \not\in B \). Se il più piccolo numero non è \(1\), ma \(2\) ad esempio, le distanze qui sopra resterebbero le uniche valide. Ovvero significherebbe traslare tutto di \(1 \) (nel caso che il minimale è il \(2\)), quindi non possiamo avere che la distanza tra i due più piccoli numeri di \(B\) è \(1\), poiché altrimenti dovremmo prendere numeri più grandi di \(20 \).
Supponiamo che la distanza tra i due più piccoli è \(2\).
Supponiamo \(1 \in B \)
Allora la presenza di \(1\) e \(3 \) permette la presenza di \(4 \). Il \(5\) non può essere presente. Il \(6\) può essere presente invece, quindi attualmente \( 1,3,4,6 \in B \). Infatti tutte le medie possibili fra questi 4 numeri sono diverse da \(1,3,4,6\).
Ora il \(7 \) non può essere dentro poiché la media tra 1 e 7 è 4. Il numero 8 non può essere dentro poiché la media tra 8 e 4 è 6. Il numero 9 non può essere dentro poiché la media tra 3 e 9 è 6. Il 10 invece può essere dentro poiché la media tra \(10 \) e \(b =1,3,4,6 \) non appartiene a \(\{ 1,3,4,6\}\).
Quindi attualmente \( 1,3,4,6,10 \in B \). Il numero \(11\) non ci può essere poiché \((1+11) /2 = 6 \).
Il numero \(12 \) può essere presente poiché la media tra \(12 \) e \(b=1,3,4,6,10 \) non appartiene al set \( \{1,3,4,6,10 \} \).
Quindi attualmente \(1,3,4,6,10,12 \).
Il numero 13 può essere presente invece poiché la media tra \(13\) e \( b=1,3,4,6,10,12 \) non appartiene a \( \{1,3,4,6,10,12 \} \). Quindi attualmente
\( 1,3,4,6,10,12,13 \in B \).
Il \(14 \) non può essere presente poiché la media tra \(14 \) e \(6\) è \(10 \).
Il \( 15\) può essere presente poiché infatti la media tra \(15\) e \(b=1,3,4,6,10,12,13 \) non appartiene a \( \{1,3,4,6,10,12,13 \} \).
Quindi \( 1,3,4,6,10,12,13,15 \in B \) e ci resta un numero da determinare.
Vediamo immediatamente che \( (16 + 4)/2=10 \), \( (17+3)/2=10 \), \( (18+6)/2=12\) e \( (19+1)/2=10 \) pertanto resterebbe il \(20\). Ma \( (20+4)/2=12\)... quindi mmm
Stesso discorso se il minimale non fosse \(1\) dovremmo traslare tutto di almeno 1 superando la capacità di prendere solo numeri inferiori a \(20\).
Supponiamo che la distanza tra i due più piccoli è \(3\).
Supponiamo \(1 \in B \)
Allora la presenza di \(1\) e \(4 \) permette la presenza di \(5 \). Il \(6\) non può essere presente. Il \(7\) può essere presente invece, quindi attualmente \( 1,4,5,7 \in B \). Infatti tutte le medie possibili fra questi 4 numeri sono diverse da \(1,4,5,7\).
Ora il \(8\) può essere presente. Il numero 9 non può essere dentro. Infatti \(7,8,9 \) è una AP. Il numero 10 non può invece può essere presente poiché \(10+4 = 14 \).
Quindi attualmente \( 1,4,5,7,8 \in B \). Il numero \(11\) non può esserci poiché \( 5,8,11 \) è progressione aritmetica.
Il numero \(12 \) non può essere presente poiché \(4,8,12 \) è AP.
Per \(13 \) abbiamo \(1,7,13 \).
Il \(14 \) può essere presente (per via delle medie) Quindi
\( 1,4,5,7,8,14 \in B \). E ci restano 3 numeri. Il 15 no poiché \( 1,8,15 \) è AP. Il \(16 \) sì per via delle medie. Il \(17\) può esserci per via delle medie, quindi attualmente abbiamo
\( 1,4,5,7,8,14,16,17 \in B \). E ci resta un numero da determinare. Il \(18 \) no poiché \(16,17,18 \) è AP. Il \(19 \) è possibile mentre il \(20 \) no \(8,14,20 \).
Pertanto
\[ B= \{ 1,4,5,7,8,14,16,17,19 \} \]
Presumo sia unico. Ma non ho voglia di dimostrarlo anche se non dovrebbe essere così difficile.
Posso provare che non esiste un sottoinsieme con + di 8 elementi che soddisfi il requisito...ma usando un setaccio. Ti andrebbe bene?
http://www.cs.umd.edu/~gasarch/BLOGPAPERS/3apsurvey.pdf
Dovrebbe esistere. Se guardi definition 5 a pagina 4 \( \operatorname{sz}(n) \) è il sottoinsieme di \([n] \) di cardinalità massimale tale che è 3-free. Con k-free in definition 4 dice che intende un insieme che non contiene progressioni aritmetiche di lunghezza \(k\). E a pagina 56, la tabella per \(1 \leq n \leq 100 \) dice che \( \operatorname{sz}(20)=9 \).
Le mie conclusioni erano sbagliate. Infatti partendo da \(1,2\) mettevo i primi numeri che erano disponibili, arrivavo a non trovare un insieme di cardinalità 9 con le proprietà richieste e concludevo, precocemente ed erroneamente, che \(1 \in B \Rightarrow 2 \not\in B \). Ma questo è sbagliato perché magari il terzo numero è disponibile ma non devo metterlo per trovare \(B\).
Osserviamo che \(20\) è l'intero minimale per cui esiste un insieme di \( [20] \) di cardinalità massimale \(9\) tale che è possibile trovare un tale \(B\) (questa è una cosa che ho letto nel articolo che ho messo sopra, nella tabella a pagina 56). Questo significa che \( 20 \in B \), altrimenti avremmo che \( B \subseteq [19] \). Pertanto troviamo gli insiemi di cardinalità \(8\), \( B \setminus \{20 \} \subset [19] \) tale che sono 3-liberi (per 3-liberi intendo che non ci sono 3 elementi che formano una progressione aritmetica).
La mia speranza nel modo seguente era di trovare un insieme che era \(3\)-libero con 9 elementi, di cui uno era il 20. E in effetti l'ho trovata.
Iniziamo con \(1,2\) in \(B\). Chiaramente il \(3\) non possiamo metterlo.
Nel mio commento precedente se dopo \(1,2\) ci mettiamo il \(4\) e procediamo riempendo i "buchi" appena possibile troviamo.
\[ B \setminus \{20\} = \{1,2,4,5,10,11,13,14 \} \]
è 3-libero. Aggiungendo il \(20 \) però non diventa più 3-libero infatti \(20+2 = 22= 2 \cdot 11 \).
Proviamo che dopo \(1,2 \) ci mettiamo il \(5\) e procediamo riempendo i "buchi" appena possibile troviamo
\[ B \setminus \{20\} = \{1,2,5,6,10,12,13,17 \} \]
è 3-libero. Aggiungendo il \(20 \) però non diventa più 3-libero infatti \(20+6 = 26= 2 \cdot 13 \).
Proviamo allora a mettere il \(6\) e procediamo riempendo i "buchi" appena possibile troviamo
\[ B \setminus \{20\} = \{1,2,6,7,9,14,15,18\} \]
è 3-libero. Aggiungendo il \(20 \) resta 3-libero!
@3m0o E l'altra? Perché è ovvio che esiste anche l'altra, no?
Non leggere finché non trovate l'altra
Dato che quello che conta non sono i numeri in sé ma le "distanze" tra di essi, allora partire dall'altro capo in senso inverso con la stessa sequenza di distanze produce la "simmetrica".
Potrebbe coincidere, certo, ma non è il caso della simmetrica postata da 3m0o.
Inoltre, secondo quanto scoperto da 3m0o, il $20$ deve sempre esserci ma allora ne consegue che c'è sempre la simmetrica che parte dall'$1$ e siccome anch'essa deve finire al $20$, una volta trovate quelle che partono da $1$, trovate tutte.
Teoricamente ci sarebbero anche le "traslate" ma poiché tutte iniziano da uno e finiscono in venti, la traslazione farebbe finire la sequenza fuori "range" perciò non ci sono "traslate".
Ho detto giusto?
Certo, è ovvio! Come ho fatto a non arrivarci
Basta prendere quell'insieme e cambiare il ruolo delle distanze
Abbiamo
\[ B_1 = \{ 1,2,6,7,9,14,15,18,20 \} \]
con relative distanze di successivi
\[ 1,4,1,2,5,1,3,2 \]
Basta prendere le distanze di successivi "al contrario"
\[ 2,3,1,5,2,1,4,1 \]
e formare
\[ B_2 = \{ 1,3,6,7,12,14,15,19,20 \} \]
Mentre che non ve ne siano altri oltre a questo non è ovvio, in realtà non so se ce ne sono altre
Ok, ci sono tornato su. A quanto pare ho usato male il setaccio (grazie 3m0o per il link!).
Ho buttato dentro le soluzioni per n=9 e alla fine ho derivato per buonsenso una soluzione per il caso n=20...e poi mi son rotto gli zebedei.
Rispondi
Per rispondere a questa discussione devi prima effettuare il login.
Segnala Post di
Tutor AI
Ciao! Sono il tuo Tutor AI, il compagno ideale per uno studio interattivo. Utilizzo il metodo maieutico per affinare il tuo ragionamento e la comprensione. Insieme possiamo:
Risolvere un problema di matematica
Riassumere un testo
Tradurre una frase
E molto altro ancora...
Cosa vuoi imparare oggi?
Il Tutor AI di Skuola.net usa un modello AI di Chat GPT.
Per termini, condizioni e privacy, visita la relativa pagina.
E l'altra? Perché è ovvio che esiste anche l'altra, no? 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo