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
[+]

 #26 - 08-05-2016 12:05:51

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

superposition de nombreq binaires

Autre résultat intéressant : p étant le plus grand cardinal d'un tel ensemble pour une taille n, il existe plusieurs ensembles de cardinal p.
S'il est unique, alors d'après les permutations il devrait y en avoir d'autres sauf si toutes ces permutations donnent le même ensemble. Donc on sait que si k est tel que l'ensemble contient un nombre avec k bits à 1, alors il contient tous les nombres à k bits=1.
S'il existe un tel k>1, alors l'ensemble n'est pas valide : on montre qu'il existe toujours 3 éléments qui donneront au moins 2 fois la même somme. Et si un tel k n'existe pas, alors p=n+1, et on peut facilement trouver deux solutions pour ce cardinal.

Je pense que le nombre de solutions est important pour trouver le résultat au rang n: ayant choisi le premier nombre on peut en déduire la forme des autres pour un rang n'<n

#0 Pub

 #27 - 08-05-2016 16:02:06

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

superposition dz nombres binaires

@nodgim #25 :
J'ai testé ta méthode pour n=46, et ça semble marcher. On ne peut pas adjoindre les nombres dont un seul bit vaut 1, car ça génère des sommes identiques.

 #28 - 09-05-2016 08:05:49

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

superposotion de nombres binaires

D'accord merci, Enigamatus.
92 reste tout de même élevé. Je crois savoir qu'un algo qui fournit des nombres au hasard permet d'arriver à 1000 nombres avec 54 bits après un certain nombre d'essais. Sans qu'on sache si on peut descendre plus bas.

 #29 - 09-05-2016 17:36:51

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

duperposition de nombres binaires

Bon, je crois que ça marche aussi pour des triplets, mais il faut que la zone de codage soit 2 fois plus importante que la zone des nombres.

Zone de codage: 2n bits de rang 1 à 2n.

Zone des nombres: n bits de rang 1 à n.

la somme de 2 bits à 1 (somme des rangs) est donc inférieure à 2n.

Codage: pour chaque nombre, qui ont tous 3 bits à 1, on additionne les rangs de 2 bits voisins: le 1er avec le second, puis le second avec le 3ème.

Exemple:
nombre avec 1 bit à 1 aux rangs 2, 5 et 8 : codage : 7 et 13. Dans la zone codage, il y aura 1 bit à 1 aux rangs 7 et 13.

La vérification se fait en tentant de distinguer les 2 nombres dans la superposition, grace au codage. La partie la plus délicate est lorsque il y a 1 bit en commun. Toutes les configurations possibles ont été analysées.

Donc avec 3n bits, on peut obtenir n(n-1)(n-2)/6 nombres.

Avec 60 bits, on doit pouvoir obtenir 1140 nombres.

Enigmatus, pourras tu vérifier avec un programme ? Je ne suis pas à l'abri d'un oubli dans mon analyse....et si ça marche, je pousserais mon analyse avec des quadruplets.

 #30 - 09-05-2016 20:46:10

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

superposition de nolbres binaires

nodgim #29 a écrit:

Enigmatus, pourras tu vérifier avec un programme ?

En fait, tu n'utiliseras que 3*n-3 bits au total (les sommes sont comprises entre 3 et 2*n-1). Ici, 57 bits pout n=20.
On peut aussi ajouter le nombre 0.

Sauf erreur, bien sûr, j'obtiens 15504 paires de couples ayant la même somme.
Voici un exemple :

Code:

        Codage                                Nombre
  ----------------------------------------------------------
  0000000000000000000000000001000010000 00000000000001010010
  0000000000000000000000000010000100000 00000000000010010100
  ----------------------------------------------------------
  0000000000000000000000000010000010000 00000000000010010010
  0000000000000000000000000001000100000 00000000000001010100
  ----------------------------------------------------------
s=0000000000000000000000000011000110000 00000000000011010110

Le comptage des bits se fait à partir de la droite, commence à 1 pour le nombre et à 3 pour le codage

Ajouté :
Même pour n=5, il y a 1 collision :

Code:

  -------------
  0010010 01101
  0100100 10110
  -------------
  0100010 10101
  0010100 01110
  -------------
s=0110110 11111

 #31 - 10-05-2016 08:15:52

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

superposition de nombrrs binaires

Ah oui quand même...
Bon, ben ça ne marche pas. Cette voie est à abandonner.
Merci pour ton aide.

 #32 - 10-05-2016 17:02:25

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

Superpositio de nombres binaires

Bon, j'ai fait un bout de code, qui sur le papier devrait dépoter, mais il me manque un morceau...
Comme indiqué, on peut facilement montrer qu'une permutation de bits donne un ensemble toujours valide. Donc une simple récursion serait bien sûr trop longue, mais si on pouvait identifier les doublons, ça serait sensiblement plus rapide.

Exemple: je teste 0, puis 0,1; puis 0,1,2; puis 0,1,2,4; etc...
par contre, arrivé à 0,2 ==> identique à 0,1 ==> je zappe
je teste 0,3, mais pas 0,3,4 (identique à 0,1,6 que j'aurai déjà testé), etc...
Reste plus qu'à trouver un bon moyen de détecter les doublons.
Ce que j'ai fait :
==> je commence par trier les colonnes en fonction du nombre de 1
==> puis les lignes, en fonction des entiers correspondants
==> construit un nombre à partir de tout ça, et je stocke ce nombre

ex: sur 4 bits, l'ensemble 0,1,3,4 donne
0000
0001
0011
0100
colonne déjà triées, lignes aussi ==> total 0000000100110100
et toujours sur 4 bits: 0, 1, 2, 6 donne
0000
0001
0010
0110
tri par colonne
0000
0100
0001
0011
tri par ligne ==> 0000000100110100
même total donc.

Principal souci : suivant la manière de trier les colonnes avec le même nombre de 1, on peut se retrouver avec un autre code pour un ensemble équivalent.

Rien qu'avec ça, j'ai pu calculer en une dizaine de minutes les résultats pour n=1..9 bits, mais si quelqu'un connait une manière plus efficace d'éviter les doublons, je prends !!!
(Pour info, pour n=9, on évite le calcul de 10^28 ensembles différents !!! donc c'est clairement plus rapide)
(ET pour ne pas être qu'optimiste, mais aussi réaliste, ça se termine avec un dépassement de mémoire, donc je pourrais pas monter bien plus haut que 10 ou 11 bits, mais déjà on pourra peut-être voir un pattern qui se répète)

 #33 - 11-05-2016 13:28:54

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

Superposition d enombres binaires

Eh oui, les doublons, c'est bien là le coeur du problème !

Une autre idée à tester:
On réserve une zone de codage de n bits pour espérer une liste de n(n-1)/2 nombres.
On établit une liste de n nombres premiers autre que le 2. Dans la zone de codage, chaque bit représente un nombre premier (3 pour le 1er bit, 5 pour le second, 7 pour le 3ème...)
Dans la zone des nombres proprement dit, on entrera le produit de 2 nombres premiers différents de la liste.
En superposition, il apparaitra 3 ou 4 bits qui donneront 3 choix seulement pour les solutions possibles.
Par exemple si les bits 3,5,7,11 sont à 1, les couples de nombres possibles sont (15,77) ou ( 21,55) ou (33,35). Il y a de grandes chances pour que la superposition dans la zone de nombres sache faire la différence. C'est bien le cas dans cet exemple.

On peut tester cette méthode d'abord avec les 10 premiers nombres premiers pour voir où ça mène (nombres de doublons).
A noter que les doublons éventuels seront présents en 2 exemplaires seulement, peut être 3 si vraiment pas de chance,  mais pas au dela.

 #34 - 11-05-2016 19:35:07

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

superppsition de nombres binaires

@nodgim #33 :
Pour n=10, j'obtiens 28 paires de couples avec sommes identiques, et 2 triplets.
Par exemple :

Code:

  ---------------------
  0000000110 0000100011  35  5* 7
  0000100010 0001010101  85  5*17
  ---------------------
  0000000110 0000100011  35  5* 7
  0000100100 0001110111 119  7*17
  ---------------------
  0000100010 0001010101  85  5*17
  0000100100 0001110111 119  7*17
  ---------------------
s=0000100110 0001110111

 #35 - 12-05-2016 08:15:34

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

Superposition de nombres binaaires

Merci pour ton test Enigmatus.

Avec n=10, on a 55 nombres. Avec les 28 doublons + 1 triplet, ce sont 29 nombres à éliminer, soit un peu plus que la moitié.
Donc pour n nombres premiers, c'est plutôt vers n²/4 au mieux qu'on peut estimer les nombres possibles. C'est donc moins performant que la méthode " 2 bits à 1".

Ce que je pense, c'est qu'il faut peut être définir un nombre comme un double code, dont chaque code serait indépendant de l'autre, et le format de chaque code serait identique.
Par exemple, 1 code serait défini par 4 bits à 1 dans une zone de 20 bits.
Un nombre serait la combinaison de 2 de ces codes. 1 nombre serait donc défini, par 2*4 bits à 1 dans un champ de 2*20 bits. La superposition donnerait donc de 5 à 8 bits à 1 dans chaque zone, ce qui laisse pas mal de possibilités.

Le problème avec les nombres premiers, c'est que les 1 sont statisquement aussi nombreux que les 0, et donc la superposition n'est pas assez sélective.
En limitant le nombre de bits à 1, on fait baisser ce risque.

Reste maintenant à savoir si on peut définir une fonction bijective pour transformer un code à 4 bits par un autre code à 4 bits. Pour au moins ne pas laisser faire le hasard.

 #36 - 12-05-2016 13:59:03

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

Superpposition de nombres binaires

@scarta #32 :
Après quelques essais, j'ai peut-être une piste pour normaliser les résultats.

Une étape consiste à :
1) Trier les colonnes en les considérant comme des nombres binaires
2) Trier les lignes de la même façon

On continue jusqu'à ce que 2 étapes consécutives donnent le même résultat.

Il y a peut-être des cas qui ne convergent pas, mais dans les essais que j'ai faits avec des tableaux aléatoires 20x20 ou 100x20, il suffit de 3 ou 4 étapes.

 #37 - 15-05-2016 08:56:58

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

Superpositoin de nombres binaires

Pas d'avancées dans la méthode des interventions dans les lignes / colonnes ?
C'est sûrement très long....

 #38 - 15-05-2016 09:33:08

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

syperposition de nombres binaires

La méthode de normalisation que je préconisais en #36 ne marche pas : j'ai de nombreux exemples de matrices 3x3 équivalentes qui convergent en 2 étapes vers des matrices différentes.

 #39 - 15-05-2016 12:56:07

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

Superposition de nombres binnaires

Est il possible de tester cette méthode là ?

-produire un nombre au hasard de 4 bits à 1 parmi 40.

-vérifier à chaque nouveau nombre que la superposition avec l'un quelconque des nombres déja établis n'entaîne pas de superposition existante. Eliminer ce nombre dans l'affirmative et en choisir un autre au hasard.


Mais c'est peut être trop gourmand en temps....

 #40 - 15-05-2016 19:17:44

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

superpisition de nombres binaires

@nodgim #39 :
J'ai testé ta proposition qui donne des résultats intéressants, mais le temps de calcul augmente vite avec le nombre de nombres générés.

Code:

Pour générer 100 nombres :     1 seconde
             200 nombres :    19 secondes
             300 nombres :   121 secondes
             400 nombres :   558 secondes
             500 nombres :  1879 secondes
             600 nombres :  5004 secondes
             625 nombres :  6498 secondes

 #41 - 16-05-2016 08:01:09

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

Superposition de nombes binaires

Merci Enigmatus.
C'est plus long qu'une fonction cubique, à cause des échecs qui se multpilient avec le temps.
Bon, encore une méthode à retenir pour... ne plus l'utiliser.

 #42 - 16-05-2016 08:44:57

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

Superrposition de nombres binaires

@nodgim #41 :
Dans un de mes essais, il a fallu tirer 3263 quadruplets pour n'en garder que 783. La vérification prend aussi de plus en plus de temps.

Édité : Après amélioration du programme, j'obtiens 1000 nombres de 39 bits en moins de 3 secondes (après tirage de 31226 quadruplets)

Édité (2) : En appliquant toujours ta méthode, mais en tirant au hasard 8 bits au lieu de 4, pour des nombres de 28 bits, j'obtiens 1000 nombres en moins de 6 secondes, pour 65849 tirages.

 #43 - 19-05-2016 17:39:59

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

Superposition de nombres bniaires

C'est très impressionnant !

Il faut que tu transmettes l'info à cette adresse :

http://www.maths-forum.com/enigmes/dine … 70419.html

Il faut que tu sois inscrit pour ajouter un message (je ne me rappelle pas y avoir vu ton pseudo)

ça va en épater plus d'un, d'autant que ça fait un moment que ce sujet tourne !

Pense à rappeler la méthode générale et joins ton programme.

 #44 - 20-05-2016 19:34:11

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

Superpoition de nombres binaires

@nodgim #43 :
Je ne vais pas m'inscrire mais j'ai regardé ton lien. Si j'ai bien compris, l'énigme que tu poses ici permet de résoudre le problème des 1000 bouteilles dont 2 sont empoisonnées, le nombre de bits du code étant le nombre de testeurs (au testeur n° k est attribué le bit n° k des codes). Chaque testeur n'a besoin de boire qu'une seule fois, en composant son breuvage à partir des bouteilles dont le code contient un bit à 1 en k ème colonne.

Toujours avec ta méthode, j'en suis à 27 bits, dont 8 tirés au hasard et mis à 1. Suivant les tirages, j'arrive à 1000 entre 55 et 80 secondes. Une fois le programme s'est arrêté à 996, après avoir épuisé les combinaisons, mais il arrive fréquemment jusqu'à 1015.

Voici le script :

Code:

#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
# 
# enigmatus mai 2016 (sur une idée de nodgim)
# 
import sys
from itertools import combinations as C
from random import seed, shuffle
from time import time

#seed(0)
k=0
k+=1;N=int(sys.argv[k])   # Nb de bits
k+=1;M=int(sys.argv[k])   # Nb de bits choisis à 1
try: k+=1;B=int(sys.argv[k])   # Nb de nombres voulu
except IndexError: B=None
try: k+=1;NN=int(sys.argv[k])  # Nb max de tirages
except IndexError: NN=None
#-------------------------------------------------
def bi(n,l):
 # Représentation binaire de n sur l bits
   s=bin(n)[2:]
   ret='0'*(l-len(s))+s
   return ret
cods=[]; soms=set()
#-------------------------------------------------
def gener_bits():
 # Génération dans un ordre aléatoire des combinaisons de M bits pris parmi N
   lst=list(C(range(N),M))
   shuffle(lst)
   for bits in lst: yield bits
   return
#-------------------------------------------------
def gener_cod():
 # Génération et test des encodages
   global soms, nn
   genbits=gener_bits()
   nn=0
   while not NN or nn<NN:
      try: bits=next(genbits)
      except StopIteration: print('\nFini : Combinaisons épuisées=%d'%nn); break
      nn+=1
      cod=0
      for k in bits: cod+=1<<k
      deja=False
      som_new=set()
      for cod0 in cods:
         som=cod0|cod
         if som in som_new or som in soms: deja=True; break
         else: som_new.add(som)
      if not deja:
         soms|=som_new
         cods.append(cod)
         yield bi(cod,N)
   return
#-------------------------------------------------
mat=[]; c=0; nn1=0; T0=T1=time()
gencod=gener_cod()
while True:
   try: cod=next(gencod)
   except StopIteration: print('\nFini : Nb max de tirages=%d'%nn); break
   c+=1; T2=time();
   print("%4d %s %7d %7d %8.3f %10.3f %9.6f %9.6f"%(c,cod,nn-nn1,nn,T2-T1,T2-T0,(T2-T1)/(nn-nn1),(T2-T0)/nn));
   sys.stdout.flush()
   nn1=nn; T1=T2
   mat.append(cod)
   if B and c>=B: print('\nFini : Résultat atteint=%d'%c); break
print("%d nombres de %d bits générés, avec tirage aléatoire de %d bits"%(len(mat),N,M))

À lancer ainsi (les 2 derniers paramètres sont facultatifs) :

Code:

./le_script.py nb_de_bits nb_de_bits_a_1 nb_de_codes_a_generer nb_max_de_tirages

 #45 - 20-05-2016 19:45:56

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

Superposition de nombres binaries

Merci Enigmatus.

Tu as en effet bien compris le problème. Jusqu'à maintenant, c'est Doraki, un mec plutôt baleze en math, qui s'est le plus investi sur le sujet.

C'est dommage que tu n'ailles pas sur le site, tu pourrais mieux que moi expliquer ta démarche.

Je vais copier ton programme pour le mettre sur le sujet en question.

@+

 #46 - 21-05-2016 00:55:55

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

superposition se nombres binaires

Doraki, et ses posts surprenants du ProjectEuler...
La Scène Française marche toujours bien smile

 #47 - 21-05-2016 01:54:36

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

Superpositionn de nombres binaires

ProjectEuler les trente premiers sont fait mais la suite me tente moins lol


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

 #48 - 21-05-2016 03:25:38

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

Sueprposition de nombres binaires

Level 11
Solved 281 out of 560 problems

Mon préféré tout recent reste le 544
https://projecteuler.net/problem=544

Mais je me rappelle que les commentaires de Doraki sur les sujets 223/224 ont été de véritables ovnis par rapport aux autres, les problèmes devenant ridiculement simples alors que tout le monde se complaisait à dire que c'était pas facile facile...

 #49 - 21-05-2016 08:15:39

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

superpositipn de nombres binaires

Je ne pense pas que l'on parle du même Doraki.

 #50 - 21-05-2016 08:26:28

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

Superposiiton de nombres binaires

Sinon, en Français, quel est ce problème ?

Mon préféré tout recent reste le 544
https://projecteuler.net/problem=544

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

Sujet Date Forum
P2T
Des nombres binaires par Promath-
20-12-2015 Enigmes Mathématiques
P2T
09-12-2010 Enigmes Mathématiques
28-08-2007 Enigmes Mathématiques
23-01-2008 Enigmes Mathématiques
19-10-2007 Enigmes Mathématiques
21-05-2011 Enigmes Mathématiques
P2T
13-08-2016 Enigmes Mathématiques
P2T
Equation par salehseghiri
15-06-2009 Enigmes Mathématiques
P2T
Oh ! les chiffres par steph54360
05-01-2014 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