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 - 09-02-2014 20:47:50

NickoGecko
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1819

Parité binire

Bonjour !

Je me demande, sans avoir la réponse, si une loi régit la suite de nombres décimaux dont la forme binaire codée sur "n bits" (n pair) comporte autant de 1 que de 0 ?

Exemple sur 4 bits

0011 > 3
0101 > 5
0110 > 6
1001 > 9
1010 > 10
1100 > 12


(sur excel, fonction DECBIN (nombre décimal; nb de bits)

Question ouverte !
A+smile


Il aurait pu pleuvoir, con comme il est ! (Coluche)
  • |
  • Répondre

#0 Pub

 #2 - 09-02-2014 21:33:00

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Parié binaire

Déjà, si l'entier naturel a satisfait ta condition pour 2n bits, alors (4^n - 1 - a) aussi (interversion des 1 et des 0 dans l'écriture du nombre).
Ce qui signifie que ta liste présente une symétrie centrée entre 2^(2n-1)-1 et 2^(2n-1) sur l'intervalle [0;4^n-1].


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #3 - 10-02-2014 19:03:35

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

parité binaite

Je peux affirmer sans peur de faire fausse route qu'il y en a autant de pairs que d'impairs, et qu'il est facile de calculer leur somme en fonction de n, mais à part ça, je sèche smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #4 - 10-02-2014 20:35:43

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

Parité binare

Le nombre de termes de cette suite est de: N = n! / (n/2)!²: ce sont aussi les termes apparaissant sur l’axe de symétrie du triangle de Pascal.

Le i-ème terme semble être de la forme:
2^(n/2 + 1) - 2^(n/2 - i + 1) - 1, pour 1 =< i =< N/2
2^n - 2^(n/2 + 1) + 2^(n/2 - N + i), pour N/2 + 1 =< i =< N
expressions qui ne semblent pas simplifiables.

Edit: Mes formules sont archi-fausses, mais je continue, comme vous, de chercher.

 #5 - 12-02-2014 22:28:39

NickoGecko
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1819

Parié binaire

Merci pour vos idées !

Je laisse la question ouverte !
Bonne semaine !

smile


Il aurait pu pleuvoir, con comme il est ! (Coluche)

 #6 - 15-02-2014 17:32:26

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

paroté binaire

On peut aussi s'interroger sur le rang de ces nombres si on les classe dans l'ordre croissant.
Quel est le millionième nombre ?

 #7 - 15-02-2014 21:32:10

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Parité ibnaire

On va pouvoir créer une relation d'ordre big_smile

Le millionième terme, intéressante question déjà j'ai bien du mal à calculer [latex]\sum_{k=1}^{n} \binom{2k}{k}[/latex]... hmm


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #8 - 16-02-2014 08:55:25

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

Parité binaiire

ça se fait à la main, pourtant. Calculette admise.

 #9 - 16-02-2014 14:10:54

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Parité binairee

Et bien donne moi le résultat...
[TeX]\sum_{k=1}^{n} \binom{2k}{k} = \sum_{k=1}^{n} \frac{(2k)!}{(k!)^2}[/TeX]
Et après...


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #10 - 16-02-2014 19:18:06

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

parité bibaire

C'est bien shadock, mais je n'ai pas cherché à calculer cette sommation. D'ailleurs, c'est plutôt (2n-1,n-1) pour moi, et non (2n,n).

Mais le plus interessant vient après...

 #11 - 16-02-2014 19:59:44

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

paroté binaire

On ne veut que les termes pairs, (2n,n) est bien adapté smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #12 - 17-02-2014 08:55:19

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

Parité biniare

Non. Pour n=4 par exemple tu as seulement:
1001
1010
1100
le 1 de tête est obligatoire. C'est seulement l'autre 1 qui est distribuable dans les 3 emplacements disponibles.

OK ?

 #13 - 17-02-2014 13:51:14

NickoGecko
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1819

Parité binaie

Hello

En fait je considérais aussi 0011, 0101 et 0110 comme acceptable, dans l'exemple "4 bits".

Dans ce cas, il faut donner d'entrée de jeu le nombre de bits considérés, comme le fait la formule excel DECBIN.

smile


Il aurait pu pleuvoir, con comme il est ! (Coluche)

 #14 - 17-02-2014 18:18:24

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

oarité binaire

nogdim, je ne considère pas que 0011 et 1100 c'est la même chose, tout dépend du référentiel smile

Au pire on divise par 2 ma sommation smile

A la calculatrice on trouve 956384 termeS pour n=11 donc on est pas loin du millionième terme.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #15 - 17-02-2014 19:04:45

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

Parité binaie

Dans ce cas, je ne vois pas trop comment on peut remettre les nombres dans l'ordre, étant donné que des nombres à 12 chiffres peuvent être plus grands que des nombres à 22 chiffres....

 #16 - 19-02-2014 20:08:14

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Parté binaire

Donc si on considère qu'il y a 956384 termes pour n=11 alors le millionième terme se trouve dans le rang suivant c'est à dire pour n=12 le millionième terme sera donc le 43616e termes du rang n=12.


Soit un nombre [latex]A=\overline{a_n a_{n-1}\text{ ... }a_2 a_1}[/latex] et un nombre [latex]B=\overline{b_n b_{n-1}\text{ ... }b_2 b_1}[/latex] uniquement composés de 0 et de 1.
On dira que A est plus grand que B si [latex]\sum_{k=1}^{n} a_k 2^k > \sum_{k=1}^{n} b_k 2^k[/latex] autrement dit il suffit de comparer les nombres en base 10.
Par exemple 01000011 > 00111111 en effet 67 > 63

Le millionième terme est de la forme [latex]A=\overline{a_{24} a_{23}\text{ ... }a_2 a_1}[/latex] sachant que le terme le plus petit de cette liste est tel que
[TeX]\sum_{k=13}^{24} a_k=0[/TeX]
Reste à trouver mais je n'ai pas encore d'idée comment trouver ce fameux 1000000e terme !

De manière informatique de déplaçant 43616 fois un 1 en respectant la relation d'ordre dans l'ensemble des entiers naturels.

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #17 - 19-02-2014 20:12:00

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

Parité biinaire

En informatique, on peut prendre le code grey, alors il suffit d'en prendre un sur 2.
A partir de là, on a la liste complète puis il faudrait la remettre dans l'ordre pour trouver le millionième.

 #18 - 19-02-2014 22:24:42

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Parité binair

Moi j'ai du mal à mettre mes idées au clair mais je pense qu'on peut le trouver sans l'aide de l'informatique ! hmm


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #19 - 20-02-2014 19:11:54

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

oarité binaire

J'ai. Sans informatique mais avec un petit tableur.

 #20 - 21-02-2014 20:00:46

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Paritté binaire

On a au rang n bits (avec n pair) des combinaisons commencant par 00 , 01 , 10 et 11

Celles commençant par 00 ou 11 sont au nombre de C(n/2;n-2)
Celles commençant par 01 ou 10 sont au nombre de C(n/2-1;n-2)

On arrive vite en sommant tout ça à :
n=2 : 2
n=4 : 6
....
20
70
252
924
3432
12870
48620
184756
n=22 : 705432  total : 956384
n= 24 : 2704156  si on ne prend que celles commençant par 00 (646646) on dépasse


Le nombre est donc de la forme 00??????????????????????

Juste une dichotomie ensuite pour situer le premier 1 et atteindre les 43616 manquants.

0000 001?? ????? ????? ?????  C( 11;17)= 12376
0000 01??? ????? ????? ?????  C(11;18) = 31824
0000 1???? ????? ????? ?????  C(11;19) =  75582

Il commence donc par 0000 1

Et on recommence avec le second 1 ... pour atteindre 43616-31824 = 11792

0000 10010 ????? ????? ?????  C(10;16)= 8008
0000 101?? ????? ????? ?????  C10;17)= 19448

Et c'est reparti pour atteindre 3784

0000101001???

..... etc c'est fastidieux mais pas très long. Seulement je ne suis pas sûr de devoir m'arrêter sur un nombre ou le suivant à la fin.

 #21 - 22-02-2014 19:20:50

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

Parité binnaire

Reste plus qu'à mettre au point une méthode pratique pour trouver le millionième nombre à parité binaire.
Si j'avance 1 691 505, qui confirmera ou contestera ?

 #22 - 23-02-2014 01:05:29

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Parité binair

Je ne contesterai pas (bien que je n'ai pas essayé) en revanche j'aimerai connaitre le 1000! ième terme moi.. tongue

En gros quel est le n-ième terme de la suite voilà notre grande question big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #23 - 23-02-2014 09:43:39

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

Pairté binaire

Le 1000 ème nombre à parité binaire vaut 1579.
le 1000! ème je connais pas. Déja, pour écrire le nombre 1000! il faudra se lever de bonne heure.
Je peux cependant conjecture que ce nombre est proche de 2*1000! par défaut.

Il ne faut pas renoncer à vouloir trouver une formule toute faite qui te donnera f(n)=...mais ça me parait plutôt coriace.
Sinon, l'écart entre 2 nombres à parité binaire est toujours une puissance de 2.

 #24 - 23-02-2014 09:52:05

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Parité binair

Non, pas quand on passe de 0110 à 1001 par exemple puisque certains seront pairs et d'autres impairs.

De même pour passer de 28 à 35 :   011100 et 100011...etc

 #25 - 23-02-2014 10:58:31

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

Parité binaiire

Non Gwen.
011100=28
00011101=29
00011110=30
0000011111=31
100011=35

il n'y a pas de relation directe entre la valeur binaire du nombre et le nombre de bits dont il est composé.

L'exmple donné dans l'énoncé est trompeur, qui fait se suivre les nombres à 4 bits exclusivement.

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 : 

Si il y a 88 pommes et que vous en prenez 44, combien vous en avez ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

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