eh, missà che hai ragione, ho fatto una svista nel mio.
correggo per la posterità ma il prossimo spetta a te.
Staffetta combinatoria.
Per me era tuo, comunque senza perdere tempo posto il prossimo.
Problema 5:
Siano $ $A$ $ ed $ $E$ $ due vertici opposti di un ottagono. Una rana parte dal vertice $ $A$ $. Da ogni vertice diverso da $ $E$ $ può saltare su uno dei due vertici adiacenti. Quando arriva ad $ $E$ $ si stoppa. Sia$ $a_n$ $ il numero di percorsi di $ $n$ $ salti che terminano in $ $E$ $ dimostrare che $ \displaystyle a_{2n-1}=0 $, $ \displaystyle a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}} $
Problema 5:
Siano $ $A$ $ ed $ $E$ $ due vertici opposti di un ottagono. Una rana parte dal vertice $ $A$ $. Da ogni vertice diverso da $ $E$ $ può saltare su uno dei due vertici adiacenti. Quando arriva ad $ $E$ $ si stoppa. Sia$ $a_n$ $ il numero di percorsi di $ $n$ $ salti che terminano in $ $E$ $ dimostrare che $ \displaystyle a_{2n-1}=0 $, $ \displaystyle a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}} $
Numeriamo i lati con 1 e -1 in modo che: AB, AH, GF, CD siano 1, mentre BC, HG, FE, ED siano -1. Per arrivare ad E devo "sendere" di 4, perciò la somma dei lati che ho percorso mi darà sempre 0.Jessica92 ha scritto:Per me era tuo, comunque senza perdere posto il prossimo.
Problema 5:
Siano $ $A$ $ ed $ $E$ $ due vertici opposti di un ottagono. Una rana parte dal vertice $ $A$ $. Da ogni vertice diverso da $ $E$ $ può saltare su uno dei due vertici adiacenti. Quando arriva ad $ $E$ $ si stoppa. Sia$ $a_n$ $ il numero di percorsi di $ $n$ $ salti che terminano in $ $E$ $ dimostrare che $ \displaystyle a_{2n-1}=0 $, $ \displaystyle a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}} $
Dico che faccio un percorso a destra se l'ultimo lato che percorro è DE, altrimenti faccio un percorso a sinistra, quindi $ a_{2n}=4a_{2n-2}-2a_{2n-4} $.
Infatti con $ 2n $ mosse posso allungare il percorso facendo "avanti e indietro" su un lato. Lo posso fare su i tre a sinistra o a destra di A (rispettivamente se faccio un percorso a sinistra o a destra) e in ogni caso su quelli adiacenti ad A, che in totale sono 4. A questi devo togliere i 2 allungamenti doppi che sono $ 2a_{2n-4} $
A questo punto il tutto dovrebbe seguire per con una facile verifica per induzione.
EDIT: che forse è meglio fare:
se la formula è vera per i numeri fino ad $ n $ allora si ha che:
$ \displaystyle a_{2n+2}=4\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}}-2\frac{(2+\sqrt{2})^{n-2}-(2-\sqrt{2})^{n-2}}{\sqrt{2}}= \frac{(2+\sqrt{2})^{n}-(2-\sqrt{2})^{n}}{\sqrt{2}} $, poichè la formula è vera per $ n=2,3 $ è vera per ogni $ n\ge2 $
ehmm..scusate ho scritto un po' di scemenze... ignoratemi
Forse ho trovato una soluzione:
chiamo con $ b_{2n} $ i percorsi che posso fare da C o da G fino ad E.
$ $a_{2n}=2a_{2n-2}+2b_{2n-2}$ $. Infatti le prime due mosse che posso fare sono o nello stesso senso o in senso opposto, quindi, se sono nello stesso senso mi ritrovero o in C o in G ( e allora ho $ $b_{2n-2}$ $ percorsi), se sono in senso opposto mi ritroverò di nuovo in A ( e allora ho $ $a_{2n-2}$ $ percorsi).
$ $b_{2n}=2b_{2n-2}+a_{2n-2}$ $, vale un discorso analogo:
col le prime due mosse da C o da G mi posso ritrovare di nuovo in C o in G (rispettivamente) in due casi e in A in un caso (ho supposto che $ $n>1$ $ perchè altrimenti sarei dovuto andare dritto in E)
Ora sottraggo membro a membro le due uguaglianze ottenute e ottengo: $ $a_{2n}-b_{2n}=a_{2n-2}$ $, $ $b_{2n}=a_{2n}-a_{2n-2}$ $, per cui, sostituendo $ $b_{2n}$ $ nella prima uguaglianza ho:
$ $a_{2n}=4a_{2n-2}-2a_{2n-4}$ $. A questo punto tutto, se è giusto, tutto dovrebbe filare seguendo quello che ho scritto prima.
Che ne pensate?
chiamo con $ b_{2n} $ i percorsi che posso fare da C o da G fino ad E.
$ $a_{2n}=2a_{2n-2}+2b_{2n-2}$ $. Infatti le prime due mosse che posso fare sono o nello stesso senso o in senso opposto, quindi, se sono nello stesso senso mi ritrovero o in C o in G ( e allora ho $ $b_{2n-2}$ $ percorsi), se sono in senso opposto mi ritroverò di nuovo in A ( e allora ho $ $a_{2n-2}$ $ percorsi).
$ $b_{2n}=2b_{2n-2}+a_{2n-2}$ $, vale un discorso analogo:
col le prime due mosse da C o da G mi posso ritrovare di nuovo in C o in G (rispettivamente) in due casi e in A in un caso (ho supposto che $ $n>1$ $ perchè altrimenti sarei dovuto andare dritto in E)
Ora sottraggo membro a membro le due uguaglianze ottenute e ottengo: $ $a_{2n}-b_{2n}=a_{2n-2}$ $, $ $b_{2n}=a_{2n}-a_{2n-2}$ $, per cui, sostituendo $ $b_{2n}$ $ nella prima uguaglianza ho:
$ $a_{2n}=4a_{2n-2}-2a_{2n-4}$ $. A questo punto tutto, se è giusto, tutto dovrebbe filare seguendo quello che ho scritto prima.
Che ne pensate?
Problema 6 In una gara ci sono $ $a$ $ partecipanti e $ $b$ $ giudici, dove $ $b\ge 3$ $ è un intero dispari. Ogni giudice vota ogni partecipante o con "pass" o con "fail". Supponiamo che $ $k$ $ sia un numero tale che, comunque presi due giudici, i loro voti coincidano al massimo per $ $k$ $ partecipanti. Dimostrare che $ $\frac{k}{a}\ge \frac{b-1}{2b}$ $
Trascuro l'appartenenza delle variabili, spero si capisca.
$ n_{i,j} $ vale 1 se l'j-esimo giudice ha votato pass l' i-esimo partecipante altrimenti vale 0.
Double-conto: $ $S=|\{x,y<z|n_{x,y}=n_{x,z}\}| $
Definisco $ $f(y,z)=|\{x|n_{x,y}=n_{x,y}\}| $ con y<z. Per definizione f(y,z) sono i voti uguali tra l'y-esimo e il z-esimo giudice, quindi k è maggiore del maggiore dei f(y,z) e quindi anche della media. Inoltre vale:
$ $\sum_{y< z}f(y,z)=S $
Definisco $ $g(x)=|\{y<z|n_{x,y}=n_{x,z}\}| $. Per definizione g(x) è il numero di coppie di voti uguali dati ad uno studente. Quindi se chiamo $ $p_x $ i pass che ha ottenuto e $ $f_x $ i fail che ha preso l'x-esimo studente vale: $ $g(x)={p_x\choose 2}+{f_x\choose 2} $. Inoltre vale:
$ $\sum_xg(x)=S $.
Da tutti i ragionamenti fatti posso dire (alla fine sfrutto il fatto che se la somma è data il minimo della somma dei quadrati sia raggiunge "nel mezzo"):
$ $ k\ge \frac{\sum_{y\not=z}f(y,z)}{{b\choose 2}}=\frac{\sum_x {p_x\choose 2}+{f_x\choose 2}}{{b \choose 2}}\ge \frac{a\left( min\{{p_x\choose 2}+{f_x\choose 2}\}\right)}{{b \choose 2}}\ge \frac{a\left(\frac{(\frac{b+1}{2})^2+(\frac{b-1}{2})^2-b}{2}\right)}{{b \choose 2}}=a\frac{b-1}{2b} $
Da cui viene la tesi.
Mi scuso se ho saltato qualche passaggio, ma i fatti importanti ho provato a dirli tutti...
$ n_{i,j} $ vale 1 se l'j-esimo giudice ha votato pass l' i-esimo partecipante altrimenti vale 0.
Double-conto: $ $S=|\{x,y<z|n_{x,y}=n_{x,z}\}| $
Definisco $ $f(y,z)=|\{x|n_{x,y}=n_{x,y}\}| $ con y<z. Per definizione f(y,z) sono i voti uguali tra l'y-esimo e il z-esimo giudice, quindi k è maggiore del maggiore dei f(y,z) e quindi anche della media. Inoltre vale:
$ $\sum_{y< z}f(y,z)=S $
Definisco $ $g(x)=|\{y<z|n_{x,y}=n_{x,z}\}| $. Per definizione g(x) è il numero di coppie di voti uguali dati ad uno studente. Quindi se chiamo $ $p_x $ i pass che ha ottenuto e $ $f_x $ i fail che ha preso l'x-esimo studente vale: $ $g(x)={p_x\choose 2}+{f_x\choose 2} $. Inoltre vale:
$ $\sum_xg(x)=S $.
Da tutti i ragionamenti fatti posso dire (alla fine sfrutto il fatto che se la somma è data il minimo della somma dei quadrati sia raggiunge "nel mezzo"):
$ $ k\ge \frac{\sum_{y\not=z}f(y,z)}{{b\choose 2}}=\frac{\sum_x {p_x\choose 2}+{f_x\choose 2}}{{b \choose 2}}\ge \frac{a\left( min\{{p_x\choose 2}+{f_x\choose 2}\}\right)}{{b \choose 2}}\ge \frac{a\left(\frac{(\frac{b+1}{2})^2+(\frac{b-1}{2})^2-b}{2}\right)}{{b \choose 2}}=a\frac{b-1}{2b} $
Da cui viene la tesi.
Mi scuso se ho saltato qualche passaggio, ma i fatti importanti ho provato a dirli tutti...
...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
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
Mi scuso per il ritardo, non sono riuscito a trovare nulla di originale per la staffetta, perciò pongo un problema che sta sul forum da un pezzo ma che nessuno ha mai risolto e io vorrei tanto vedere una soluzione dato che ci ho sbattuto la testa parecchio...
viewtopic.php?t=13450
viewtopic.php?t=13450
...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
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
-
Spammowarrior
- Messaggi: 282
- Iscritto il: 23 dic 2009, 17:14
uhm, mi pareva di avere visto in giro un problema simile a quello...
provo a risolverlo.
n pari, inizia A.
copro la scacchiera con tessere del domino messe in orizzontale (posso farlo perchè è un quadrato di lato pari)
A fa la prima mossa rimanendo sulla stessa tessera del domino, B è obbligato a cambiare tessera.
ragioniamo per "induzione":
nella coppia di mosse 1 A occupa tutta la tessera 1, B si deve muovere sulla tessera 2 (con 2 intendo la seconda, può ovviamente essere qualunque)
supponiamo che questo succeda in tutte le mosse fino alla n-esima, ragioniamo sulla n+1-esima:
B si è spostato su una tessera nuova, e A può rimanere sulla stessa tessera, perchè in ogni mossa ha "bruciato" la tessera (quindi se B ha mosso sulla tessera, vuole dire che l'altro quadrato è libero). di conseguenza B dovrà per forza cambiare tessera.
quindi A può sempre muovere. di conseguenza, visto che il gioco finisce in un numero finito di mosse (poichè ci sono finite posizioni), sarà B per primo a non avere mosse.
N dispari:
metto un quadratino singolo sull'angolo in alto a sinistra (quello su cui si comincia), e copro tutti gli altri con tessere del domino (è possibile per esempio riempiendo la prima riga in orizzontale, la prima colonna in verticale e poi tutte in orizzontale (è un quadrato di lato pari, vedi sopra).
A è obbligato a finire sulla tessera nuova, e B può rimanere sulla stessa.
si ragiona in maniera analoga a prima, e si vede che B ha sempre una strategia vincente (cioè la stessa di A per n pari)
provo a risolverlo.
n pari, inizia A.
copro la scacchiera con tessere del domino messe in orizzontale (posso farlo perchè è un quadrato di lato pari)
A fa la prima mossa rimanendo sulla stessa tessera del domino, B è obbligato a cambiare tessera.
ragioniamo per "induzione":
nella coppia di mosse 1 A occupa tutta la tessera 1, B si deve muovere sulla tessera 2 (con 2 intendo la seconda, può ovviamente essere qualunque)
supponiamo che questo succeda in tutte le mosse fino alla n-esima, ragioniamo sulla n+1-esima:
B si è spostato su una tessera nuova, e A può rimanere sulla stessa tessera, perchè in ogni mossa ha "bruciato" la tessera (quindi se B ha mosso sulla tessera, vuole dire che l'altro quadrato è libero). di conseguenza B dovrà per forza cambiare tessera.
quindi A può sempre muovere. di conseguenza, visto che il gioco finisce in un numero finito di mosse (poichè ci sono finite posizioni), sarà B per primo a non avere mosse.
N dispari:
metto un quadratino singolo sull'angolo in alto a sinistra (quello su cui si comincia), e copro tutti gli altri con tessere del domino (è possibile per esempio riempiendo la prima riga in orizzontale, la prima colonna in verticale e poi tutte in orizzontale (è un quadrato di lato pari, vedi sopra).
A è obbligato a finire sulla tessera nuova, e B può rimanere sulla stessa.
si ragiona in maniera analoga a prima, e si vede che B ha sempre una strategia vincente (cioè la stessa di A per n pari)
A te il prossimo-
Spammowarrior
- Messaggi: 282
- Iscritto il: 23 dic 2009, 17:14
