Newsgroup: it.hobby.enigmi
Titolo: Proposto da un'amico...

Consideriamo un piano e n punti su di esso.
Dimostrare che esiste almeno una retta che passa solo per due degli n punti
Ciao

 Dimostrare che esiste almeno una retta che passa solo per due degli n punti
Forse non ho capito, ma a me pare falso.
Basta che tutti gli n punti (n>2, ovviamente) siano allineati e la retta 
in questione non esiste.
C'e' il trucco?
bye
-- 
Paolo Lucchesi
email: plucchesi(at)tin(dot)it
home page: 
http://www.paololucchesi.it


A me non sembra assolutamente vero.
Probabilmente diventa vero assumendo che almeno uno degli n punti non 
appartenga alla stessa retta degli altri n-1 ...


Ovviamente punti non tutti allineati...
Sorry per la dimenticanza
Ciao

 Ovviamente punti non tutti allineati...
Il tuo amico e' decisamente cattivello :-)
Il problema e' noto e la sua dimostrazione, anche se e' elementare, e'
piuttosto difficile: fu proposto nel 1897 da Sylvester e la prima
dimostrazione corretta arrivo' nel 1933 per opera di Gallai (Grunwald).
Qui si puo' trovare qualche altra notizia
http://mathworld.wolfram.com/SylvestersLineProblem.html
ciao
-
-
-
s
p
o
i
l
e
r
-
-
-
Questa che riporto e' la dimostrazione data da L. M. Kelly nel 1948.
Non e' proprio la dimostrazione ideale perche' usa il concetto di distanza
in un problema che riguarda solo incidenze tra punti e rette ma ha il
vantaggio di essere breve (e bella!).
Siano P1,P2,...,Pn gli n punti.
Consideriamo le coppie Pi, PjPk formate da punti e da rette congiungenti
altri due punti in modo che Pi non appartenga alla retta PjPk. Sia, per
esempio, la coppia P1, P2P3 quella per cui la distanza del punto dalla retta
sia minima (essendo queste coppie in numero finito ne esistera' almeno una).
Vogliamo dimostrare che la retta P2P3 non puo' contenere un terzo punto.
Supponiamo per assurdo che, diciamo P4, sia su P2P3 e
chiamiamo H il piede della perpendicolare condotta da P1 su P2P3
allora una delle due semirette in cui H divide la retta P2P3 conterra' 
almeno due
punti. Siano questi per esempio P2 e P3 e sia P2 dei due quello piu' vicino
a H (eventualmente coincidente con H).
---- P4 ----- H -- P2 --- P3 ----
Se ora si considera la coppia P2, P1P3
la distanza tra P2 e P1P3 sara' minore della distanza  tra P1 e P2P3 contro
quanto avevevamo supposto.
P1
| \
|  \
|   \
|    \
|     \
|      \
|       \
|        \
|       . \
|    .     \
H --P2 --- P3

 Dimostrare che esiste almeno una retta che passa solo per due degli n punti
rilancio con questo.
siano infiniti punti nel piano tali che ciascuna distanza tra due 
qualsivoglia punti sia un numero intero. allora tutti i punti sono 
allineati.
pazqo




E io contro rilancio: forse non e` necessario che siano
infiniti.. qual e` - se cosi` fosse - il minimo?
Fino a cinque OK, esempio ai vertici e al centro di un
rettangolo 6x4, ma sei si potranno sistemare?
-- 
Ciao,		|   Attenzione! campo "Reply-To:"  alterato	|
Remigio Zedda	|   posta: ti.ilacsit@zoigimer  <-- dx/sn  ;^)	|
	-- GNU/Linux 2.4.25 su Slackware 9.1

 rettangolo 6x4, ma sei si potranno sistemare?
certo, perché no?
anzi.
la dimostrazione del fatto di cui sopra ti dice proprio che per ogni 
numero finito di punti è possibile trovare una disposizione in modo che 
stia tutti a distanze intere :-)
infatti, per ogni k puoi trovare un cerchio che passa per k punti a 
coordinate intere. beh, se prendi k abbastanza grande potresti fare in 
modo che ci siano abbastanza punti da rendere le distanze reciproche intere.
oppure usi il metodo previsto dal mio problema :-)
pazqo

oppure usi il metodo previsto dal mio problema :-)
Che appunto non so, lo vedro` quando lo risolveranno..


 ha scritto nel messaggio 
news:wza0e.1102793$35.40...@news4.tin.it...

Scusa, dov'è il problema? se degli n punti (non allineati, come è stato 
chiarito in seguito) se ne considerano solo due alla volta, come sembra 
voler suggerire il testo nell'ultima sibillina frase, fin dalle elementari 
insegnano che per due punti non allineati del piano passa una ed una sola 
retta...
Per dimostrare questo fatto basta quindi la semplice geometria euclidea...
Ste 

 vantaggio di essere breve (e bella!).
OK!
Io avevo pensato di seguire una  strada "combinatoria", ovvero:
- Le rette che passano per punti non allineati sono date da :
# rette totali - # rette che passano per 3 o più punti
che può essere scritto anche come:
n*(n-1)/2 - sommatoria su i (ki*(ki-1)/2)
dove ki è la cardinalità dell'i-simo insieme di punti allineati (ki>2).
Basterebbe dimostrare che questa differenza è sempre >=1 indipendentemente
dai ki per ottenere la tesi
 Purtroppo mi sono impelagato nelle maggiorazioni...secondo te è possibile
ottenere risultati seguendo questa strada?
Ciao

 Allora spiega un po' tu dov'e` l'inghippo.  8-]
Se ho capito bene il tuo metodo il problema sta nel fatto che devi trovare 
il mcm dei denominatori di un numero infinito di frazioni, non mi sembra 
un'operazione facile-facile.
Ciao,
Gabriele




Si` ma in ogni caso dovrebbe pero` negare la tesi: che
i punti siano necessariamente tutti allineati.


 allineati.
Ho una mezza idea che però non riesco a formalizzare:
S
P
O
L
I
E
R
Prima un piccolo ripasso di geometria che mi aiuta a chiarire i concetti: 
l'iperbole è il luogo geometrico dei punti la cui differenza (in modulo) 
delle distanze da due punti detti fuochi è costante, chiamiamola D. Si ha un 
iperbole per D minore della distanza tra i due fuochi.
Procediamo per assurdo.
Consideriamo, per ipotesi "assurda", 3 punti non allineati A, B e C. 
Prendiamo ora in considerazione un altro generico punto P appartenente 
all'insieme considerato.
Date le distanze AP e BP si ha, per la disuguaglianza triangolare, 
|PA-PB|<AB e quindi possiamo considerare l'iperbole con fuochi A e B 
passante per P. Visto che tutte le distanze devono essere intere possono 
esistere un numero finito di tali iperboli (se AB=m D può essere 
0,1,2,3,...,m).
Ugualmente P dovrà appartenere ad un'iperbole con fuochi in A e C e con 
differenza costante, ancora una volta esiste un numero finito di queste 
iperboli.
Il punto P dovrà quindi essere intersezione tra due insiemi finiti di 
iperboli e quindi può esistere solo un numero finito di punti P contro 
l'ipotesi che è un insieme infinito.
Detto male ma spero che si capisca l'idea di fondo.
Ciao,
Gabriele 


ottimo, davvero.
si può anche dare una stima sul numero dei punti che possiamo 
individuare volta per volta con le intersezioni. e comunque, non intacca 
il ragionamento che va bene :-)
ciao ciao!
pazqo

 Per dimostrare questo fatto basta quindi la semplice geometria euclidea...
Come e' stato gia' fatto notare, il risultato non e' tanto facile
da dimostrare.
Il punto e' riuscire a dimostrare che almeno una delle rette individuate
da 2 punti non puo' contenere un terzo punto dell'insieme.
Cioe', la cosa difficile da dimostrare (anche se e' intuitiva) e' che
non puo' esistere una configurazione finita di punti in cui su ogni 
retta passante per 2 di essi ce ne sta almeno un terzo.
ciao,
g.

 ottenere risultati seguendo questa strada?
Purtroppo non ti so aiutare, non mi viene in mente niente di utile.
Ciao!