OliForum Matematico

E' giusta la soluzione di piever. Era un problema di 3 media preso da un libro russo.

Due falegnami hanno ricevuto un ordinazione. Per portare a termine l'ordinazione
al primo serviranno 7 ore in più del secondo. Dopo che insieme hanno completato
metà dell'ordinazione, continua a lavorare soltanto il secondo falegname e
alla fine risulta che l'ordinazione è stata completata con 4,5 ...

Si, esatto hai scelto la strada un pò più lunga però ok.

\sum_{k=0}^{[\frac{n}{2}]}{n-k \choose k} = F_{n+1}

Dove F_{n+1} è l'(n+1)-esimo numero di Fibonacci! Tra l'altro per dimostrare che la sommatoria è uguale a F_{n+1} , si può ragionare nel seguente modo:

Con a_n indichiamo il numero di ...

Ok, scusa tanto, penserò allora alla dimostrazione. E scusate anche per il "qual'è", ogni tanto scrivendo veloce si può anche sbagliare, la prossima volta sarò più preciso nelle mie risposte.

Se non ho sbagliato i conti dovrebbe essere, la max lunghezza (3*n) e tutte le possibili parole $ 2^{n-1}\cdot n! $

Si può dimostrare così:
Ho una array di n elementi, supponiamo n sia pari:
n = 6:

a1 a2 a3 a4 a5 a6

faccio un confronto a 2 a due tra i termini dell'array, cioè confronto i termini:

[a1,a2] [a3,a4] [a5,a6]

Dopo il confronto so qual'è il più grande o il più piccolo, quindi confronto il più grande ...

[Mi raccomando i titoli: se si trova nella categoria "combinatoria", è ovvio che debba essere un problema di combinatoria.... M.]
-------------------------

Salve, volevo proporvi un problemino semplice ma carino:

Supponiamo di avere una parola lunga n, composta dalle lettere A e B.
Quante sono ...

Il numero di tutti i possibili sottoinsiemi di r elementi sono C(n,r) dove con C(n,r) indico le combinazioni di n elementi su k posizioni (il coefficiente binomiale). Adesso enumeriamo tutti i possibili minimi. Ad esempio se volessimo che il minimo dei sottoinsiemi sia 1, allora tutti gli insiemi ...

Esatto! E' vera anche la tua ultima affermazione, in quanto si può sempre costruire la matrice A per qualsiasi relazione di ricorrenza lineare. Corretta anche la generalizzazione di f(k), io avevo usato f(k) = k^3 per rendere le cose un pò più semplici.

Ops scusa hai ragione:
ridefiniamo i casi base:

F_0 = 0

F_1 = 1

F_ 2 = 1
.
.
.
F_{k-1} = 1

Adesso sono k casi base.

Ciao, forse non ho capito bene:
1. Se M = 1 (tutti i berretti dello stesso colore), gli N bambini si possono distintinguere tra di loro oppure no? Quindi se non si distinguono il numero di girotondi dovrebbe essere N.

2. M è il numero dei colori distinti, e se M<N ci saranno sicuramente 2 bambini ...

Per k = 2 il tuo ragionamento è corretto. Adesso prova ad estendere il ragionamento per k generico, se vogliamo essere più precisi l'upper bound dell'algoritmo è O(log n) se consideriamo k una costante, altrimenti sarà O(k^3 log n).

Ciao a tutti, mi sono appena iscritto e questo è il mio primo post nel forum. Volevo proporvi un problema che a me è sembrato abbastanza carino:

Definiamo il numero n-esimo di K-Bonacci nel seguente modo:

F_{n} = F_{n-1} + F_{n-2} + F_{n-3} + ... + F_{n-k}

F_{1} = 1
F_{2} = 1
F_{3} = 1
.
.
F_{k ...