Enigme Partition par exponentiation @ Prise2Tete

nodgim · #1

Bonjour à tous.

Combien de nombres doit on utiliser au minimum pour obtenir 2020 et 1 milliard par sommation ? On peut se servir de nombres intermédiaires, mais ceux-ci devront être élaborés à partir de 1 ou d'autres nombres intermédiaires.

Exemple :

10 = 5 + 5 ( donc 2 nombres )
5 = 3 + 2 ( + 2 nombres, soit 4 )
3 = 2 + 1 ( + 2 nombres, soit 6)
2 = 1 + 1 ( + 2 nombres, soit 8 )

En cherchant un peu, on se rend compte qu'on fait légèrement mieux :

10 = 4 + 4 + 2 ( 3 )
4 = 2 + 2 ( 3 + 2 = 5)
2 = 1 + 1 ( 5 + 2 = 7 )

P(10) = 7.

Bonne recherche

Ebichu · #2

Salut nodgim,

j'obtiens 23 pour 2020 :

1+1+1=3
3+3+3=9
9+9+9+1=28
28+28=56
56+56+56=168
168+168+168+1=505
505+505+505+505=2020

Tu as mieux ?

nodgim · #3

Bravo Ebichu !

Je doute qu'il y ait mieux....

Et pour 1 milliard ?

Sinon, as-tu des idées pour la stratégie ?

Ebichu · #4

Pour 1 milliard, je n'ai pas encore eu le temps de chercher, je te tiens au courant.

Pour la stratégie, globalement, on remarque que le plus efficace pour augmenter rapidement est de faire a+a+a.
a+a et a+a+a+a sont à égalité ensuite.
puis a+a+a+a+a est un peu plus lent, etc.

Quand on vise un certain nombre, j'essaie de m'en approcher le plus possible, mais sans le dépasser, avec le maximum d'opérations x3, puis avec des opérations x2 ou x4, voire x5. Et lorsque je suis assez proche du nombre, j'essaie de corriger en insérant des nombres supplémentaires dans certaines opérations.

Par exemple, pour 2020, j'ai d'abord remarqué que :
3*3*3*3*3*2*2*2=1944
Il manque 76 = 72 + 4, j'ai donc inséré un 1 qui s'est fait multiplier par 4 et un autre 1 par 72 dans mes opérations (c'est une méthode que j'utilise souvent quand je joue à "des chiffres et des lettres", c'est assez efficace )
((3*3*3+1)*3*3*2+1)*2*2=2020

Mais je ne sais pas trop comment faire pour obtenir une démonstration rigoureuse du fait qu'on ne puisse faire mieux que 23.

godisdead · #5

1 + 1 = 2
2 + 2 = 4
4 + 4 = 8
8 + 8 = 16
16 + 16 = 32
32 + 32 = 64
64 + 64 = 128
128 + 128 = 256
256 + 128 + 64 + 32 + 16 + 8 + 1 = 505
505 + 505 = 1010
1010 + 1010 = 2020

27 nombres.

Si je fais du binaire pur :
1 + 1 = 2
2 + 2 = 4
4 + 4 = 8
8 + 8 = 16
16 + 16 = 32
32 + 32 = 64
64 + 64 = 128
128 + 128 = 256
256 + 256 = 512
512 + 512 = 1024
1024 + 512+256+128+64+32+4 = 2020

27 également !
Zut, je pensais que ce serait plus long !

Par contre !
1 + 1 = 2
2 + 1 = 3
3 + 3 = 6
6 + 6 = 12
12 + 12 = 24
24 + 24 = 48
48 + 48 = 96
96 + 96 = 192
192 + 192 = 384
384 + 384 = 768
768 + 768 + 384 + 96 + 2 + 2 = 2020

26 nombres

Allez, je tente un dernier pour la route
1 + 1 = 2
2 + 2 + 1 = 5
5 + 5 = 10
10 + 10 = 20
20 + 20 = 40
40 + 40 = 80
80 + 80 = 160
160 + 160 = 320
320 + 320 = 640
640 + 640 + 640 + 80 + 20 = 2020
24 nombres !

Encore un dernier

Allez, je tente un dernier pour la route
1 + 1 = 2
2 + 2 + 1 = 5
5 + 5 = 10
10 + 10 = 20
20 + 20 = 40
40 + 40 + 40 + 5 = 125
125 + 125 = 250
250 + 250 = 500
500 + 500 = 1000
1000 + 1000 + 20 = 2020
24 nombres !

Franky1103 · #6

Mon idée est d’écrire le nombre final sous la forme d’une somme de puissances de 2.
Puis P(N) = 2 x (plus grande puissance de 2) + (nombre de termes de l’addition finale)
2020 = 2^2 + 2^5 +2^6 +2^7 +2^8 +2^9 +2^10
=> P(2020) = 2 x 10 + 7 = 27
10^9 = 2^9 + 2^11 +2^14 +2^15 +2^17 +2^19 +2^20 +2^23 + 2^24 +2^25 +2^27 + 2^28 +2^29
=> P(10^9) = 2 x 29 + 13 = 71
Mais je ne suis pas persuadé qu’on obtient ainsi la meilleure solution.

nodgim · #7

@ Godisdead : Il y a chouïa mieux.

@ Francky: oui, en effet, il y a mieux.

@ Ebichu : rassure-toi, je n'ai pas de recette miracle.

Ebichu · #8

J'arrive à 65 pour 1 milliard. Et toi ?

nodgim · #9

Sauf erreur, j'en ai 1 de mieux.

Ebichu · #10

Grrr

Il faut dire que je n'ai pas trop forcé : j'écris 1 milliard en base 3 (2120200200021010001), je calcule les puissances de 3 jusqu'à 3^18 (coût=54), puis je calcule x=3^7+3^11+3^14+3^16+3^18 (coût=5), et enfin x+x+1+3^4+3^6+3^17 (coût=6).

Mais peut-être que si je m'y prends mieux, je peux réduire le coût. Il me reste un petit peu de temps pour essayer.

Ebichu · #11

OK, en arrangeant un peu l'ordre des opérations, on peut faire un coût de 64.

En comptant en base 3, et en mettant le coût entre parenthèses, je construis dans l'ordre les nombres suivants :
10, 100, 1000, 10001 (13)
21202 (5)
21202000000 (18)
212020020002 (5)
2120200200021 (4)
212020020002100000 (15)
2120200200021010001 (4)

L'astuce est de tirer parti de 10001 qui apparaît à plusieurs endroits.

nodgim · #12

Excellent !

nodgim · #13

Je donne mes solutions.

@ Ebichu : curieusement, tu as eu 23 pour 2020 en faisant un mixte base 2 / base 3 alors que j'ai le même résultat en base 3. Pour 1 milliard ,c'est le contraire : tu as 64 en travaillant base 3, j'ai le même résultat en faisant un mixte base 2/ base 3.

Le plus faible rapport n / ln n est obtenu pour n = 3, en 2ème vient n = 2. Il est donc assez naturel de représenter un nombre à traiter en base 3.

2020 en base 3 = 2201122.

Brut, on compte le nombre de partitions ainsi :
3 * ( nb de chiffres -1) + chiffres non nuls ( sauf le 1er) + 2 ( car 2 = 1 + 1 )

p (2020) = 3*6 + 5 + 2 = 25.

On peut améliorer en observant les répétitions éventuelles à partir de la gauche :
existe t’il un 22, ou 2201, ou 22011 , ….dans le nombre ?

Oui : 22 à droite.

Et même 11, moitié de 22.

Ainsi la partition donnera :
2201122 = 3 * 220110 + 22
220110 = 3 * 22011
22011 = 3 * 2200 + 11
2200 = 3 * 220
220 = 3 * 22
22 = 2 * 11
11 = 2 + 2
2 = 1 + 1

Total : 5 * 3 + 8 = 23.

Cependant, la division par 2 peut être meilleure si le nombre est pair.
2 n / ln2 < (3n+1) / ln 3 pour n < 5.

1 000 000 000 = 2 *
5 000 000 00 = 2 *
25 000 000 0 = 2 *
125 000 000 = 2 *
625 000 00 = 2 *
3125 000 0 = 2 *
15625 000 = 2 *
7812500 = 2 * 3906250

3906250 en base 3 = 21100110100221

Une seule répétition : 21

P (3906250)= 3*13 + 7 + 2 = 48

P ( 10 ^ 9 ) = 16 + 48 = 64.

nodgim · #14

Pour 1 milliard, j'avais oublié ma propre réponse initiale, dont le résultat est en fait........63.

Et c'est la façon la plus directe de procéder :

10 ^9 = 2^9 * 5^9.

Pour les puissances de 2 : 9 fois 2 nombres = 18
Pour les puissances de 5 : 9 fois 5 nombres = 45

TOTAL = 63.

Étonnant, non ?

Ebichu · #15

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 - 30-01-2020 11:36:11

Partition par exopnentiation

#0 Pub

#2 - 02-02-2020 16:01:45

Parttion par exponentiation

#3 - 02-02-2020 18:20:10

Partitino par exponentiation

#4 - 02-02-2020 19:55:31

partition par ecponentiation

#5 - 02-02-2020 23:21:21

partition par expinentiation

#6 - 03-02-2020 08:50:11

Partiition par exponentiation

#7 - 03-02-2020 10:37:45

partirion par exponentiation

#8 - 04-02-2020 23:01:15

Partition par exponentiaiton

#9 - 05-02-2020 08:19:48

Partition par exponentiatoin

#10 - 05-02-2020 10:05:10

Partition par exponentiiation

#11 - 05-02-2020 10:36:37

Partittion par exponentiation

#12 - 05-02-2020 11:51:07

partitiob par exponentiation

#13 - 05-02-2020 17:21:08

Partition par epxonentiation

#14 - 06-02-2020 17:33:31

partitiin par exponentiation

#15 - 06-02-2020 19:16:27

partition par exponentiatuon

Réponse rapide

Sujets similaires

Pied de page des forums