Un gioco di prestigio

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Un gioco di prestigio

Messaggioda Delfad0r » 30/08/2015, 8:02

Alberto sta mostrando a Barbara un gioco di prestigio di sua invenzione (o così dice lui...).
Barbara deve scegliere un numero intero $k$ compreso fra $1$ e $n$ (inclusi); poi Alberto le mostra una serie di carte, su ciascuna delle quali è scritta una lista di numeri; sarà poi sufficiente sommare i numeri in cima alle liste nelle quali è presente $k$ per ottenere $k$ stesso.
Barbara, però, si accorge molto presto del trucco: su ciascuna carta, infatti, è scritta una potenza di due, seguita da tutti i numeri ($\le n$) che hanno quella potenza nella loro rappresentazione binaria. La fanciulla propone allora ad Alberto la seguente restrizione: ordinando le carte secondo il primo elemento della lista di ciascuna, non devono mai apparire due numeri uguali su due carte consecutive; ad Alberto sorge spontanea una domanda: qual è il massimo $n=f(m)$ tale che il gioco è ancora realizzabile sotto questa restrizione e usando al più $m$ carte?
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Un gioco di prestigio

Messaggioda lucaboss98 » 30/08/2015, 15:17

ALBERTO MENTE
Allora $f(1)=1$ e $f(2)=2$.
Supponiamo che con $m$ "avanzo" al più di $f(m)$ . Prendiamo una configurazione qualsiasi che arrivi fino a $x\leq f(m)$ . Aggiungendoci una carta di primo elemento $y$ si deve avere $y\leq x+1$ per poter coprire $x+1$ , dunque otterrò come massimo un numero $\leq x+1+f(m-1) \leq f(m)+f(m-1)+1$ . Ma quindi (visto che se prendo come configurazione iniziale quella con $f(m)$ e metto $y=f(m)+1$ ci arrivo si ha $f(m+1)=f(m)+f(m-1)+1$.
Sia ora Fibonacci con $F(0)=0$ e $F(1)=1$ si ha che $f(1)+1$ rispetta ed è fibonacci traslato. Ovvero $f(n)=F(n+2)-1$.
Spero di non aver commesso idiozie :D ps: cosa probabile
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: Un gioco di prestigio

Messaggioda Delfad0r » 30/08/2015, 16:50

Premesso che ho dovuto leggere 5 o 6 volte il messaggio prima di capire il contenuto :mrgreen: il risultato è giusto.
Riesci a costruire esplicitamente le liste sulle carte (o comunque a dimostrare che effettivamente con $f(m)=F(m+2)-1$ si riesce (a meno che tu non l'abbia già fatto e che mi sia sfuggito, cosa plausibile data la difficoltà che ho avuto a decifrare il messaggio ^^))?
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Un gioco di prestigio

Messaggioda lucaboss98 » 30/08/2015, 17:52

beh per induzione si fa, cioè supponi che con $m$ carte arrivi a $F(m+2)-1$ allora ci piazzi $F(m+2)$ come primo sul numero (sull'$m+1$ esima carta) . In questo modo fai $f(m)+1+z$ dove $z$ è un qualsiasi numero in $\{ 0 , 1 \ldots F(m+1)-1 \} $ dunque arrivi a $F(m+1)+F(m+2)-1=F(m+3)-1$.
Non scrivo gli altri numeri che mette su ogni carta perchè basta aggiungerli opportunamente!
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite