Le "catenelle"

[iademarco]

100 numeri interi la cui somma è uguale a 1 sono scritti su una circonferenza. Si chiama "catenella" una sequenza di numeri che si susseguono (la catenella può consistere di un sol numero). Qual è il numero di catenelle la cui somma delle cifre che la compongono è positiva?

[dario2994]

Facendo dei calcoli mi viene 4951... ma non ho la dimostrazione xD
Anzi io ero convinto che il risultato non fosse neanche univoco xD
Puoi specificare se il risultato è univoco così se è mi scervello a dimostrarlo xD

[SkZ]

a parte che per cifre penso tu intenda numeri, ma catenelle di 100 num?

[iademarco]

ma catenelle di 100 numeri?

(la catenella può consistere di un sol numero)

...quindi da uno in su...almeno credo
@dario2994: si è giusto, per ora posta il ragionamento, e poi cerca di dare una dimostrazione dell'univocità del risultato

[dario2994]

Alur... io ho assunto che il risultato fosse univoco e ho calcolato un caso: quello in cui c'è un 1 e tutti 0.
In questo caso bisogna contare tutte le catenelle che contengono 1... basta vedere che quelle da 1 numero, quelle da 2 sono 2, quelle da k sono k e quelle da 100 sono solo 1.
Da qui basta calcolare:
(99(100)/2)+1=4951
La dimostrazione di univocità non la saprei veramente fare :|

[julio14]

Il risultato è giusto, ma l'approccio è sbagliato... una dimostrazione così non vale praticamente nulla a ces.
Se vuoi un consiglio, non cercare tanto un motivo perché tutti gli altri casi dovrebbero essere equivalenti, semplicemente cerca la soluzione nel caso generale, senza curarti del caso particolare.

[giggiotb]

beh..la dimostrazione ke tutti i casi sn equivalenti è molto semplice..se così non fosse come si farebbe a dire se una risposta è buona o no?? Chi ha scritto il problema ha dovuto per forza calcolarlo,se no ke razza di propositore di problemi sarebbe??:lol: ..questa potevo risparmiarmela

[dario2994]

Bueno... dopo averci passato sopra una cifra di tempo ho finalmente concluso questo problema... tra l'altro l'ho trovato bellissimo (e parecchio difficile)
Pubblico anche questa dimostrazione in step così mi alleno xD

Step 0 Definizioni
$ L_n= $ Circonferenza con somma n
$ C= $ Catenelle totali
$ C_{+}= $ Catenelle con somma positiva
$ C_{-}= $ Catenelle con somma negativa
$ C_{0}= $ Catenelle con somma 0
$ C(a) $ Catenelle che contengono l'elemento a
$ a_n= $ nEsimo elemento della circonferenza

Step 1 Ragionamenti introduttivi
La circonferenza che considero è $ L_1 $, ma la si può anche definire una $ L_0 $ a cui all'elemento $ a_1 $ è stato aggiunto 1. Se si ragiona in questo modo la tesi del problema, e cioè calcolare quante sono $ C_{+} $ diventa calcolare quante sono le $ C_{+}+C_0(a_1) $, questo perchè diventano positive anche quelle che contengono $ a_1 $ ed erano neutre (+1).

Step 2 Analisi delle proprietà di $ L_0 $
$ L_0 $ ha una proprietà molto utile, cioè che $ C_{+}=C_{-} $. Si dimostra notando che la corrispondenza è biunivoca, cioè che per ogni $ C_{+} $ la catenella opposta (formata da gli altri elementi) è negativa, dato che la somma degli elementi è 0. La biunivocità è chiara quando si vede che è vero anche il contrario. $ C_0 $ invece non è ben definito ed è un numero che varia tra 1 e il massimo numero di catenelle. Per i precedenti ragionamenti si ottiene anche che $ C_{+}=C_{-}=\frac{C-C_0}{2} $ Questo deriva dal fatto che $ C_{+}+C_{-}+C_0=C $.

Step 3 Dimostrazione con dati generali
La tesi del problema chiede di trovare $ C_{+}+C_{0}(a_1) $, ora dimostrerò che questo valore equivale a $ \frac{C+1}{2} $. Per quanto detto nello step 2 vale l'uguaglianza $ C_{+}+C_0(a_1)=\frac{C-C_0}{2}+C_0(a_1) $. Ma $ C_0(a_1) $ equivale a $ \frac{C_0+1}{2} $ perchè per ogni $ C_0(a_1) $ esiste un $ C_0 $ di cui non fa parte $ a_1 $e cioè la catenella formata da tutti gli altri elementi (la somma fa 0 quindi se una è 0 lo anche l'altra) tranne che quando si considera la catenella massima, in quel caso esiste solo $ C_0(a_1)\Rightarrow C_0(a_1)=C_0(senza\ a_1)+1 $ ma dato che $ C_0(a_1)+C_0(senza\ a_1)=C_0\Rightarrow C_0(a+1)=\frac{C_0+1}{2} $. Sostituendo nell'espressione iniziale
$ C_{+}+C_0(a_1)=\frac{C-C_0}{2}+C_0(a_1)\Rightarrow C_{+}+C_0(a_1)=\frac{C-C_0}{2}+\frac{C_0+1}{2}\Rightarrow $
$ C_{+}+C_0(a_1)=\frac{C+1}{2} $.

Step 4 Conclusione
Tornando ad $ L_1 $ e ai dati del problema per quanto dimostrato in precedenza $ C_{+}=\frac{C+1}{2} $ e ora non rimane che calcolare $ C $. Per calcolarlo noto che di catenelle che contengono da 1 fino ad 99 elementi ne esistono 100 ognuna e cioè il possibile elemento iniziale, a queste va aggiunta la catenella da 100 elementi che ovviamente è unica. Perciò $ C=100\cdot 99+1=9901 $. Sostituendo nell'espressione iniziale ottengo: $ C_{+}=\frac{9901+1}{2}=4951 $ che è la tesi del problema.

Spero di non aver preso nessuno strafalcione enorme xD
p.s. questo problema è uno dei più carini che abbia mai affrontato... per curiosità da dove lo hai preso???

[iademarco]

p.s. questo problema è uno dei più carini che abbia mai affrontato... per curiosità da dove lo hai preso???

Dal libro "La matematica del club olimpico kangourou" di Marc Bachmakov
http://www.kangourou.it/catalogo.html
A mio parere, un magnifico libro sotto tutti i punti di vista

[Maioc92]

A mio parere, un magnifico libro sotto tutti i punti di vista

io non ce l'ho, però l'ho visto e da quel che mi ricordo dedica i 3/4 del libro a combinatoria e il restante quarto alle basi di analisi o mi sbaglio?

[dario2994]

Uhmm... quel libro me lo procurerò :)
Qualcuno può dire se la dimostrazione è giusta...

[iademarco]

A mio parere, un magnifico libro sotto tutti i punti di vista

io non ce l'ho, però l'ho visto e da quel che mi ricordo dedica i 3/4 del libro a combinatoria e il restante quarto alle basi di analisi o mi sbaglio?

Proprio i 3/4 non direi.
Forse è proprio per questo che ho detto che è un magnifico libro

[Maioc92]

allora forse ricordo male però comunque una buona parte sono sicuro. Comunque che sfiga l'anno scorso in cui nel kangourou sono andato male hanno regalato 1 libro e quest'anno che sono andato bene quel maledetto hitori.....io già odiavo il sudoku!!!!!

[dario2994]

Qualcuno mi conferma postando, via mp, mandandomi un sms, un email, un fax, un piccione viaggiatore o quello che gli pare se la dimostrazione è giusta... non vorrei aver toppato tutto e non essermene accorto...

[Maioc92]

scusa ma io ora sono troppo fuso per leggerla....domani mi prendo un po' di tempo e la leggo tutta