Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 24-11-2020 17:00:34

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombres quilibrés.

Bonjour @ tous.

Cette question là est bien adaptée pour ce site, je crois....

On dit d'un nombre n impair qu'il est équilibré si :

n = S+(n) + S-(n)

La fonction S+(n) est la somme des impairs obtenus par les divisions par 2 de n jusqu'à 1. S'il faut diviser par 2 un impair, on lui ajoute 1 au préalable.

La fonction S-(n) est la même, sauf que pour diviser un impair, on lui ôte un 1 au préalable.

Ainsi pour le nombre 11 :
S+(11) = 3 + 1 = 4
S-(11)= 5 + 1 = 6

n n'est pas équilibré puisque S+(11) + S-(11) = 10.

Pour 19:
S+(19) = 5 + 3 + 1 = 9
S-(19)= 9 + 1 = 10

19 est équilibré puisque 19 = S+(19) + S-(19)

Questions:

Quel est le 1er nombre équilibré supérieur à un million ?

Combien y a t'il de nombres équilibrés jusqu'à mille ?

  • |
  • Répondre

#0 Pub

 #2 - 02-12-2020 19:31:20

TOUFAU
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 104

Nombres équilirés.

Bonjour Nodgim, je découvre hier soir ton problème, en passant un peu par hasard je dois dire. J'ai failli être hors limite, mais vu l'enthousiasme général, pas si structurant...

Comme dab, pas trivial. On sent bien qu’il faut bosser en binaire, mais j’ai pataugé un peu pour trouver la solution. Bref.

n un nombre impair
Je note T(n) = S-(n) + S+(n)
On cherche les conditions pour que T(n) = n.

En représentation « binaire », n= αp*2^p + α(p-1)*2^(p-1)+…+ α1*2 + α0
Avec α0 = αp = 1 et αi = 0 ou 1 entre 1 et p-1.
Je note Fi la somme des facteurs αi entre 1 et i.

En comprenant la mécanique des S-(n) et S+(n) - à chaque division, un des deux est impair et ajoute sa contribution à T(n) - on peut montrer que
T(n) = Fp*2^(p+1) – 2*Fp - ∑(Fi*2^i).
Pas immédiat quand même.
On peut ensuite montrer que du coup T(n) = n + p -2*Fp -1.
Pas immédiat on plus.

Donc T(n) – n = p – 2*Fp -1.
Et finalement, T(n) = n si et seulement si p est impair et Fp=(p-1)/2.
Bref, si j’écarte le 1 de l’unité en binaire de n, il faut et suffit qu'exactement la moitié des autres digits vaille 1.

Le premier n supérieur à 1.000.000 : 1.000.007
Le nombre de n inférieurs à 1000 : 50

 #3 - 04-12-2020 08:27:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombres quilibrés.

@ Toufau :

"Bref, si j’écarte le 1 de l’unité en binaire de n, il faut et suffit qu'exactement la moitié des autres digits vaille 1"

C'est correct, mais es tu sûr que 1 000 007 est équilibré ?

 #4 - 04-12-2020 09:45:15

TOUFAU
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 104

Nombres équiilibrés.

précipitation en binaire.
correction du coup : 1.049.599
mieux comme ça...

 #5 - 05-12-2020 07:53:17

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombres équiilibrés.

C'est mieux comme ça en effet. Bravo !

As tu une justification propre pour cette règle ? Perso, il m'a fallu du temps pour la peaufiner.

 #6 - 05-12-2020 10:51:47

TOUFAU
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 104

nombrzs équilibrés.

Yes.
Mais pas simple à reporter sans Latex (∑ de ∑...)

D'abord je montre, par itérations de S-(n) et S+(n) que T(n)= ∑(∑α(j+i)*2^î)+∑((1-αj) avec j de 1 à p et i de 0 à p-j

Donc que T(n) = Fp*2^(p+1) – 2*Fp - ∑(Fi*2^i).

Puis par réarrangement que Fp*2^(p+1) - ∑(Fi*2^i) = p - 1 + ∑αi*2^i

Donc T(n) – n = p – 2*Fp -1, ce qui donne le résultat.

Calculs un peu complexes quand même...

 #7 - 05-12-2020 17:05:12

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Nombres qéuilibrés.

Perso, je l'ai fait en comparant avec la somme des nombres pairs et impairs obtenus par division par 2 jusqu'à 1. Cette somme est elle-même une question qui mérite une petite recherche.

Par exemple que vaut s(57) ? : 28 + 14 + 7 + 3 + 1 = 53

On montre que c'est n - nombre de "1" de l'écriture binaire.

On en déduit à partir de là S-(n) +  S+(n) par comparaison.

 #8 - 08-12-2020 00:01:55

TOUFAU
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 104

Nombres qéuilibrés.

Salut Nodgim,

pas sûr de comprendre précisément ta méthode.
j'ai pris quelques minutes pour écrire la mienne (Latex manuel), au plus court

joli problème en tout cas:)

http://www.prise2tete.fr/upload/TOUFAU-nbequilibres.jpg

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
09-10-2010 Enigmes Mathématiques
22-01-2009 Enigmes Mathématiques
P2T
Triangles par Anapurna
19-09-2009 Enigmes Mathématiques
P2T
Gâteau 109 par Vasimolo
25-10-2015 Enigmes Mathématiques
P2T
Des nombres 2 par gabrielduflot
17-11-2009 Enigmes Mathématiques
10-11-2010 Enigmes Mathématiques
P2T
14-10-2008 Enigmes Mathématiques
P2T
C'est l'heure 2 par scarta
27-04-2011 Enigmes Mathématiques
P2T
Soyez prudents ! par SaintPierre
04-03-2011 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete