alberi fruttiferi

[bestiedda]

tutti gli alberi del giardino di villa parravicini sono formati da 2003 rami (considerando il tronco come un ramo); inoltre ogni ramo si biforca in altri due rami, oppure termina con un frutto, oppure termina con due frutti. Tutti gli alberi hanno un solo tronco. Determinare la somma del numero minimo e del numero massimo di frutti che può avere l'albero

[Tibor Gallai]

Il problema viene dalla gara a squadre di Genova del 2003. E' più bello citare le fonti dei problemi, specialmente nei forum che potrebbero essere bazzicati dagli inventori stessi di tali problemi.

P.S. Oltretutto il testo me lo ricordavo leggermente meno ritardato. Sicuro di averlo trascritto esattamente?

[kn]

Mi viene un risultato piuttosto strano... Minimo = 1001 e massimo = 2004, quindi 3005.
Se è giusto metto la soluzione completa

[Tibor Gallai]

E' quasi giusto.
Se ti metti a scrivere la dimostrazione, trovi l'errore, IMHO.
In effetti il problema è abbastanza semplice, soprattutto se la risposta va solo "indovinata" e non dimostrata. Non so bene perché sia finito come ultimo problema... Credo che alla fine quasi tutte le squadre l'abbiano risolto, ed in confronto ha mietuto molte più vittime il problema 4 (il cucù impazzito), che curiosamente valeva 1/4 dei punti di questo qua.

[kn]

Pardon, il minimo deve essere 1002, quindi 3006. Ho provato anche un'altra strada che non passi per il calcolo di minimo e massimo e conferma 3006.

[Tibor Gallai]

Sìsì, hai il visto per poter iniziare a scrivere la dimostrazione.

[SkZ]

piu' che altro basta vedere come si procede per passare da una ramificazione ad un altra e vedere cosa cambia.

[kn]

Cerchiamo prima di costruire un albero con il minimo di frutti. Supponiamo che a ogni ramo venga trasmesso un numero n (che chiameremo "importanza"), uguale al numero dei rami che da lui dovranno discendere. Se n è diverso da 0 (e da 1, valore che n non può avere) si dividerà in due rami di cui la somma delle importanze sarà pari a $ \displaystyle~n-2 $. È ovvio che n deve essere pari, altrimenti il ramo (essendo n > 0) dovrebbe dividersi in un ramo di importanza pari e uno di importanza dispari (minore di n), che a sua volta ...; continuando a seguire i rami con importanza dispari si arriverebbe a un ramo che deve generare un solo figlio, assurdo.
Ora chiamiamo $ \displaystyle~m_n $ il minimo di frutti che originano un ramo di importanza n e la sua discendenza. Ovviamente $ \displaystyle~m_0=1 $. Ogni ramo con n > 0 sceglie fra tutte le combinazioni possibili, perciò $ \displaystyle~m_n=\min\{m_{0}+m_{n-2},~m_2+m_{n-4},~\dots\} $ (dato che i figli non possono avere importanza dispari).
Per induzione si dimostra che $ \displaystyle~m_{2n}=n+1 $ ($ \displaystyle~m_2=2=1+1 $, $ \displaystyle~m_{2n+2}=\min\{m_{2k}+m_{2n-2k},~\forall k\}=n+2=(n+1)+1 $, dato che tutti gli elementi dell'insieme sono uguali). Il minimo in totale è $ \displaystyle~m_{2002}=1002 $, con 2002 = importanza del tronco. Analogamente si deduce che il massimo $ \displaystyle~M_n=n+2 $, da cui che il massimo globale è 2004.

Un altro modo per concludere è ricordare che per il minimo i rami senza discendenti devono avere un solo frutto, quindi il numero di rami che danno frutti è sempre uguale al minimo di frutti, da cui che il massimo è il doppio del minimo.

Oppure ancora fin dall'inizio si possono considerare contemporaneamente massimo e minimo e trovare (sempre ricorsivamente) il totale $ \displaystyle~t_{2n}=M_{2n}+m_{2n}=3(n+1) $.