"Ancora" con $2n+3$

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Tess
Messaggi: 258
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

"Ancora" con $2n+3$

Messaggio da Tess » 16 mag 2013, 19:01

Dati $n+3$ punti del piano, dimostrare che il numero minimo di punti medi distinti di segmenti che hanno per estremi 2 di questi punti è $2n+3$.

Così il prossimo anno a Mirabilandia qualche altra persona potrà dire che il kangourou 5 l'aveva già visto! :wink:

Gulliver
Messaggi: 17
Iscritto il: 10 set 2013, 19:08

Re: "Ancora" con $2n+3$

Messaggio da Gulliver » 12 set 2013, 13:53

Allora il problema si può riformulare in: dati n+3 vettori nel piano $v_1,...,v_{n+3}$ dimostrare che $|\{v_i+v_j, i \neq j\}|>2n+3$.
Osserviamo che possiamo ordinare completamente i vettori nel seguente modo: se la prima coordinata di v è più grande di quella di w, allora v>w, se sono uguali si passa alle seconde coordinate e si fa lo stesso confronto. Inoltre valgono le usuali regole $v>w$ implica $v+a>w+a$.
Pertanto indicizziamo in modo che $v_1<v_2<...<v_{n+3}$. Consideriamo gli n+2 elementi della forma $v_{i}+v_{i+1}, i<n+3$ e gli n+2 della forma $v_{i}+v_{i+2}, i<n+2$.
Dimostro che sono tutti diversi: $v_i+v_{i+1} \neq v_j+v_{j+1}$ se $i \neq j$; difatti supponendo, wlog, i<j, abbiamo $v_i<v_j,v_{i+1}<v_{j+1}$ pertanto addizionando $v_i+v_{i+1}<v_j+v_{j+1}$, analogamente si dimostra che $v_i+v_{i+2} \neq v_j+v_{j+2}$ se $i \neq j$. Resta il caso $v_{i}+v_{i+1} \neq v_{j}+v_{j+2}, \forall i,j$.Se i=j, allora $v_{i}+v_{i+1}<v_{i}+v_{i+2}$, se j<i allora $j+2 \leq i+1$ quindi essendo $v_j<v_i$ abbiamo $v_{j}+v_{j+2}<v_i+v_{i+1}$, se j>i allora $v_j>v_i,v_{j+2}>v_{i+1}$, quindi $v_{j}+v_{j+2}>v_i+v_{i+1}$. Pertanto abbiamo trovato n+2+n+1=2n+3 punti distinti(dividendo per 2 si hanno i punti medi).

Avatar utente
Tess
Messaggi: 258
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: "Ancora" con $2n+3$

Messaggio da Tess » 24 set 2013, 11:51

Bene, funziona!

Un altro modo per vederlo era quello di proiettare tutti i punti su una retta in modo che non ce ne fossero 2 che cadevano coincidenti. (che, sostanzialmente, allagerisce la tua dimostrazione della definizione di "<").

Un altro modo è usare il principio dell'estremale: prendere i 2 punti che hanno massima distanza, e far vedere che ogni altro genera un punto medio diverso con ciascuno di questi 2.

Rispondi