Numero de enteros positivos menores que 9999999 y la suma de sus dígitos sea 31

Es un problema de recuento yo creo que bastante largo. No sé si es que quieren que lo hagas así, o te dejan usar ordenador, o es que existe una teoría que desconozco que haga fáciles estos problemas o es que no es un problema de los estudios, pero la primera impresión que me llevo es que hay que operar mucho. Ayer contesté uno sobre las formas de meter 30 bolas en 6 cajas casi al libre albedrío y hubo que tirar de ordenador y programación. No digo que este sea tanto, pero quizá no se pueda hacer a mano.

Ahora no tengo tiempo para hacerlo, pero antes de cuando me ponga me gustaría que me dijeses eso de si hay alguna teoría especial o cómo habéis hecho problemas similares. Dime también el curso para hacerme una idea de los medios que se supone se pueden usar.

quieren que lo haga manualmente

Vale, son números de hasta 7 cifras con suma de dígitos 31. Los recontamos empezando por el más pequeño, con las cifras siempre en orden creciente y sin repetir el mismo conjunto de cifras. Y en cada caso calculamos después de cuántas formas se pueden reordenar esas cifras

0004999 PR(7; 3,3) = 7!/(3!3!) = 140

0005899 PR(7; 2,3) = 7!/(2!3!) = 420

Y así seguiríamos hasta el final. El problema es que ¡Hay 468 casos!

1 0004999
2 0005899
3 0006799
4 0006889
5 0007789
6 0007888
7 0013999
8 0014899
9 0015799
10 0015889
11 0016699
12 0016789
13 0016888
14 0017779
15 0017788
16 0022999
17 0023899
18 0024799
19 0024889
20 0025699
21 0025789
22 0025888
23 0026689
24 0026779
25 0026788
26 0027778
27 0033799
28 0033889
29 0034699
30 0034789
31 0034888
32 0035599
33 0035689
34 0035779
35 0035788
36 0036679
37 0036688
38 0036778
39 0037777
40 0044599
41 0044689
42 0044779
43 0044788
44 0045589
45 0045679
46 0045688
47 0045778
48 0046669
49 0046678
50 0046777
51 0055579
52 0055588
53 0055669
54 0055678
55 0055777
56 0056668
57 0056677
58 0066667
59 0112999
60 0113899
61 0114799
62 0114889
63 0115699
64 0115789
65 0115888
66 0116689
67 0116779
68 0116788
69 0117778
70 0122899
71 0123799
72 0123889
73 0124699
74 0124789
75 0124888
76 0125599
77 0125689
78 0125779
79 0125788
80 0126679
81 0126688
82 0126778
83 0127777
84 0133699
85 0133789
86 0133888
87 0134599
88 0134689
89 0134779
90 0134788
91 0135589
92 0135679
93 0135688
94 0135778
95 0136669
96 0136678
97 0136777
98 0144499
99 0144589
100 0144679
101 0144688
102 0144778
103 0145579
104 0145588
105 0145669
106 0145678
107 0145777
108 0146668
109 0146677
110 0155569
111 0155578
112 0155668
113 0155677
114 0156667
115 0166666
116 0222799
117 0222889
118 0223699
119 0223789
120 0223888
121 0224599
122 0224689
123 0224779
124 0224788
125 0225589
126 0225679
127 0225688
128 0225778
129 0226669
130 0226678
131 0226777
132 0233599
133 0233689
134 0233779
135 0233788
136 0234499
137 0234589
138 0234679
139 0234688
140 0234778
141 0235579
142 0235588
143 0235669
144 0235678
145 0235777
146 0236668
147 0236677
148 0244489
149 0244579
150 0244588
151 0244669
152 0244678
153 0244777
154 0245569
155 0245578
156 0245668
157 0245677
158 0246667
159 0255559
160 0255568
161 0255577
162 0255667
163 0256666
164 0333499
165 0333589
166 0333679
167 0333688
168 0333778
169 0334489
170 0334579
171 0334588
172 0334669
173 0334678
174 0334777
175 0335569
176 0335578
177 0335668
178 0335677
179 0336667
180 0344479
181 0344488
182 0344569
183 0344578
184 0344668
185 0344677
186 0345559
187 0345568
188 0345577
189 0345667
190 0346666
191 0355558
192 0355567
193 0355666
194 0444469
195 0444478
196 0444559
197 0444568
198 0444577
199 0444667
200 0445558
201 0445567
202 0445666
203 0455557
204 0455566
205 0555556
206 1111999
207 1112899
208 1113799
209 1113889
210 1114699
211 1114789
212 1114888
213 1115599
214 1115689
215 1115779
216 1115788
217 1116679
218 1116688
219 1116778
220 1117777
221 1122799
222 1122889
223 1123699
224 1123789
225 1123888
226 1124599
227 1124689
228 1124779
229 1124788
230 1125589
231 1125679
232 1125688
233 1125778
234 1126669
235 1126678
236 1126777
237 1133599
238 1133689
239 1133779
240 1133788
241 1134499
242 1134589
243 1134679
244 1134688
245 1134778
246 1135579
247 1135588
248 1135669
249 1135678
250 1135777
251 1136668
252 1136677
253 1144489
254 1144579
255 1144588
256 1144669
257 1144678
258 1144777
259 1145569
260 1145578
261 1145668
262 1145677
263 1146667
264 1155559
265 1155568
266 1155577
267 1155667
268 1156666
269 1222699
270 1222789
271 1222888
272 1223599
273 1223689
274 1223779
275 1223788
276 1224499
277 1224589
278 1224679
279 1224688
280 1224778
281 1225579
282 1225588
283 1225669
284 1225678
285 1225777
286 1226668
287 1226677
288 1233499
289 1233589
290 1233679
291 1233688
292 1233778
293 1234489
294 1234579
295 1234588
296 1234669
297 1234678
298 1234777
299 1235569
300 1235578
301 1235668
302 1235677
303 1236667
304 1244479
305 1244488
306 1244569
307 1244578
308 1244668
309 1244677
310 1245559
311 1245568
312 1245577
313 1245667
314 1246666
315 1255558
316 1255567
317 1255666
318 1333399
319 1333489
320 1333579
321 1333588
322 1333669
323 1333678
324 1333777
325 1334479
326 1334488
327 1334569
328 1334578
329 1334668
330 1334677
331 1335559
332 1335568
333 1335577
334 1335667
335 1336666
336 1344469
337 1344478
338 1344559
339 1344568
340 1344577
341 1344667
342 1345558
343 1345567
344 1345666
345 1355557
346 1355566
347 1444459
348 1444468
349 1444477
350 1444558
351 1444567
352 1444666
353 1445557
354 1445566
355 1455556
356 1555555
357 2222599
358 2222689
359 2222779
360 2222788
361 2223499
362 2223589
363 2223679
364 2223688
365 2223778
366 2224489
367 2224579
368 2224588
369 2224669
370 2224678
371 2224777
372 2225569
373 2225578
374 2225668
375 2225677
376 2226667
377 2233399
378 2233489
379 2233579
380 2233588
381 2233669
382 2233678
383 2233777
384 2234479
385 2234488
386 2234569
387 2234578
388 2234668
389 2234677
390 2235559
391 2235568
392 2235577
393 2235667
394 2236666
395 2244469
396 2244478
397 2244559
398 2244568
399 2244577
400 2244667
401 2245558
402 2245567
403 2245666
404 2255557
405 2255566
406 2333389
407 2333479
408 2333488
409 2333569
410 2333578
411 2333668
412 2333677
413 2334469
414 2334478
415 2334559
416 2334568
417 2334577
418 2334667
419 2335558
420 2335567
421 2335666
422 2344459
423 2344468
424 2344477
425 2344558
426 2344567
427 2344666
428 2345557
429 2345566
430 2355556
431 2444449
432 2444458
433 2444467
434 2444557
435 2444566
436 2445556
437 2455555
438 3333379
439 3333388
440 3333469
441 3333478
442 3333559
443 3333568
444 3333577
445 3333667
446 3334459
447 3334468
448 3334477
449 3334558
450 3334567
451 3334666
452 3335557
453 3335566
454 3344449
455 3344458
456 3344467
457 3344557
458 3344566
459 3345556
460 3355555
461 3444448
462 3444457
463 3444466
464 3444556
465 3445555
466 4444447
467 4444456
468 4444555

Vamos, para morirse. SI este es el método a usar te podría completar el programa para que calculase las reordenaciones de cada caso e hiciese la suma. Pero si estáis usando otro método, si me lo facilitas o explicas a lo mejor podría hacerlo con ese método, con este ya ves que es imposible a mano.

Tendré que desdecirme de lo dicho. Es tal la avalancha de problemas similares que me están llegando estos días que me he dado cuenta que el que fallaba era yo. Que había algo que no conocía y se usaba para resolver estos problemas.

Ese algo son las combinaciones con repetición, las conocía pero de mala manera, no como sacarles el jugo.

Hay una teoría que dice que dada una ecuación:

$$x_1+x_2+x_3+....+x_n=k$$

con k entero no negativo, el número de soluciones enteras no negativas de esa ecuación es

CR(n,k)

Yo lo estoy viendo aquí

<a>http://www.mat.upm.es/~pzz/docencia/grado/mtds/combinatoria_sin_pause4.pdf</a>

Pero tu lo tendrás en tu libro. Que por cierto no me vendría mal que me dijeras cuál es.

También nos dice como se calculan esas combinaciones con repetición.

CR(n,k) = C(n+k-1, k)

En nuestro problema n=7 y k=31

números posibles = C(7+31-1, 31) = C(37, 31) = C(37,6) =

37·36·35·34·33·32 / 6! = 167384480 / 720 = 2324784

Esos son los números posibles.

Y eso es todo.

Espera, que no está bien, porque con eso he metido respuestas donde las cifras podían ser mayores que 9. Espera que lo corrija, pero no va a ser muy rápidamente a lo mejor.

Antes de aprender cosas nuevas he completado el programa que es lo que mejor se me da y la respuesta que me da es 622734.

Veamos ahora a mano cuánto da.

Sea Ai = {soluciones donde la cifra i-esima >9} 1<=i<=9

Lo calculamos para A1. Si le restamos 10 a la cifra primera las soluciones son equivalentes al problema

(x1-10) +x2 + x3+···+ x7 = 21

x1' + x2 + x3 + ···+ x7 = 21

CR(7,21) = C(21+7-1, 21) = C(27,21) = C(27,6) =

27·26·25·24·23·22 / 720 = 213127200 / 720 = 296010

Para los otros seis Ai es la misma cuenta, cada Ai tiene 296010 elementos.

Pero no podemos coger y resta 7 veces eso y ya está, porque los Ai tienen intersecciones entre sí.

Veamos cuantos elementos tiene de intersección un Ai con in Aj. Son todos iguales por simetría lo haremos con A1 y A2

Si la primera y segunda cifra son mayores de 9 les restamos diez a cada una y queda la ecuación

(x1-10)+(x2-10)+x3+···+x7= 11

x1' + x2'+x3+...+x7 = 11

El numero de soluciones es

CR(7,11) = C(11+7-1,11) = C(17,11) = C(17,6) =

17·16·15·14·13·12 / 720 = 8910720 / 720 = 12376

Luego |Ai n Aj| =12376 donde n es el símbolo de intersección y el modulo es el número de elementos del conjunto.

Pero no nos quieren dejar descansar puesto que puede haber intersecciones entre tres conjuntos Ai ya que puede haber tres cifras mayores que 9. La ecuación quedará

x1'+x2'+x3'+x4+···+x7=1

Y las soluciones son

CR(7,1) = C(7+1-1,7) C(7,1) = 7

Pues vamos a calcular el cardinal de la unión de los 7 conjuntos Ai.

Cuando se unen varios conjuntos el cardinal es mejor que veas la fórmula en la Wikipedia

<a>http://es.wikipedia.org/wiki/Uni%C3%B3n_de_conjuntos</a>

Las combinaciones de 7 elementos tomadas de 1 en 1 son 7

Las combinaciones de los siete conjuntos tomadas de 2 en 2 son 21.

Tomadas de tres en tres son 35

Y la formula es

|A1 U A2 U A3...U A7| = 7 · 296010 - 21·12736 + 35·7 = 2072070 - 267456 + 245 = 1804859

Vamos a restar estas, que son las combinaciones con alguna cifra superior a 9 a las combinaciones totales que salían.

2324784 - 1804859 = 519925

Es una pena pero no coinciden.

Y la respuesta que me da un nuevo programa que simplemente los cuenta todos y ve cuales suman 31 es 512365.

Y esa es la respuesta auténtica, no hay otra, luego tendré que ver que pasó con el otro programa sofisticado que hice y todas las cuentas recién hechas mano.