Grossa Grigliata

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
PubTusi
Messaggi: 60
Iscritto il: 01 feb 2008, 15:30

Grossa Grigliata

Messaggio da PubTusi » 14 feb 2008, 21:01

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: 75
Iscritto il: 20 set 2007, 18:50
Località: napoli

Messaggio da hoja nasredin » 14 feb 2008, 21:53

scusa per la diagonale intendi tutte possibili i diagonali?
"Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn"

PubTusi
Messaggi: 60
Iscritto il: 01 feb 2008, 15:30

Messaggio da PubTusi » 14 feb 2008, 21:59

No, solo quelle di equazione x+y=k, cioè da sinistra in alto a destra in basso

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 15 feb 2008, 21:53

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? **
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

PubTusi
Messaggi: 60
Iscritto il: 01 feb 2008, 15:30

Messaggio da PubTusi » 20 feb 2008, 16:39

uh, che bello Marco.
La soluzione che ho è già incasinata per il caso che ho proposto.
Saresti così gentile da hintarmi pesantemente?

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 20 feb 2008, 22:03

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 ...
uh, che bello Marco.
e non sai cosa ti perdi a non vederlo dal vivo!

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 20 feb 2008, 23:51

edriv ha scritto:
uh, che bello Marco.
e non sai cosa ti perdi a non vederlo dal vivo!
...lo prendero' come un complimento... A proposito: ci siamo visti? Forse al Senior 2006?

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."

PubTusi
Messaggi: 60
Iscritto il: 01 feb 2008, 15:30

Messaggio da PubTusi » 21 feb 2008, 21:37

edriv ha scritto: e non sai cosa ti perdi a non vederlo dal vivo!
Toh, e io che mi accontentavo della paperetta -_-'

carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop » 21 mar 2008, 11:49

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...
Butto li un esempio banale...
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

Rispondi