Numeri distinti su vertici adiancenti

[jordan]

Due numeri reali distinti sono scritti su ogni vertice di poligono convesso con $2012$ lati. Mostrare che si può rimuovere un numero da ogni vertice di modo tale che i numeri rimanenti su due vertici adiacenti sono sempre distinti.

[maurizio43]

Presumo di non avere interpretato bene il problema, o che manchi nel testo qualche condizione, perchè mi sembra un po' troppo semplice :
Indichiamo con :
$ 2N $ il numero dei vertici del poligono ; $ a_i $ il primo dei due numeri reali associati al vertice $ i-esimo $ ; $ b_i $ il secondo dei due numeri.
Le sequenze delle coppie di numeri associati ai vari vertici del poligono saranno :
$ a_1,a_2,a_3, ... ,a_{2N},a_{2N+1} $
$ b_1,b_2,b_3, ... ,b_{2N},b_{2N+1} $ ,
dove con $ a_{2N+1} $ e $ b_{2N+1} $ indichiamo per comodità la coppia associata al vertice $ 1 $ di partenza, cioè $ a_1 $ e $ b_1 $
Tutti gli $ a_i $ siano uguali tra loro $ ( = a ) $ e tutti i $ b_i $ siano uguali tra loro $ ( = b ) $ , con $ a $ diverso da $ b $ .

I vertici di ogni lato sono sempre uno di posto pari e uno di posto dispari.

Se per ogni $ i $ pari si cancella l' $ a_i $ corrispondente, e per ogni $ i $ dispari si cancella il $ b_i $ ( o viceversa), ogni lato risulta avere vertici associati a numeri distinti.
( ? )

[fph]

Non è l'unico caso - prendi per esempio un quadrato in cui hai scritto i numeri (1,2) (2,3) (3,4) (4,1). Non puoi riordinarli come asserisci tu.

[angelo3]

Testo nascosto:

Per induzione dovrebbe venire tranquillamente senza troppo sforzo (spero di non aver cannato la dimostrazione)

[karlosson_sul_tetto]

Testo nascosto:

Sbaglio o non funziona con un numero dispari di vertici? Oppure stai considerando il numero di vertici come $ 2n $ e induzione su n?

[maurizio43]

Infatti ho usato 2N, pari come l' iniziale 2012

[karlosson_sul_tetto]

Infatti ho usato 2N, pari come l' iniziale 2012

Era riferito alla risposta di angelo, ma mi ero dimenticato di specificarlo...

[Lasker]

Testo nascosto:

Anche io nel contest ho fatto l'induzione sui pari, considerando 36 comodi casi (di sicuro i 7 punti sono un miraggio, data la bruttezza della soluzione )

[scambret]

Altro modo: ogni vertice $v_i$ ha i reali $a_i,b_i$, indichiamo con $s_i$ il reale scelto sul vertice $v_i$. Sia inoltre $\mathcal{I}$ l'insieme di tutti i reali che compaiono sul poligono, ovviamente $2 \leq \# \mathcal{I} \leq 2024$
Se $\# \mathcal{I}=2$ allora dato che 2012 è pari c'è la faccio abilmente
Se $\# \mathcal{I} \neq 2$ allora numero i vertici tale che esiste $v_1$ un vertice avente wlog $b_{2012} \neq a_1 \neq a_{2012}$.
In questo caso sia $s_1=a_1$.
Ora per determinare $s_j$ lo determino ricorsivamente
- se $s_j=a_{j+1}$ allora $s_{j+1}=b_{j+1}$ e analogamente il caso contrario
- se $a_{j+1} \neq s_j \neq b_{j+1}$ allora $s_{j+1}$ a caso.
In questo modo $s_2$ dipende solo da $s_1$, ..., $s_{2012}$ dipende solo da $s_{2011}$ e in questo modo non ho creato lati cattivi (cioè con vertici adiacenti uguali), escluso il possibile caso $s_1=s_{2012}$, ma dato che $s_1=a_1$ e $a_1$ era diverso dai numeri che comparivano su $v_{2012}$ allora anche $s_{2012} \neq s_1$, che conclude

[Triarii]

La mia andava più o meno così, non so se ho sbagliato
1) Dimostro che una catena aperta ha almeno 2 configurazioni in cui varia almeno 1 far elemento finale e iniziale. (Discende dal fatto che preso un numero su un vertice, ne esiste almeno uno su quello adiacente diverso da questo)
2) Dimostro che è possibile chiuderla. Faccio induzione su 2n. Aggiungo in pratica 2 vertici al 2n-2-agono fra i vertici finale e iniziale che avevamo prima, e che per ipotesi induttiva ha scritti sui 2 vertici che prima si toccavano 2 numeri distinti a e b. Ora, l'unico casi in cui non riusciamo a chiudere il poligono è che abbiamo nei 2 nuovi vertici qualcosa del tipo (a,c) adiacante al vecchio vertice con a e (b,c) adiacente al vertice con b, che non ammette soluzioni chiaramente. Tuttavia grazie al punto 1 posso cambiare almeno 1 tra i vertici "vecchi". Cambio wlog a nell'altro numero scritto sull stesso vertice. Il caso più sfigato è che sia c, che ci costringe a scegliere sul vertice accanto c. Ora sul secondo vertice aggiunto possiamo scegliere b se anche b è variata per via del cambiamento di configurazione, oppure c se è rimasto uguale

[xXStephXx]

Volendo c'è un metodo abbastanza rapido che bene o male è equivalente a qualcuno già postato.
Parto da un vertice a caso che chiamo $O$ dove prendo un numero a caso e giro in senso orario. Per ogni vertice $X$ che trovo agisco in questo modo:
- Se sul vertice $X$ ho la scelta obbligata allora prendo il numero che sono costretto a prendere e passo al vertice $X+1$
- Se sul vertice $X$ ho entrambe le opzioni disponibili allora non prendo niente, ricomincio da $O-1$ stavolta girando in senso antiorario e agisco in modo analogo a prima con la differenza che stavolta se ho due opzioni prendo a caso (e non cambio giro).

EDIT: ah no, non funziona , ma tanto non ho usato questo metodo

[angelo3]

@karlosson: certo sì hai ragione scusate