Punti colorati [Mathlinks]

Marco · Messaggio da **Marco** » 06 giu 2006, 16:29

Problema proposto da un tizio armeno.

Abbiamo 2n-1 punti allineati. Ogni punto è colorato bianco o nero. Per ogni punto calcoliamo il numero di punti bianchi alla sua destra più il numero di punti neri alla sua sinistra. Otteniamo così 2n-1 valori.

Supponiamo che facendo ciò, ci sia un unico numero che compare un numero dispari di volte. Quali sono le possibilità per tale numero?

VINXENZ · Messaggio da **VINXENZ** » 07 giu 2006, 13:48

Le possibilità dovrebbero essere:
(2n-1)!/(n!(n-1)!)
ovvero tutte le combinazioni possibili su 2n-1 elementi essendo il numero dei punti di un colore uguale al numero dei punti dell'altro colore più uno.
Ma non so dimostrarlo.[/tex][/code]

Marco · Messaggio da **Marco** » 07 giu 2006, 15:08

Hmm... claim interessante: il numero di punti bianchi è uno in più [o in meno] di quello dei punti neri....

Attento però: il problema non ti chiede in quanti modi possono essere disposti, ma quali valori può prendere l'unico totale che compare un numero dispari di volte [ma se sei arrivato a formulare il tuo guess, non dovresti far fatica a congetturare la risposta...]

VINXENZ · Messaggio da **VINXENZ** » 07 giu 2006, 19:14

Allora il valore del totale dovrebbe essere n-1.
Sembra che se la differenza tra il numero dei punti di diverso colore aumenta di k
aumenta di k anche il numero dei totali che appaiono dispari volte .

Marco · Messaggio da **Marco** » 08 giu 2006, 08:42

Ok. n-1 è la risposta corretta. Chi si butta a provare a dimostrarlo?

VINXENZ · Messaggio da **VINXENZ** » 09 giu 2006, 01:18

Come si dimostra?
Sapresti dimostrare le mie congetture?

Marco · Messaggio da **Marco** » 09 giu 2006, 08:29

Dai tuoi msg mi sembra di capire che hai sperimentato che se bianchi - neri = +/-k, allora i valori distinti che compaiono un numero dispari di volte sono k.

Sapresti trovare una combinazione con k punti bianchi in più rispetto ai punti neri, in cui è facile calcolare i valori? La più facile che ti viene in mente...

VINXENZ · Messaggio da **VINXENZ** » 09 giu 2006, 15:29

bnbnb
k=1
bnbnb b
k=2
bnbnbb bb
.....
k=n
bnbnbb ....bb(n*(n-1)/2 volte)

Marco · Messaggio da **Marco** » 12 giu 2006, 08:39

Ah, beh, anche queste, certo, ma io pensavo a qualcosa di ancora più semplice:

Se metti k pietre bianche e 0 nere, ottieni tutti i valori da 0 a k-1 (quindi k valori che compaiono un numero dipari di volte). Ok?

Adesso, se hai una situazione con bianche = n + k e nere = n, come fai a passare ad una situazione con bianche = (n+1) + k e nere = (n+1)?

Inducete gente, inducete...

VINXENZ · Messaggio da **VINXENZ** » 12 giu 2006, 16:56

quindi?

Marco · Messaggio da **Marco** » 13 giu 2006, 11:14

Prova a dimostrare il seguente

Lemma: Inserendo una palla bianca e una palla nera consecutive (in qualunque posizione e in qualunque ordine), compare una coppia di valori identici e tutti gli altri valori aumentano di 1.