Enigme Couper un gogol en 3 ! @ Prise2Tete

titoufred · #1

Combien y a-t-il de façons décomposer un gogol sous la forme d'un produit de 3 entiers naturels ?

Autrement dit, de combien de façons peut-on écrire [latex]10^{100}[/latex] sous la forme d'un produit [latex]abc[/latex] de 3 entiers naturels avec [latex]a \leq b \leq c[/latex] ?

fix33 · #2

Ca revient à savoir combien il existe de façons de partager en 3 lots, 100 chiffres "2" + 100 chiffres "5".
La suite 10^n commence semble-t-il par 2, 8, 19, 39 42, ... Le site OEIS me trouve A101427, mais pas de formule
La combinatoire de ce niveau va me nécessiter quelques heures de réflexion !!

nodgim · #3

Je proposerais bien 4 423 332 partitions possibles, mais c'est sans garantie...

titoufred · #4

@fix33 : effectivement, c'est un bon début.

@nodgim : c'est presque ça, tu es tout tout près.

Fito11235 · #5

Coucou,

La décomposition en facteurs premiers d'un gogol nous donne 100 facteurs 2 et 100 facteurs 5 soit 201 facteurs avec 1 inclus.

Reste à savoir combien de façons de faire 3 groupes avec 201 éléments… je ne suis plus sûr, est le nombre de Stirling S (3;201) ?

titoufred · #6

@Fito11235 : Je ne pense pas qu'il faille compter le 1. Essaye d'abord avec 10, 100, 1000...

NickoGecko · #7

Bonsoir,

10^100 = 2^100 * 5^100

2^100 possède 101 diviseurs (1 compris), les puissances successives de 2 ...
On peut écrire 2^100 sous la forme ab de 101x100 sortes différentes

de la même façon
5^100 possède 101 diviseurs (1 compris), les puissances successives de 5 ...

Je dirais donc que l'on peut écrire 10^100 sous la forme d'un produit abc de
101x100x101 soit 1020100 façons différentes.

A bientôt

titoufred · #8

@NickoGecko : ce n'est pas ça. Essaye d'abord avec 10, 100 et 1000.

Milou_le_viking · #9

C'est la suite du problème avec les pavés ?
Je préfère celui-ci. ;-)

scarta · #10

Pour tout x, y entre 0 et N, a = 2^x*5^y divise 2^N
Donc bc = 2^(N-x)*5^(N-y), qui comporte (N+1-x)*(N+1-y) diviseurs

Total = somme(somme((N+1-x)*(N+1-y), y=0..N), x=0..N)
= somme((N+1-x)*somme((N+1-y), y=0..N), x=0..N)
= somme((N+1-x), x=0..N)*somme((N+1-y), y=0..N)
= somme(x, x=1..N+1)*somme(y, y=1..N+1)
= somme(x, x=1..N+1)^2 = (N+1)^2(N+2)^2/4

Parmi ceux-là, il existe "quelques" doublons:
- Dans le cas d'un N multiple de 3, 10^N est un cube et le triplet (a,a,a) existe, mais il est unique
- Dans le cas où N-x et N-y sont pairs, il existe un triplet (a, b, b) qui apparait 3 fois dans notre décompte, sous les formes (a, b, b); (b, a, b) et (b, b, a)
- Dans tous les autres cas, les triplets (a, b, c) sont présents 6 fois, en permutant chacun des éléments.

Dans un cas où N est pair et n'est pas un multiple de 3 (comme N=100 par exemple):
- on n'a pas de cas "cubique"
- les cas où N-x et N-y sont pairs sont au nombre de (1+N/2)^2 = (N+2)^2/4
- les autres cas apparaissent 6 fois.
Au total on a donc
- ((N+1)(N+2))^2/4 : total avec doublons
- ((N+1)(N+2))^2/12 : on élimine ceux qui apparaissent 3 fois, et la moitié de ceux qui apparaissent 6 fois
- ((N+1)(N+2))^2/12 - (N+2)^2/4 : ceux qui apparaissent 6 fois, chacun compté en double
- (((N+1)(N+2))^2/12 - (N+2)^2/4)/2 + (N+2)^2/4 en enlevant les derniers doublons et en rajoutant ceux qui apparaissaient 3 fois

On simplifie :
(((N+1)(N+2))^2/12 - (N+2)^2/4)/2 + (N+2)^2/4 =
(((N+1)(N+2))^2/12 + (N+2)^2/4)/2 =
((N+1)(N+2))^2/24 + (N+2)^2/8 =
((N+2)^2 (3 + (N+1)^2))/24

Pour le cas N=100, ça nous fait 4423434

scarta · #11

Suite (approfondissement) :

En fonction de la valeur de N modulo 6 on a 6 cas différents, dont les résultats sont au final
N=6q
54q^4+54q^3+24q^2+6q+1
N=6q+1
54q^4+90q^3+60q^2+18q+2
N=6q+2
54q^4+126q^3+114q^2+48q+8
N=6q+3
54q^4+162q^3+186q^2+96q+19
N=6q+4
54q^4+198q^3+276q^2+174q+42
N=6q+5
54q^4+234q^3+384q^2+282q+78

Avec en prime une petite liste pour toutes les valeurs de N entre 0 et 100 :

Code:

N    Combinaisons
0    1
1    2
2    8
3    19
4    42
5    78
6    139
7    224
8    350
9    517
10    744
11    1032
12    1405
13    1862
14    2432
15    3115
16    3942
17    4914
18    6067
19    7400
20    8954
21    10729
22    12768
23    15072
24    17689
25    20618
26    23912
27    27571
28    31650
29    36150
30    41131
31    46592
32    52598
33    59149
34    66312
35    74088
36    82549
37    91694
38    101600
39    112267
40    123774
41    136122
42    149395
43    163592
44    178802
45    195025
46    212352
47    230784
48    250417
49    271250
50    293384
51    316819
52    341658
53    367902
54    395659
55    424928
56    455822
57    488341
58    522600
59    558600
60    596461
61    636182
62    677888
63    721579
64    767382
65    815298
66    865459
67    917864
68    972650
69    1029817
70    1089504
71    1151712
72    1216585
73    1284122
74    1354472
75    1427635
76    1503762
77    1582854
78    1665067
79    1750400
80    1839014
81    1930909
82    2026248
83    2125032
84    2227429
85    2333438
86    2443232
87    2556811
88    2674350
89    2795850
90    2921491
91    3051272
92    3185378
93    3323809
94    3466752
95    3614208
96    3766369
97    3923234
98    4085000
99    4251667
100    4423434

titoufred · #12

Oui, bravo scarta !

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 15-03-2014 17:50:30

couper un gofol en 3 !

#0 Pub

#2 - 15-03-2014 19:04:10

Couper un ggool en 3 !

#3 - 16-03-2014 11:21:26

Couper un goglo en 3 !

#4 - 16-03-2014 13:31:39

Cuper un gogol en 3 !

#5 - 16-03-2014 14:34:53

Couepr un gogol en 3 !

#6 - 16-03-2014 16:36:18

Couper un gogol en 33 !

#7 - 16-03-2014 21:17:58

Coper un gogol en 3 !

#8 - 16-03-2014 21:40:05

Couper un goglo en 3 !

#9 - 17-03-2014 15:51:10

Couperr un gogol en 3 !

#10 - 17-03-2014 18:00:14

Couuper un gogol en 3 !

#11 - 18-03-2014 11:07:45

Cuper un gogol en 3 !

Code:

#12 - 18-03-2014 13:59:24

Couper un goglo en 3 !

Réponse rapide

Sujets similaires

Pied de page des forums