|
#26 - 08-05-2016 12:05:51
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1961
Superposittion de nombres 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
#27 - 08-05-2016 16:02:06
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
superposition de nombres binaures
@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 : 3802
Superpositionn 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 : 3802
Superposition de nombres binairse
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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
superposution de nombres 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 :
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 :
#31 - 10-05-2016 08:15:52
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Superposittion de nombres 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 : 1961
superposition de bombres 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 : 3802
superpositiob de nombres 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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Superposition de nobres binaires
@nodgim #33 : Pour n=10, j'obtiens 28 paires de couples avec sommes identiques, et 2 triplets. Par exemple :
#35 - 12-05-2016 08:15:34
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
superposition de nombres ninaires
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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Supreposition 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 : 3802
superposition de nombres binaireq
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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
superposition de nombres vinaires
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 : 3802
superposition de nombres bonaires
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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
superposition de nombres binairzs
@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.
#41 - 16-05-2016 08:01:09
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Superposition de nombres biniares
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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Superposiiton 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 : 3802
Superposition de nombre sbinaires
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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
superposition dz 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 :
À lancer ainsi (les 2 derniers paramètres sont facultatifs) :
#45 - 20-05-2016 19:45:56
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Superpositin de nombres binaires
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 : 1961
Superposition e nombres binaires
Doraki, et ses posts surprenants du ProjectEuler... La Scène Française marche toujours bien
#47 - 21-05-2016 01:54:36
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Suprposition de nombres binaires
ProjectEuler les trente premiers sont fait mais la suite me tente moins
"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 : 1961
Superposition de ombres 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 : 3802
Sueprposition 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 : 3802
superposition de nombres bunaires
Sinon, en Français, quel est ce problème ?
Mon préféré tout recent reste le 544 https://projecteuler.net/problem=544
Mots clés des moteurs de recherche
|
|