Grossa Grigliata
Grossa Grigliata
Dimostrare che inn $ $ \mathbb Z^2 $ $ è possibile prendere uno e un solo punto su ogni colonna, riga e diagonale nella forma $ x+y=k $.
-
hoja nasredin
- Messaggi: 76
- Iscritto il: 20 set 2007, 18:50
- Località: napoli
In verità è vero molto di più:
Supponiamo di avere $ D $ un insieme finito di direzioni razionali (i.e. fasci di rette parallele che sono della forma $ aX+bY =k $, con $ a, b $ numeri interi).
Allora esiste un insieme $ P $ di punti di $ \mathbf Z \times \mathbf Z $ t.c. su ogni retta con direzione appartenente a $ D $ che contiene almeno un punto di $ \mathbf Z \times \mathbf Z $ si trova uno ed un solo punto di $ P $.
1. Dimostrare. *
2. Resta vero se si toglie l'ipotesi che $ D $sia finito? **
Supponiamo di avere $ D $ un insieme finito di direzioni razionali (i.e. fasci di rette parallele che sono della forma $ aX+bY =k $, con $ a, b $ numeri interi).
Allora esiste un insieme $ P $ di punti di $ \mathbf Z \times \mathbf Z $ t.c. su ogni retta con direzione appartenente a $ D $ che contiene almeno un punto di $ \mathbf Z \times \mathbf Z $ si trova uno ed un solo punto di $ P $.
1. Dimostrare. *
2. Resta vero se si toglie l'ipotesi che $ D $sia finito? **
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Una soluzione "automatica" che sfrutta la tecnica della costruzione induttiva.
Per ogni $ ~ d \in D $, ordiniamo le rette con quella direzione: $ ~ d_1,d_2,\ldots $.
Facciamo così: dedichiamo la nostra attenzione, a turno, a tutte le direzioni di D, e poi ricominciamo dalla prima, e andiamo avanti all'infinito.
Mettiamo che l'"attenzione" tocca alla direzione d. Allora prendiamo la più piccola retta con la direzione d, nell'ordine fissato all'inizio, che non contiene ancora nessun punto di quelli messi finora nel sacco.
Vogliamo aggiungere un punto di questa retta r. Ma non tutti vanno bene: alcuni stanno già su una retta (tra quelle con le direzioni di D) che ha già un suo punto nel sacco. Ma i punti nel sacco sono finiti, e quindi anche le rette (con direzioni di D) che ne contengono uno sono finite, e quindi anche le loro intersezioni con r sono finite. Quindi c'è almeno un punto di r che possiamo aggiungere. Aggiungiamolo.
E poi scegliamo la direzione successiva, e andiamo avanti.
Consideriamo ora l'insieme di tutti i punti che prima o poi PubTusi metterà nel sacco. Se ce ne sono due,a e b, che stanno su una retta con direzione tra quelle di D, troviamo un assurdo: se b è stato aggiunto dopo a... capiamo che il procedimento non avrebbe permesso questo!
Ora prendiamo una direzione di D e una retta r con quella direzione. Diciamo che nell'ordinamento era n-esima. Allora entro i primi n*|D| passaggi abbiamo aggiunto un punto che sta su r.
Senza l'ipotesi che D sia finito... potremmo prendere l'insieme di tutte le direzioni. Il nostro insieme di punti deve contenere almeno due punti... ma per questi due punti passa una retta che ha una certa direzione razionale. Male ...
Per ogni $ ~ d \in D $, ordiniamo le rette con quella direzione: $ ~ d_1,d_2,\ldots $.
Facciamo così: dedichiamo la nostra attenzione, a turno, a tutte le direzioni di D, e poi ricominciamo dalla prima, e andiamo avanti all'infinito.
Mettiamo che l'"attenzione" tocca alla direzione d. Allora prendiamo la più piccola retta con la direzione d, nell'ordine fissato all'inizio, che non contiene ancora nessun punto di quelli messi finora nel sacco.
Vogliamo aggiungere un punto di questa retta r. Ma non tutti vanno bene: alcuni stanno già su una retta (tra quelle con le direzioni di D) che ha già un suo punto nel sacco. Ma i punti nel sacco sono finiti, e quindi anche le rette (con direzioni di D) che ne contengono uno sono finite, e quindi anche le loro intersezioni con r sono finite. Quindi c'è almeno un punto di r che possiamo aggiungere. Aggiungiamolo.
E poi scegliamo la direzione successiva, e andiamo avanti.
Consideriamo ora l'insieme di tutti i punti che prima o poi PubTusi metterà nel sacco. Se ce ne sono due,a e b, che stanno su una retta con direzione tra quelle di D, troviamo un assurdo: se b è stato aggiunto dopo a... capiamo che il procedimento non avrebbe permesso questo!
Ora prendiamo una direzione di D e una retta r con quella direzione. Diciamo che nell'ordinamento era n-esima. Allora entro i primi n*|D| passaggi abbiamo aggiunto un punto che sta su r.
Senza l'ipotesi che D sia finito... potremmo prendere l'insieme di tutte le direzioni. Il nostro insieme di punti deve contenere almeno due punti... ma per questi due punti passa una retta che ha una certa direzione razionale. Male ...
e non sai cosa ti perdi a non vederlo dal vivo!uh, che bello Marco.
...lo prendero' come un complimento... A proposito: ci siamo visti? Forse al Senior 2006?edriv ha scritto:e non sai cosa ti perdi a non vederlo dal vivo!uh, che bello Marco.
Tornando on topic: ok. La soluzione è esattamente quella di Edriv: le rette da controllare sono numerabili, e dato che ad ogni passo ci sono solo un numero finito di punti, i punti sulla retta che non vanno bene sono finiti.
Mi chiedo se è possibile trovare un esempio di $ D $ insieme di infinite direzioni razionali, ma che comunque ha la proprietà di avere esattamente un punto su ogni retta da controllare. Ma di questo ammetto di non avere una soluzione...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Butto li un esempio banale...Marco ha scritto:Mi chiedo se è possibile trovare un esempio di $ D $ insieme di infinite direzioni razionali, ma che comunque ha la proprietà di avere esattamente un punto su ogni retta da controllare. Ma di questo ammetto di non avere una soluzione...
Rappresentando le rette come $ aX + bY = k $, possiamo scegliere tutte le rette del tipo $ a + b = 1 $, uno e uno solo dei punti del tipo $ X = Y $ appartiene a ciascuna delle rette di questa classe.
Non saprei, non mi viene in mente un esempio decente, in cui i punti non giaciano tutti sulla stessa retta