Allora, dato che ci sono tante idee, ma le soluzioni complete latitano, cerco di scriverne una io.
<BR>
<BR>
<BR>Dati due interi n e k, quanti sono i sottoinsiemi di k elementi dell\'insieme {1,...,n} che non contengono due elementi consecutivi?
<BR>
<BR>
<BR> EDIT: Aaaargh! perché non funzionano i tags QUOTE? Ho usato
<BR> quelli dell\'icona predisposta...
<BR>
<BR>Claim: dico che il numero cercato è { n - k + 1 } \\choose k, con la convenzione usuale che a \\choose b vale 0 se b è negativo o a < b.
<BR>
<BR>Dimostro il claim per induzione su n.
<BR>
<BR>Per n = 0, 1 il claim è vero. Infatti nei casi n=k=0; n=1, k=0; n=k=; l\'unico sottoinsieme che, nei tre casi, soddisfa le ipotesi è, rispettivamente, \\empty; \\empty; {1}.
<BR>
<BR>Sia ora n>1 e suppondo il claim vero per n-1 e n-2. Contiamo gli insiemi che soddisfano l\'ipotesi suddividendo gli insiemi che non contengono l\'elemento n e quelli che lo contengono.
<BR>
<BR>I primi, sono esattamente i sottoinsiemi di k elementi di {1, ..., n-1} che soddisfano le ipotesi e quindi, per ipotesi induttiva, sono { n - k } \\choose k.
<BR>
<BR>I secondi, sono in corrispondenza biunivoca con i sottoinsiemi di k-1 elementi di {1, ..., n-2}, dove la corrispondenza è data dall\'aggiunta dell\'elemento n. Quindi, per ipotesi induttiva, sono { n - k } \\choose { k - 1 }.
<BR>
<BR>Ma allora, il numero cercato vale { n - k } \\choose k + { n - k } \\choose { k - 1 } = { n - k + 1 } \\choose k.
<BR>
<BR>Questo dimostra il claim.
<BR>
<BR>------
<BR>
<BR>Ho scritto questo messaggio non è tanto per dare nuove idee o rubare idee di altri; tuttavia, per fare bene le gare olimat, occorre anche sapere scrivere BENE una dimostrazione. A volte, vedere una dimostrazione scritta bene (o, meglio ancora, cercare di scriverne una), può insegnare qualcosa.
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>-------
<BR>
<BR>\"Well, master, we\'re in a fix and no mistake.\"
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: marco il 15-09-2004 10:54 ]