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 - 04-05-2016 08:14:38

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

superpodition de nombres binaires

Bonjour à tous,

Dans le prolongement du sujet "nombres premiers d'addition" voici une autre énigme beaucoup plus complexe:

Dans un segment de n bits, combien peut-on compter au maximum de codes différents tels que la superposition de 2 quelconques d'entre eux donne à chaque fois un code différent ? Par superposition, il faut comprendre qu'à un rang donné, il y a 1 si au moins un des deux codes est à 1, et 0 si les 2 codes sont à 0.

Vous allez vous rendre compte rapidement qu'il n'est pas efficace de travailler dans l'ordre croissant des codes. Et que donc, l'usage d'un programme doit être précédé d'une réflexion poussée.

Le sujet étant très ouvert, je ne donne pas de temps. Chacun peut élaborer sa propre méthode et la présenter ici. Cette question fait l'objet déja d'un sujet sur un site voisin depuis un certain temps. Rien de probant n'en est sorti sur la preuve d'un maximum...



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 04-05-2016 10:34:48

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

superposition dr nombres binaires

Bonjour,
Avec n bits, on est sûr de pouvoir coder n+1 nombres différents qui répondent à la question : 0, et n nombres dont 1 seul bit vaut 1.

Une expérimentation informatique montre que pour obtenir m nombres différents, il faut au moins m-1 bits (pour 2 ≤ m ≤ 7).

Code:

   1 solution  pour 2 ≤ m ≤ 5
  13 solutions pour m=6 (2.5 secondes de calcul)
2533 solutions pour m=7 (32 minutes de calcul)

 #3 - 04-05-2016 11:13:02

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

Superpositino de nombres binaires

Enigmatus, c'est une première réponse à minima. Mais je n'aurais pas proposé cette question si la réponse était réduite à m+1 codes différents sur m bits.

On peut faire mieux.

Exemple:

Je code sur m bits:
-tous les codes à 2 bits à 1 décalés de 2 unités (..101...)
-tous les codes à 2 bits à 1 décalés de 3 unités (...1001..)
-tous les codes à 2 bits à 1 décalés de 7 unités (..10000001...)
De plus, je dispose les m bits sur un cercle, de sorte que je peux mettre m codes pour chaque catégorie.

Normalement la superposition permet de tjs distinguer les 2 codes.

Pour m=20  (il faut un minimum de bits) par exemple , je peux faire 60 codes différents.

 #4 - 04-05-2016 11:48:36

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

superposition de nombrrs binaires

Ah ok, je comprends mieux que dans le thread précédent.
Faut que je creuse un peu plus, mais je dirais: "assez peu".
Sur n bits, prenons le nombre de notre liste qui comporte le plus de 1 (un nombre x, et donc par conséquent y=n-x zéros).
Le résultat d'un OR avec un autre nombre ne se jouera que sur les zéros (tous les bits à 1 resteront à 1 quel que soit l'autre nombre), donc au plus 2^y autres éléments dans la liste.
Conclusion : si x est grand, 2^y est petit; et si x est petit, alors tous les autres nombres ont au plus x bits à 1, soit 2^x autres valeurs possibles avec x petit

 #5 - 04-05-2016 12:37:01

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

superposition de nomnres binaires

Et du coup, en reprenant l'exemple que tu donnes, il y a un lien clair entre les nombres 2, 3, 7 etc... et le problème précédent.
4=2+2, 5=2+3, 6=3+3 ne sont pas retenus. 7, oui.
8+2 = 7+3, 9 = 7+2, 10=7+3, 11+3=7+7, 12+2 = 7+7
(Explication pour 8, 11 et 12, avec comme exemple 11: 100010010001 est à la fois la superposition d'un bloc "décalage 11" et d'un bloc "décalage 3" par dessus, ou 2 blocs "décalage 7" qui se chevauchent)
J'imagine que le suivant sera donc un bloc "décalage 13", puis 21, 30, 45, 61, 81, 107, 136

 #6 - 04-05-2016 12:57:01

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

superposition de nombred binaires

Et pour finir enfin, je peux affirmer que 108 bits suffisent pour répondre à ta question du thread précédent (combien de bits faut-il pour avoir un ensemble de 1000 éléments tels que le OR de deux d'entre eux est toujours distinct).
Avec cette méthode (!!!) 107 bits ne suffisent pas, l'ensemble obtenu sera de 964 éléments, avec 108 bits on passe directement à 1081.

Par contre, rien ne prouve qu'avec une autre méthode on ne puisse pas obtenir des résultats plus petits

 #7 - 04-05-2016 12:59:44

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

Superposition de nombrse binaires

Bien vu, Scarta, je n'avais pas vraiment fait le rapprochement de cette façon avec le message précédent. Cependant, il faut bien avoir en tête que l'exemple que j'ai présenté reste un exemple, et il faut bien admettre que le nombre de codes reste bien faible par rapport aux possibilités offertes. Il y a une infinité de manières d'aborder ce problème, alors il faut les inventer.
J'ai pour ma part une autre idée de codage totalement différente, et qui semble être bien plus efficace, mais elle est encore à vérifier.

 #8 - 04-05-2016 14:42:21

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

SSuperposition de nombres binaires

Si j'ai bien compris ce que tu proposes en #3, ça ne me semble pas coller. Voici deux couples d'éléments ayant des sommes identiques :

Code:

000101
101000
------
101101

001001
100100
------
101101

 #9 - 04-05-2016 16:10:32

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

quperposition de nombres binaires

Damned, il a raison sad
En fait ça ne marche jamais, c'est pas les blocs avec des décalages de 2 ou de 3 qui coincent. Pour deux décalages distincts m et n, m<n, si j'écris 1+(m-1)0+1+(n-m-1)0+1+(m-1)0+1, alors j'ai deux manière d'obtenir ce résultat : via deux blocs de taille (m+1), qui sont lu tels quels, et deux blocs de taille (n+1) qui se chevauchent.

J'avais pris ton affirmation pour argent comptant et j'étais parti sur une analyse de la suite. Du coup, tout le reste du raisonnement est faux.

 #10 - 04-05-2016 17:28:36

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

Superposition de nommbres binaires

Bien vu Enigmatus.
De toute façon, cette piste, comme je le disais, ne menait vraiment pas loin, question performance.
Il faut inventer autre chose....

 #11 - 05-05-2016 08:38:49

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

superoosition de nombres binaires

Bon, j'expose ici mon idée, j'espère qu'elle peut être mise dans un programme facilement....

Je réserve un certain nombre de bits à une opération de codage, comme on fait en transmission pour sécuriser les messages. Le reste des bits est rempli par le nombre proprement dit écrit en binaire.

Codage:
On associe à un nombre donné sa valeur modulo un ou plusieurs nombres impairs (j'avais pensé modulo un nombre premier autre que 2, mais impair devrait convenir).
On réserve pour ce reste autant de bits que de restes possibles:
3 bits pour modulo 3 (0,1,2)
5 bits pour modulo 5 (0,1,2,3,4)
k bits pour modulo k. (0,1,2,..k-1)

Un bit est à 1 pour la valeur modulo le nombre.

Plus on choisit de nb modulo, plus on va occuper des bits. Si on veut utiliser 3 et 5, il faut 8 bits. Si on veut utiliser 3,5 et 7, il faut 15 bits. etc...

Le nombre de modulos à utiliser est donc en rapport avec l'efficacité qu'on peut en tirer. Plus on veut obtenir de nombres, plus on aura besoin de modulos.
Pour l'instant, je n'ai pas d'idée sur la performance à attendre, seuls des essais pourront le dire.

Pour attteindre 1000 nombres par exemple, je vois ça comme ça:
bits 1 à 3 pour le reste modulo 3
bits 4 à 8 pour le reste modulo 5
bits 9 à 15 pour le reste modulo 7
bits 16 à 24 pour le reste modulo 9

Compte tenu des déchets inévitables à attendre, je vois environ 15 bits nécessaires pour obtenir les 1000 chiffres.

Quelqu'un pour se pencher sur le programme qui en découle ?

Il n'est pas facile, puisqu'il faut déja inventer l'opération de superposition, faire des opérations en binaire, etc....

En revanche, on peut le faire tourner en prenant les entiers dans l'ordre, comme dans le problème précédent.

J'espère que c'est assez clair.

 #12 - 05-05-2016 10:26:46

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Supperposition de nombres binaires

@nodgim #11 :
Ce n'est pas clair pour moi. Peux-tu donner un exemple précis avec un petit nombre de bits ?

Ajouté :
Avec 1000 nombres, on doit avoir suffisamment de bits pour représenter 1000*999/2=499500 sommes différentes. Il faut donc au moins 19 bits (2^18=262144, 2^19=524288).

 #13 - 05-05-2016 12:18:22

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

Superposition de nombrse binaires

Avec la configuration de codage 3,5,7,9, le nombre 758 par exemple va s'écrire ainsi:
001 car son reste modulo 3 vaut 2.
00010 car son reste modulo 5 vaut 3
00100000 car son reste modulo 7 vaut 2
001000000 car son reste modulo 9 vaut 2
1011110110 pour 758 écrit en binaire.

Le code complet de 758 est donc :
001.00010.0010000.001000000.1011110110

il n'est pas certain qu'il faille 19 chiffres binaires, car il faut tenir compte des bits de codage.

 #14 - 05-05-2016 13:40:11

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Superposition de onmbres binaires

@nodgim #13 :
Il y a une erreur dans le reste de la division par 5.

Si tu me fournis 1000 nombres codés ainsi, je peux faire les tests.

En codant les entiers 0 à 999 avec ta méthode, on obtient des sommes identiques :

Code:

  0100100001000000100000000000000001 1
  1001000010000001000000001001110110 630
  ----------------------------------
  1001000010000001000000000000000000 0
  0100100001000000100000001001110111 631
  ----------------------------------
s=1101100011000001100000001001110111

Code:

  1000001000010000001000000000000011 3
  0100100001000000100000000100111100 316
  ----------------------------------
  0100100001000000100000000000000001 1
  1000001000010000001000000100111110 318
  ----------------------------------
s=1100101001010000101000000100111111

 #15 - 05-05-2016 18:33:07

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

Superposition de nombres ibnaires

Qu'il y ait des sommes identiques, c'est normal, on ne peut pas l'éviter. Ce qui est important, c'est de connaitre le taux de déchet. J'imagine bien que ce taux augmente avec le nombre de 1 dans le nombre binaire.
As tu déja mis au point un algo ?
De plus, il faut faire tourner la routine sur plus que 999 si on veut espérer obtenir 1000 gagnants.

 #16 - 05-05-2016 19:43:09

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

superpoqition de nombres binaires

Pour ce que j'ai fait en #14 en utilisant ton codage, il y a environ 67% de sommes uniques (336363/499500).

 #17 - 05-05-2016 20:12:46

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

Superposition de nommbres binaires

67% des nombres compris entre 0 et 999, ça fait dans les 670 nombres corrects ?
Si c'est bien ça, je prends tout de suite !

Est ce que ça a pris beaucoup de temps ?

Est ce que tu peux prolonger jusqu'à obtenir les 1000 nombres corrects ?

Normalement, c'est quand il y a beaucoup de 1 dans le nombre binaire qu'on a le plus de chance d'échec. J'avais idée au départ de procéder en prenant tous les nombres à 1 seul bit à 1, puis tous les nombres à 2 bits à 1, puis tous les nombres à 3 bits à 1, etc....Mais, au dela de la complexité supplémentaire, on est obligé au départ de fixer un nombre de bits donné. On arrive sans doute plus vite au résultat, mais il faut faire plusieurs essais. Aussi, je m'en suis tenu au test des nombres dans l'ordre naturel. ça permet d'avoir une vision sur l'efficacité de la méthode. Pour l'instant, j'en suis agréablement surpris.
Et merci pour ton travail !

 #18 - 05-05-2016 21:05:02

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Superposition dee nombres binaires

Il s'agit de 67% des sommes, et pas des nombres. Si on prend les 336363 couples qui ont donné une somme unique, les 1000 nombres y sont représentés (entre 51 et 846 fois).

 #19 - 06-05-2016 07:47:28

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

Superposition de nobres binaires

Ah d'accord, ça me semblait trop beau.

 #20 - 07-05-2016 19:15:48

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Superposition de nombres binaaires

Je n'y croyais pas, mais j'ai trouvé 120 solutions pour coder 8 nombres sur 6 bits, et respectant la contrainte bien sûr.
En voici une :

Code:

         0 000000  
         3 000011  
        12 001100  
        21 010101  
        26 011010  
        38 100110  
        41 101001  
        48 110000

Je vais essayer de voir si on peut faire mieux avec 6 bits.

Édité : Sauf erreur, on ne peut pas trouver 9 nombres codés sur 6 bits.

 #21 - 08-05-2016 00:34:40

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

Superposition de nombes binaires

J'ai trouvé pareil, et ça a confirmé quelques résultats intéressants:
- pour toute permutation des n bits, on trouvera un autre ensemble - facile à démontrer
- le premier ensemble optimal (> n+1 éléments) ne peut pas contenir 0 et une puissance de 2 : d'après le point précédent, c'est équivalent à contenir 0 et 1, tout nombre impair donnera le même résultat avec 0 ou 1, donc tous les autres sont pairs et par conséquent il y a autant d'éléments que dans un ensemble pour n'=n-1, avec un zéro pour dernier bit, plus le nombre 1

Le fait qu'il y ait 120 ensembles est intéressant, il faudrait les normaliser pour voir de combien de permutations initiales ils sont issus.

 #22 - 08-05-2016 08:23:07

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

superposition de nombres bibaires

scarta #21 a écrit:

Le fait qu'il y ait 120 ensembles est intéressant, il faudrait les normaliser pour voir de combien de permutations initiales ils sont issus.

Ce sera à vérifier, mais pour 8 nombres codés sur 6 bits, je trouve 30 solutions correspondant aux permutations sur les bits de ces nombres

Code:

(0, 3, 12, 21, 26, 38, 41, 48)

et 90 correspondant à

Code:

(1, 2, 12, 21, 26, 38, 41, 48)

Ajouté :
Et voici comment sont réparties les 2533 solutions correspondant à 7 nombres codés sur 6 bits :

Code:

(0, 1, 2, 4, 8, 16, 32)       1
(0, 1, 6, 10, 20, 40, 48)    72
(0, 3, 12, 21, 26, 38, 41)   90
(0, 3, 12, 21, 26, 38, 48)  120
(0, 3, 5, 10, 20, 40, 48)    60
(0, 3, 5, 10, 20, 44, 50)   360
(0, 3, 5, 9, 18, 36, 48)    360
(0, 3, 5, 9, 18, 36, 56)    360
(1, 2, 12, 21, 26, 38, 41)  180
(1, 2, 12, 21, 26, 38, 48)  360
(1, 6, 10, 19, 36, 41, 48)  360
(1, 6, 11, 21, 24, 44, 50)  180
(3, 12, 21, 26, 38, 41, 48)  30

 #23 - 08-05-2016 09:39:44

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

superposition de nombres binaures

J'ai une solution, inspirée des modulos, mais plus simple, et pour celle ci je prouve que ça marche :
Pour un segment de 2n bits, on réserve les bits numérotés 1 à n au codage (c'est la zone codage )  les n autres bits, également numérotés de 1 à n, sont utilisés pour le nombre binaire.
Les nombres binaires se limitent à 2 bits à 1. On peut TOUS les utiliser. Le codage consiste à faire la somme modulo n des 2 bits de chaque nombre binaire.

Exemple :
Le nombre binaire est représenté par un bit au rang 2 et un bit au rang 4 : codage : 2+4=6, donc un bit à 1 au rang 6 de la zone codage.

Preuve:
On prouve que la superposition est toujours décomposable.
Une superposition, c'est 3 bits à 1 ou 4 bits à 1 :

si 3 bits à 1 aux rangs a < b < c.
Les sommes a+b, a+c et b+c sont distinctes
Preuve
on suppose a+b=x et b+c=x+n la différence vaut c-a=n impossible.
Le codage fait donc distinguer les 2 nombres.


Si 4 bits à 1 aux rangs a < b < c < d
Les égalités possibles sont :
a+b=c+d [n] ou a+d=b+c  mais pas en même temps. S'il existe une des égalités, alors un seul bit à 1 dans la zone codage, qui correspond à a+b ou a+d.
Si pas d'égalité, on cherche la somme qui convient avec a + (b ou c ou d).


Performance:
Dans 2n bits, on peut placer n(n-1)/2 nombres.

NB: on peut adjoindre les nombres à 1 bit, sauf 1, ce qui augmente légèrement la performance.

 #24 - 08-05-2016 10:06:17

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Superposition de nombres biniares

nodgim #23 a écrit:

Dans 2n bits, on peut placer n(n+1)/2 nombres.

Je ne comprends pas. Si les nombres binaires ont n bits, et sont constitués de 2 bits à 1, tu en auras seulement n(n-1)/2.
Peux-tu donner une liste complète de nombres codés avec ta méthode, pour une petite valeur de n.

 #25 - 08-05-2016 10:46:39

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

Superposition de nombrees binaires

Oui, Enigmatus, erreur en rédigeant. correction faite.

Voici ce que ça donne avec n=5, le 1er nombre est le nombre binaire défini par le rang de ses 2 bits, le second est le code défini par le rang de la somme des 2 rangs du nombre, modulo 5:

12-3
13-4: somme 123-34
14-5: sommes 124-35; 134-45
15-1: sommes 125-13; 135-14; 145-15
23-5: sommes 123-35; 123-45; 1234-5; 1235-15
24-1: sommes 124-13; 1234-14; 124-15; 1245-1; 234-15
25-2: sommes 125-23; 1235-24; 1245-25; 125-12; 235-25; 245-12
34-2: sommes 1234-23; 134-24; 134-25; 1345-12; 234-25; 234-12; 2345-2
35-3: sommes 1235-3; 135-34; 1345-35; 135-13; 235-35; 2345-13; 235-23; 345-23
45-4: sommes 1245-34; 1345-4; 145-45; 145-14; 2345-45; 245-14; 245-24; 345-24; 345-34

Voila.
Mais cet exemple ne prouve pas que ça marche en généralisant. Il faut prouver que pour une superposition, on arrive à retrouver les 2 nombres grace au codage. Ce que je crois avoir fait.

On arrive ici à 10 nombres avec 10 bits, mais bien sûr le score s'améliore avec le nombre de bits.
Pour 92 bits: 1035 nombres.

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

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