Combinatoria

Giochini matematici elementari ma non olimpici.
Avatar utente
Francutio
Messaggi: 1104
Iscritto il: 17 feb 2008, 08:05
Località: Torino

Messaggio da Francutio » 16 mar 2010, 15:02

Sir Yussen ha scritto:Semplicemente valuto le possibili combinazioni considerando ogni volta un capo lettera diversa,e successivamente sottraggo dalla somma le combinazioni uguali in entrambi i casi con capolettera diversa....


Poi non è che è sicuro al 100% quel che dico,può anche darsi che mi sbaglio eh xD
Sì sbagli. Conti combinazioni che non valgono e ne dimentichi altre se ho capito (?) il tuo ragionamento (?)

Ad esempio CBAED l'hai contata?



EDCAB come la ottieni invece?



Clara, il simbolo che hai citato te adesso è il coefficiente binomiale. E "significa" fattoriale del numero sopra fratto il prodotto tra il fattoriale del numero sotto per il fattoriale della differenza dei due numeri

...è più facile vedere la formula :roll:

http://it.wikipedia.org/wiki/Coefficiente_binomiale

Avatar utente
Clara
Messaggi: 237
Iscritto il: 02 mar 2010, 14:21
Località: Roma

Messaggio da Clara » 16 mar 2010, 15:18

EDCAB è impossibile, lui l'ha contata?
Se l'assistente parte dalla E le altre 4 lettere ormai sono tutte impilate sotto e non può che fare E D C B A.


Grazie per la dritta! :wink:
Someone, somewhere, is always doing something someone else said was impossible.

Il pi greco è il George Clooney della matematica.

La bellezza di un esercizio è inversamente proporzionale al rapporto tra la sua difficoltà e la semplicità con cui è posto.

Avatar utente
Francutio
Messaggi: 1104
Iscritto il: 17 feb 2008, 08:05
Località: Torino

Messaggio da Francutio » 16 mar 2010, 15:29

Clara ha scritto:EDCAB è impossibile, lui l'ha contata?
Se l'assistente parte dalla E le altre 4 lettere ormai sono tutte impilate sotto e non può che fare E D C B A.
Lo so che è impossibile, ma se ho capito il suo ragionamento lui l'ha contata...per quello l'ho citata...

Mentre non ne ha contate altre...sempre che abbia capito il suo ragionamento eh, non son sicuro ^^

Prego, comunque :wink:

Dani92
Messaggi: 108
Iscritto il: 08 ott 2009, 18:32
Località: Trento

Messaggio da Dani92 » 16 mar 2010, 17:09

dario2994 ha scritto: E qui un hint per la soluzione:
deriva più o meno direttamente dalla conoscenza dei numeri di Catalan.
Leggiucchiateli su wiki... è abbastanza facile far corrispondere questo problema con il numero di percorsi sotto la bisettrice in un quadrato 5x5. Inoltre controllando bene su wiki compare anche questo stesso problema al nome stack-sortable permutations.

Non ho capito, puoi spiegarmi come ci entrano Catalan e l'idea del quadrato 5x5?

Grazie! :D

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 16 mar 2010, 17:54

Alur... dividiamo la giornata in 5 momenti precisi: i momenti in cui viene poggiata una lettera sulla scrivania.
Se la segretaria stampa dopo un momento o subito prima del successiva non cambia nulla... quindi associamo ad ogni momento il numero di lettere stampate tra quel momento e il successivo. Chiamo $ $a_i $ il numero dei documenti stampati all' i-esimo momento.Ad ogni sequenza di $ $a_j $ corrisponde un ordine di scrittura e viceversa. Ora contiamo gli $ $a_i $. Per comodità fisso $ $a_0=0 $.
Sono numeri interi.
Sono crescenti non strettamente.
$ $a_i\le i $
$ $a_5=5 $
Ora disegno sul piano cartesiano la funzione $ $a_x $ (ovviamente negli interi da 0 a 5)... poi connetto in questo modo i punti: da $ $(i,x_i) $ traccio un segmento fino a $ $(i+1,x_i) $ da qui traccio un segmento (se necessario) fino a $ $(i+1,a_{i+1}) $... sembra proprio che abbia disegno un percorso sotto la bisettrice in un quadrato 5x5 :shock: Ora è facile far corrispondere ad ogni percorso una sequenza... quindi ora tocca contare i percorsi, fortunatamente l'ha fatto qualcuno al posto mio e risulta incredibilmente essere 42.
Per quest'ultimo fatto vi rimando alla lettura dei numeri di Catalan.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio da gian92 » 16 mar 2010, 18:02

tra l'altro se non mki sbaglio questo stesso problema (o comunque molto simile) l'aveva fatto a roma callegari spiegando appunto i numeri di catalan e partendo dal problema dei percorsi della pulce sotto la bisettrice
mi sembra che con gli stessi numeri si risolva il problema di trovare in quanti modi un poligono convesso può essere diviso in triangoli.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 16 mar 2010, 18:34

Si Callegari aveva parlato dei numeri di Catalan, affrontandoci vari problemi (non quello dei poligoni) tra cui anche questo... però affrontato in un altro modo, ragionando con gli stack in informatica ;) Che è proprio come ne parla wiki.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Sir Yussen
Messaggi: 134
Iscritto il: 23 feb 2010, 16:28

Messaggio da Sir Yussen » 16 mar 2010, 20:59

Francutio ha scritto:
Sir Yussen ha scritto:Semplicemente valuto le possibili combinazioni considerando ogni volta un capo lettera diversa,e successivamente sottraggo dalla somma le combinazioni uguali in entrambi i casi con capolettera diversa....


Poi non è che è sicuro al 100% quel che dico,può anche darsi che mi sbaglio eh xD
Sì sbagli. Conti combinazioni che non valgono e ne dimentichi altre se ho capito (?) il tuo ragionamento (?)

Ad esempio CBAED l'hai contata?



EDCAB come la ottieni invece?



Clara, il simbolo che hai citato te adesso è il coefficiente binomiale. E "significa" fattoriale del numero sopra fratto il prodotto tra il fattoriale del numero sotto per il fattoriale della differenza dei due numeri

...è più facile vedere la formula :roll:

http://it.wikipedia.org/wiki/Coefficiente_binomiale
O_O mi sa proprio che non ho capito la traccia O_O

Avatar utente
Clara
Messaggi: 237
Iscritto il: 02 mar 2010, 14:21
Località: Roma

Messaggio da Clara » 17 mar 2010, 14:47

Ok, io ho provato a fare un ragionamento chilometrico, ma molto facile da capire, sfruttando l'idea di dario.
Il problema è che mi viene 41!!
Intanto lo posto qui, penso che la cosa più probabile, sia che mi sono persa qualcosa...

(Vi ho avvertito, è chilometrico! :wink: )

http://img221.imageshack.us/g/immagine1m.png/
Someone, somewhere, is always doing something someone else said was impossible.

Il pi greco è il George Clooney della matematica.

La bellezza di un esercizio è inversamente proporzionale al rapporto tra la sua difficoltà e la semplicità con cui è posto.

Avatar utente
Francutio
Messaggi: 1104
Iscritto il: 17 feb 2008, 08:05
Località: Torino

Messaggio da Francutio » 17 mar 2010, 16:21

Clara ha scritto:Ok, io ho provato a fare un ragionamento chilometrico, ma molto facile da capire, sfruttando l'idea di dario.
Il problema è che mi viene 41!!
Intanto lo posto qui, penso che la cosa più probabile, sia che mi sono persa qualcosa...

(Vi ho avvertito, è chilometrico! :wink: )

http://img221.imageshack.us/g/immagine1m.png/

Nella configurazione 3-2-0-0-0 ci sono 5 casi, e non 4


00023
00032
00203
00302
02003

Quello in grassetto è quello che credo tu abbia saltato.

Avatar utente
Clara
Messaggi: 237
Iscritto il: 02 mar 2010, 14:21
Località: Roma

Messaggio da Clara » 17 mar 2010, 19:13

Oh! Perfetto, grazie! :D
Ci si mette il triplo del tempo, così, ma è più semplice da capire.
Someone, somewhere, is always doing something someone else said was impossible.

Il pi greco è il George Clooney della matematica.

La bellezza di un esercizio è inversamente proporzionale al rapporto tra la sua difficoltà e la semplicità con cui è posto.

Avatar utente
Francutio
Messaggi: 1104
Iscritto il: 17 feb 2008, 08:05
Località: Torino

Messaggio da Francutio » 17 mar 2010, 22:40

Clara ha scritto:Oh! Perfetto, grazie! :D
Ci si mette il triplo del tempo, così, ma è più semplice da capire.
Ti capisco benissimo, anche io faccio sempre tutto a casi (o a caso, boh?) :lol:

Rispondi