Tanti punti allineati

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
karlosson_sul_tetto
Messaggi: 1430
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Tanti punti allineati

Messaggio da karlosson_sul_tetto » 27 dic 2016, 17:31

Dimostrazione alternativa che sembra lunga e strana ma in realtà è molto ganza.
Testo nascosto:
Lemma: un grafo planare ha almeno un vertice di grado $\leq 5$
Dimostrazione: Siano $V, A,F$ il numero di vertici, archi e facce del grafo. Vale la formula di eulero $V+F=A+2$.
Ogni faccia è circondata da almeno 3 archi; ogni arco separa due facce (o è in mezzo ad una faccia), quindi $2A\geq 3F$. Quindi sostituendo nella formula di eulero si ottiene $A+2=V+F\leq V+\frac{2}{3}A$, ovvero $A\leq 3V-6$.
Presupponendo la tesi falsa, ogni vertice ha grado $\geq 6$; quindi $2A=\sum \text{deg}(vertice)\geq 6V$, quindi $A\geq 3V$, assurdo.

Ora passiamo al problema. Prendiamo una sfera $S$ di centro $O$ fuori dal piano dove sono disposti i punti e proiettiamo il piano su una sfera: il punto $P$ del piano viene mandato nella coppia di punti $P_1, P_2$ diametralmente opposti dati dall'intersezione di $OP$ con la sfera. Allora le rette del piano vanno in cerchi massimi e la tesi diventa "Date n coppie di antipodi sulla sfera, tali che prese due coppie a caso, esiste una terza coppia sullo stesso cerchio massimo delle prime due, allora le n coppie sono sullo stesso cerchio massimo".

Facciamo una trasformazione duale: a ogni coppia di antipodi sostituiamo il cerchio massimo perpendicolare alla loro congiungente e viceversa (cioé se i due punti sono il polo Nord e Sud, li sostituiamo con l'equatore, e preso un cerchio massimo lo sostituiamo con i relativi poli). Si vede facilmente che una coppia $A,B$ di punti stava sul cerchio massimo $C$ prima della trasformazione se e solo se i poli $C_1,C_2$ stanno sull'equatore di $AB$.

La tesi diventa "Dati n $(\geq 3)$ cerchi massimi sulla sfera, tali che presi due a caso, esiste un terzo che passa per la loro intersezione, allora tutte i cerchi massimi passano per gli stessi due punti". Presupponiamo che la tesi sia falsa, allora per ogni coppia di punti c'è al massimo un arco (senza altri punti all'interno) che la contiene: infatti presi due punti $X,Y$ diametralmente opposti esiste un cerchio massimo $C$ che non passa per questi e quindi ogni cerchio massimo per $X,Y$ deve intersecare $C$; se $X,Y$ non sono diametralmente opposti allora c'è un solo cerchio massimo che li contiene; inoltre visto che ci sono almeno $3$ cerchi ci sarà un'intersezione con almeno uno dei due pezzi in cui $X$ e $Y$ dividono il cerchio massimo.
Quindi possiamo considerare i punti come vertici di un grafo e gli archetti da un punto all'altro come archi; il grado di ogni vertice diventa dunque $2\cdot$ il numero di cerchi massimi che lo attraversavano; l'ipotesi ci dice che per qualsiasi intersezione di due cerchi ne passa almeno un altro, quindi per ogni vertice passano almeno 3 cerchi e dunque ha grado almeno 6. Ma il lemma iniziale ci dice che in un grafo planare (e questo è planare perché ad ogni intersezione di archi c'è un vertice per definizione) esiste un vertice con grado $\leq 5$, assurdo.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

AlexThirty
Messaggi: 214
Iscritto il: 20 giu 2015, 20:58

Re: Tanti punti allineati

Messaggio da AlexThirty » 28 dic 2016, 12:12

$W4G
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: Tanti punti allineati

Messaggio da Sirio » 01 gen 2017, 13:43

Oddio, dopo aver visto questa mi sento davvero a disagio...
シリオ
$T=\sqrt{\dfrac l g 12\pi}$

AlexThirty
Messaggi: 214
Iscritto il: 20 giu 2015, 20:58

Re: Tanti punti allineati

Messaggio da AlexThirty » 03 gen 2017, 20:21

Se preferite c'è anche la versione "simmetrica" la cui soluzione è praticamente uguale.
In un piano ci sono $ n $ rette a due a due non parallele. Per ogni due rette che si intersecano in un punto, c'è un'altra retta che passa per quel punto. Dimostrare che tutte le rette passano per uno stesso punto
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti