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

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.

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 :

        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 :

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

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)

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

  ---------------------
  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

@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.

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.

@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.

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

@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.

@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 :

#!/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) :

./le_script.py nb_de_bits nb_de_bits_a_1 nb_de_codes_a_generer nb_max_de_tirages

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

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...

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

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