Sia $S=\{(x,y):x,y\in \mathbb{Z}\}$ l'insieme dei punti a coordinate intere nel piano.
Fissato un certo intero positivo $k$, due punti $A,B\in S$ sono detti $k-$amici se esiste un punto $C\in S$ tale che il triangolo $ABC$ abbia area $k$.
Un insieme (finito) $T\subset S$ si dice $k-$clique se comunque presi 2 punti in $T$, questi sono $k-$amici.
Determinare il più piccolo $k$ tale che esiste una $k-$clique formata da esattamente $ 300 $ punti.
30. 300 punti molto amici
Re: 30. 300 punti molto amici
In tutta la dimostrazione utilizzo solo punti a coordinate intere, quindi appartenenti a S.
Per prima cosa determiniamo quando due punti A e B sono k-amici.
Trovo i k-amici di A(0,0). Considero B(a,b) e C(x,y); l'area del triangolo ABC è k e utilizzando la formula con la matrice per l'area del triangolo si ottiene $|ay-bx|=2k$, che per il teorema di Bezout equivale a dire che $gcd(a,b)|2k$. Ora la traslazione di un vettore a coordinate intere non cambia il fatto che A e B siano k-amici e inoltre A e B saranno a coordinate intere anche dopo la traslazione. Dunque, se prendo A(c,d) e B(a,b), questi sono k-amici se e solo se $gcd(a-c,b-d)|2k$.
A questo punto dimostriamo che una k-cricca (ho tradotto clique in italiano) non può avere più di m^2 elementi, dove m è il più piccolo intero che non divide 2k.
Considero i punti (x,y) a coordinate intere modulo m e ottengo per il pigeonhole che, se T ha più di m^2 elementi, almeno due elementi di T hanno le coordinate che danno lo stesso resto nella divisione per m (cioè due punti le cui x sono congrue modulo m e le cui y sono congrue modulo m). Da qui si arriva facilmente ad un assurdo: se prendo A(c,d) e B(a,b) tali che le loro coordinate danno lo stesso resto modulo m ho che $m|a-c$ e $m|b-d$ e quindi $m|gcd(a-c,b-d)|2k$, assurdo.
Ora dimostriamo che un tale insieme T può avere effettivamente m^2 elementi.
Considero i punti (x,y) dell'insieme T (le coordinate x e y sono comprese tra 0 e m-1 per quanto dimostrato prima). Prendo A(c,d) e B(a,b) in T ed ho che sia a-c che b-d dividono 2k, quindi anche il loro gcd divide 2k, e dunque A e B sono k-amici e quindi T può avere effettivamente m^2 elementi.
Ora poniamo $m^2>300$ e otteniamo $m\geq 18$. $m=18$ non è accettabile poiché 18 non dividerebbe 2k mentre 2 e 9 sì, quindi $m=19$. A questo punto si ha che 1,..,18 dividono 2k e quindi il minimo k è $\frac{lcm(1,..,18)}{2}$. Infatti, prendendo un quadrato 18x18 e togliendo 61 punti ottengo una configurazione di 300 punti tali che soddisfa le ipotesi del problema poiché i 300 punti sono tutti k-amici tra loro e k è minimale (per quanto visto prima, k è minimale per una k-cricca che va da $17^2+1$ punti fino a $18^2$ punti).
Per prima cosa determiniamo quando due punti A e B sono k-amici.
Trovo i k-amici di A(0,0). Considero B(a,b) e C(x,y); l'area del triangolo ABC è k e utilizzando la formula con la matrice per l'area del triangolo si ottiene $|ay-bx|=2k$, che per il teorema di Bezout equivale a dire che $gcd(a,b)|2k$. Ora la traslazione di un vettore a coordinate intere non cambia il fatto che A e B siano k-amici e inoltre A e B saranno a coordinate intere anche dopo la traslazione. Dunque, se prendo A(c,d) e B(a,b), questi sono k-amici se e solo se $gcd(a-c,b-d)|2k$.
A questo punto dimostriamo che una k-cricca (ho tradotto clique in italiano) non può avere più di m^2 elementi, dove m è il più piccolo intero che non divide 2k.
Considero i punti (x,y) a coordinate intere modulo m e ottengo per il pigeonhole che, se T ha più di m^2 elementi, almeno due elementi di T hanno le coordinate che danno lo stesso resto nella divisione per m (cioè due punti le cui x sono congrue modulo m e le cui y sono congrue modulo m). Da qui si arriva facilmente ad un assurdo: se prendo A(c,d) e B(a,b) tali che le loro coordinate danno lo stesso resto modulo m ho che $m|a-c$ e $m|b-d$ e quindi $m|gcd(a-c,b-d)|2k$, assurdo.
Ora dimostriamo che un tale insieme T può avere effettivamente m^2 elementi.
Considero i punti (x,y) dell'insieme T (le coordinate x e y sono comprese tra 0 e m-1 per quanto dimostrato prima). Prendo A(c,d) e B(a,b) in T ed ho che sia a-c che b-d dividono 2k, quindi anche il loro gcd divide 2k, e dunque A e B sono k-amici e quindi T può avere effettivamente m^2 elementi.
Ora poniamo $m^2>300$ e otteniamo $m\geq 18$. $m=18$ non è accettabile poiché 18 non dividerebbe 2k mentre 2 e 9 sì, quindi $m=19$. A questo punto si ha che 1,..,18 dividono 2k e quindi il minimo k è $\frac{lcm(1,..,18)}{2}$. Infatti, prendendo un quadrato 18x18 e togliendo 61 punti ottengo una configurazione di 300 punti tali che soddisfa le ipotesi del problema poiché i 300 punti sono tutti k-amici tra loro e k è minimale (per quanto visto prima, k è minimale per una k-cricca che va da $17^2+1$ punti fino a $18^2$ punti).
Re: 30. 300 punti molto amici
Adesso che sono tornato posso risponderti!
La soluzione è giusta, i passaggi ben spiegati... L'unica cosa è che sembra che ti venga imposto di considerare i punti sul quadrato quando dimostri che effettivamente esiste un insieme $T$ opportuno. (Tu in realtà non consideri i punti in $T$, ma prendi i punti del quadrato e li metti in $T$!)
L'ultimo passaggio io l'ho fatto leggermente diverso, ma in sostanza è quello!
Bene, a te il prossimo!
La soluzione è giusta, i passaggi ben spiegati... L'unica cosa è che sembra che ti venga imposto di considerare i punti sul quadrato quando dimostri che effettivamente esiste un insieme $T$ opportuno. (Tu in realtà non consideri i punti in $T$, ma prendi i punti del quadrato e li metti in $T$!)
L'ultimo passaggio io l'ho fatto leggermente diverso, ma in sostanza è quello!
Bene, a te il prossimo!
Re: 30. 300 punti molto amici
Infatti la rischiesta di esattamente 300 punti mi ha disorientato all'inizio proprio per questo motivo. Tu come l'avevi concluso? Comunque bel problema, l'ho trovato abbastanza difficile.
Ps. Se hai altri problemi così belli ti concedo il testimone (ultimamente mi sono dato a fisica e non mi vengono in mente bei problemi :'( )
Ps. Se hai altri problemi così belli ti concedo il testimone (ultimamente mi sono dato a fisica e non mi vengono in mente bei problemi :'( )