Noccioline e rette

[fu^2]

dimostrare che avento a disposizione $2*10^6$ noccioline da diporre su un piano, esiste senpre una retta che lasci $10^6$ noccioline da una parte e $10^6$ noccioline dall'altra.

(nb le noccioline non son altro che punti)...


aiuta il castoro a dividerle

[amel3]

Carino. Semplicissimo. ma carino... [size=75](per induzione matematica...)[/size].

[fu^2]

anche senza induzione volendo

solo con considerazioni geometriche

[Mega-X]

Do la mia anche se è molto grossolana..

Uniamo le noccioline (punti) a 2 a 2 tramite un segmento e troviamo i punti medi di tali noccioline, poi basta trovare la retta interpolante i punti medi..

ora sarebbe interessante chiedersi: Dove può nascondersi le noccioline che non gli servono al castoro?

[fu^2]

le noccioline sono messe a caso... chi ti dice che c'è una retta che passa tra i punti medi di ogni 2 noccioline?

[G.D.5]

1) Mi incuriosisce la soluzione per induzione: se volete, potete farmi vedere qual'è (magari anche con un PM)?
2) Provo a dare la mia soluzione; la metto in spoiler (si dice così?) per modo che non si guati lo spirito ludico e dilettevole del quesito (anche se difficilmente accadrà, perchè quello che ho pensato non convince nemmeno me stesso, quindi...)

Dato un numero finito di punti del piano c'è un numero finito di segmenti tracciabili: in questo caso $((2*10^6)!)/(2!*(2*10^6 - 2)!$; quindi, è senz'altro possibile prendere una retta non parallela ad alcuno dei segmenti suddetti: traslando questa retta parallelamente a se stessa si possono tagliare tutti i segmenti; poichè la retta non è parallela ad alcuno di questi segmenti, ogni estremo di ciascun segmento passa attraverso la retta suddetta una ed una sola volta e tutti i punti-estremi ci passano uno alla volta: basterà a questo punto aver "contato" $10^6$ punti per ottenere l'asserto.

[amel3]

Dicevo con sufficienza che la soluzione per induzione è semplice, ma effettivamente a ben vedere mi è diventata decisamente pipicchia...

Non so se esiste una soluzione "classica" per induzione di questo problema, non sono un grande appassionato di giochi matematici e infatti mi sa che o non va bene o è eccessivamente ridondante (o tutte e due).
La soluzione che avevo pensato io, semplice intuitivamente, decisamente complicata nella realizzazione, è la seguente.

Dati $2n$ punti nel piano cartesiano tra loro tutti distinti, $\forall n in NN$, esiste sempre almeno una retta che suddivide in due regioni il piano che contengono (nella loro parte interna) esattamente $n$ punti ciascuna.



Dim.: Per induzione su $n$.

$n=1$.
E' banale, in quanto basta prendere, ad esempio, la retta passante per il punto medio dei due punti e ortogonale al segmento congiungente i due punti stessi.


$n=k=>n=k+1$
Per ipotesi induttiva, presi $2k$ punti, esiste sicuramente una retta che soddisfa l'asserto.
Supponiamo di avere $2k+2$ punti nel piano: consideriamo poi soltanto $2k$ di questi punti e applichiamo appunto l'ipotesi induttiva. Abbiamo ottenuto una retta che divide il piano in due regioni contenenti ciascuna $k$ punti. Possiamo avere i seguenti casi:

1) i due punti giacciono rispettivamente in una delle due regioni. Siamo a posto, in quanto la retta trovata divide il piano come si desidera.

2) solo uno dei due punti giace esattamente sulla nostra retta. Si considera allora la regione di piano opposta a quella contenente il secondo punto. Preso il punto (o i punti) dei $2k$ più vicino alla nostra retta, con distanza $d$, trasliamo nella regione di piano considerata la retta di $d/2$. Avremo ottenuto una retta come quella richiesta.

3) i due punti si trovano nella stessa regione di piano. Si considera allora la regione di piano opposta a quella contenente i due punti. Si cerca il punto di tale regione che ha minore distanza $d$ da questa retta e il secondo punto più vicino a questa retta, che avrà distanza $d+s$. Si trasla la retta allora dalla parte della regione di piano che stiamo esaminando di $d+s/2$. Avremo ottenuto una retta che soddisfa le condizioni richieste.
Per questo punto occorre, però, aggiungere un caso che può comunque verificarsi. Quando andiamo a cercare i punti più vicini, potrebbe accadere che ci sia più di un punto alla stessa distanza. E' allora opportuno sostituire la retta considerata con una retta opportunamente ruotata rispetto ad uno di questi punti di un angolo tale da far sì che gli altri punti siano più vicini. Ottenuta questa retta, che soddisfa ancora l'ipotesi induttiva, posso applicare allora la 3).

4) tutti e due i punti giacciono sulla nostra retta. Grazie all'ipotesi induttiva siamo certi che solo questi ultimi due punti aggiunti stanno sulla retta. Considero allora il punto più vicino alla retta in una regione del piano e quello più vicino nell'altra, che avranno rispettive distanze $d_1$ e $d_2$. Sulla falsariga delle ultime osservazioni fatte per il punto precedente, effettuiamo una rotazione sulla retta che abbia centro il punto medio di questi due nuovi punti (sarà sempre sulla retta) e chesia di un angolo abbastanza piccolo affinche la retta ruotata non tocchi neppure ora gli altri punti. La retta così ruotata soddisfa ancora l'ipotesi induttiva e divide però anche i due punti, come si voleva.

Sono proprio negato per i giochi matematici...


EDIT: Ho tolto la discussione sugli angoli di rotazione, perchè richiederebbe in effetti l'aiuto di alcuni disegni e di piccole osservazioni supplementari.

[mircoFN1]

"fu^2":dimostrare che avento a disposizione $2*10^6$ noccioline da diporre su un piano, esiste senpre una retta che lasci $10^6$ noccioline da una parte e $10^6$ noccioline dall'altra.

(nb le noccioline non son altro che punti)...


aiuta il castoro a dividerle

credo che si debba assumere che i punti siano distinti, non credo che sia vera diversamente (basti pensare se sono tutti coincidenti)

[fu^2]

"mircoFN":[quote="fu^2"]dimostrare che avento a disposizione $2*10^6$ noccioline da diporre su un piano, esiste senpre una retta che lasci $10^6$ noccioline da una parte e $10^6$ noccioline dall'altra.

(nb le noccioline non son altro che punti)...


aiuta il castoro a dividerle

credo che si debba assumere che i punti siano distinti, non credo che sia vera diversamente (basti pensare se sono tutti coincidenti)[/quote]


per questo ho usato le noccioline ti immagini una mega nocciolina grossa come 2*10^6 noccioline?

bellissimo!!

la soluzione è tipo quella di Wizard, anche se l'ho letta velocemente....

[amel3]

Chi ha voglia guardi la mia soluzione: si metterà le mani nei capelli. Scherzi a parte, se qualcuno ha voglia di guardare la mia soluzione, la guardi, altrimenti vabbè io depongo le armi.
C'è una cosa che il mio piccolo intelletto non mi consente di capire della soluzione di Wizard: come si a provare l'asserto:

è senz'altro possibile prendere una retta non parallela ad alcuno dei segmenti suddetti

Se a qualcuno va, me lo spiega? (non è una domanda ironica o retorica...).

[Mega-X]

scusa se per un punto passano infinite rette con angolazioni diverse c'è ne sarà certamente una fra le infinite che sarà NON parallela a tutte le altre

[fu^2]

"amel":Chi ha voglia guardi la mia soluzione: si metterà le mani nei capelli. Scherzi a parte, se qualcuno ha voglia di guardare la mia soluzione, la guardi, altrimenti vabbè io depongo le armi.
C'è una cosa che il mio piccolo intelletto non mi consente di capire della soluzione di Wizard: come si a provare l'asserto:

è senz'altro possibile prendere una retta non parallela ad alcuno dei segmenti suddetti

Se a qualcuno va, me lo spiega? (non è una domanda ironica o retorica...).

i punti del piano sono finiti, quindi ogni due punti del piano passa una e una sola retta.
esiste quindi una retta che passi senza toccare neanche un punto, in qunato le rette su un piano sono infinite. e da qui l'asserto..

[fu^2]

"amel":
3) i due punti si trovano nella stessa regione di piano. Si considera allora la regione di piano opposta a quella contenente i due punti. Si cerca il punto di tale regione che ha minore distanza $d$ da questa retta e il secondo punto più vicino a questa retta, che avrà distanza $d+s$. Si trasla la retta allora dalla parte della regione di piano che stiamo esaminando di $d+s/2$. Avremo ottenuto una retta che soddisfa le condizioni richieste.
Per questo punto occorre, però, aggiungere un caso che può comunque verificarsi. Quando andiamo a cercare i punti più vicini, potrebbe accadere che ci sia più di un punto alla stessa distanza. E' allora opportuno sostituire la retta considerata con una retta opportunamente ruotata rispetto ad uno di questi punti di un angolo tale da far sì che gli altri punti siano più vicini. Ottenuta questa retta, che soddisfa ancora l'ipotesi induttiva, posso applicare allora la 3).
.

non hop letto benissimo tutto, però una cosa non mi convince...

quando tu trasli di $d+s$ per "andare a dividere" i due punti sul piano che aggiungi al passo di induziine, che ti dice che questa traslazione non tagli fuori dal piano distribuito come prima punti che prima eran divisi in modo giusto?

non so se hai capito la mia perplessità...

[amel3]

Perchè traslo apposta di $d+s/2$ e io so che in quella fascia ho incontrato solo un punto.

[amel3]

Comunque, per quanto riguarda la dimostrazione dell'asserto di Wizard, benchè assolutamente intuitivo, secondo me non bastano le vostre osservazioni
Sotto sotto c'è sempre il procedimento induttivo.

[G.D.5]

"fu^2":
i punti del piano sono finiti,

Perchè i punti del piano sono finiti? (Non voglio sfottere, seriamente non l'ho capita: in un piano ci sono punti in numero finito?)

[amel3]

Voleva dire i punti del piano studiati nell'esercizio

[G.D.5]

Lo sospettavo io che non avevo capite na mazza.