interi debolmente crescenti

[Noemi91x]

Un intero positivo si dice debolmente crescente se le sue cifre(in base 10) lette da sinistra verso destra,formano una successione debolmente crescente.Ad esempio ,13377 e 13568 sono numeri debolmente crescenti,mentre 10345 e 15466 non lo sono.Determinare quanti sono i numeri debolmente crescenti di 5cifre ( si intende che la cifra più a sinistra non può essere 0)

[jordan]

Sbaglio o è un vecchio Cesenatico? ( o al limite da un file molto reperibile nel glossario?) Ricordo questo problema perchè lo risolsi circa un tre anni fa caso per caso..la cosa ancora più triste era che il risultato che avevo ottenuto era giusto (Ora qualcuno che non ha visto la soluzione e lo risolve in maniera decorosa?)

[Noemi91x]

E' un esercizio del test del senior

[pak-man]

Consideriamo tutte le possibili sequenze di 5 cifre che formino numeri debolmente crescenti, e consideriamole come stringhe composte da 5 numeri (dato che le cifre arrivano fino a 9).
Trasformiamole in questo modo:
- la prima cifra resta invariata
- la seconda va aumentata di 1
- la terza di 2
- la quarta di 3
- la quinta di 4

Ad esempio, 1-3-5-6-8 --> 1-4-7-9-12 e 1-3-3-7-7 --> 1-4-5-10-11.

In questo modo si ottengono tutte stringhe con numeri necessariamente diversi tra di loro, perché i numeri iniziali sono disposti in maniera debolmente crescente, e più si va a destra più aumentano di valore dopo la trasformazione.

Quindi dobbiamo trovare quante sono le quintuple (a, b, c, d, e) con 0<a<b<c<d<e<14, che sono $ {13\choose5}=1287 $

È giusto?

[exodd]

solo che non va proprio così...

nel tuo calcolo assumi che a,b,c,d,e possono assumere 13,12,11,10,9 valori diversi, ma a va da 1 a 9, b da 2 a 10, e così via..

[Tenar]

Il primo numero di 5 cifre con la proprietà imposta dal testo è 11111; a questo punto facciamo variare l'ultima cifra, ottenendo i primi nove casi ( 11112,11113..)
Ora cambiamo la quarta in 2, le possibilità sono 11122,11123..ovvero altri 8 casi in quanto l'ultima cifra non può essere 1.
Continuiamo facendo variare la quarta cifra da 3 a nove, i casi possibili saranno quindi 7,6..in decrescendo fino a 1 (ovvero quando avremo il numero 11199) in modo da mantenere la successione decrescente tra le cifre.
(in tutto 45 casi)
Prendiamo ora la terza cifra, ottenendo il numero 11222 e operiamo gli stessi conti di cui sopra, ovvero facendo variare inizialmente l'ultima cifra ottenendo 8 casi, poi cambiando la quarta in 3 ottenendo 7 casi e così via fino al numero 11299.
(40 casi)
Quindi avremo
11111->11199 (45 casi)
11222->11299 (36 casi)
11333->11399 (28 casi)
11444->11499 (21 casi)
11555->11599 (15 casi)
11666->11699 (10 casi)
11777->11799 (6 casi)
11888->11899 (3 casi)
11999 (1 caso)
[tot=165]

Variamo ora la seconda cifra; dobbiamo contare quindi i casi da 12222 a 19999.
12222->12299 (36 casi)
12333->12399 (28 casi)
12444->12499 (21 casi)
...
12888->12899 (3 casi)
12999 (1 caso)
[tot=120]

Quindi avremo che:
11111->11999 (165 casi)
12222->12999 (120 casi)
13333->13999 (84 casi)
14444->14999 (56 casi)
15555->15999 (35 casi)
16666->16999 (20 casi)
17777->17999 (10 casi)
18888->18999 (4 casi)
19999 (1 caso)
[tot=495 casi]
Rimane da variare la prima cifra. Quindi andando a considerare i casi da 22222->99999.
Avremo:
22222->29999 (330 casi)
33333->39999 (210 casi)
44444->49999 (126 casi)
55555->59999 (70 casi)
66666->69999 (35 casi)
77777->79999 (15 casi)
88888->89999 (5 casi)
99999 (1 caso)

Infatti basta sfruttare il risultato ottenuto in precedenza, tenendo conto che, partendo da 22222 dovremo escludere i casi che prima avevamo calcolato per andare da 11111->11999 e così via.

In totale avremo quindi 1287 numeri con la proprietà richiesta ( a meno di possibilissimi errori di conto )

Ho perso più tempo a scriverlo che a farlo probabilmente

EDIT: Peraltro ottenendo lo stesso risultato di pak-man!

[pak-man]

solo che non va proprio così...

nel tuo calcolo assumi che a,b,c,d,e possono assumere 13,12,11,10,9 valori diversi, ma a va da 1 a 9, b da 2 a 10, e così via..

Dovrebbe essere giusto, perché sto scegliendo a caso 5 numeri da ordinare in maniera crescente, ottenendo tutte le combinazioni possibili.

Inoltre, 'b' è automaticamente >1, perché se nella quintupla scelta è presente un 1, questo valore è automaticamente assegnato ad 'a'