Commentaire sur l'article

• Août 2018, 3e défi

  le 17 août 2018 à 08:01, par mesmaker

  Cela est impossible.
  Raisonnons par l’absurde. Si cela était possible alors les 33 nombres seraient dans 11 sous-ensembles disjoints composés chacun de trois nombres différents. La somme 1+2+...+33 = 561 serait alors égale à la somme des nombres des 11 sous-ensembles. Or, dans chaque sous-ensemble composé de trois nombres, un nombre est la somme des deux autres. Alors la somme des trois nombres est paire (2 fois le plus grand nombre). Ainsi la somme des nombres des 11 sous-ensembles est une somme de nombres pairs donc paire. Donc 561 devrait être pair mais est impair : absurde.

  Répondre à ce message
• Août 2018, 3e défi

  le 17 août 2018 à 10:02, par Niak

  Oui. Une petite variante consiste à observer qu’il n’y a que deux types de groupes : ceux constitués de $3$ pairs et ceux constitués de $2$ impairs et $1$ pair. Le nombre total d’impairs, qui vaut $17$, est donc aussi égal à $2$ fois le nombre de groupes du second type, et est donc pair...

  Répondre à ce message

• Août 2018, 3e défi

  le 18 août 2018 à 13:05, par Pierre Cami

  la solution n’est possible qu’avec 1, 2, 3, 4, 5, ..., 26, 27, 29, 33, 39, 43, 49, 53 ensemble aux plus petits nombres possibles pour atteindre la solution et autres ensembles à somme supérieure, en effet :
  1+2=3, 4+5=9, 6+7=13, 8+10=18, 11+12=23, 14+15=29, 16+17=33, 19+20=39, 21+22=43, 24+25=49, 26+27=53

  Répondre à ce message
• Août 2018, 3e défi

  le 19 août 2018 à 10:29, par Blaxapate

  C’est possible pour $\{1,\cdots,12\}$.

  Répondre à ce message
• Août 2018, 3e défi

  le 19 août 2018 à 18:04, par Niak

  Mais si l’on s’autorise à réduire la taille de l’ensemble, alors à ce compte là c’est aussi possible pour $\{1,2,3\}$...

  Répondre à ce message

• Août 2018, 3e défi

  le 19 août 2018 à 17:57, par Niak

  Cela me semble faux (mais vous ne dites pas ce que vous entendez par les « plus petits nombres possibles »), cf. les exemples que je donne plus bas.

  Répondre à ce message

• Août 2018, 3e défi

  le 17 août 2018 à 18:07, par ROUX

  La somme de ces 33 entiers est égale à 561.
  Or la somme S de 22 de ces entiers devrait être égale à la somme S des 11 autres.
  On aurait alors 2×S=561 ce qui n’est pas possible.
  Donc non.

  Mais ce critère permet a priori de le faire pour les entiers de 2 à 34 dont la somme est 594.

  Mais est-ce un critère nécessaire ou suffisant ?

  Répondre à ce message
• Août 2018, 3e défi

  le 18 août 2018 à 14:26, par Pierre Cami

  La somme minimum semble être 597 = 26*27/2+29+33+39+43+49+53

  Répondre à ce message
• Août 2018, 3e défi

  le 19 août 2018 à 10:50, par Pierre Cami

  Désolé, je me suis trompé, le minimum est 27*28/2+29+33+39+43+49+53=624 !

  Répondre à ce message

• Août 2018, 3e défi

  le 19 août 2018 à 17:38, par Niak

  Et pourquoi pas $562$ pour l’ensemble $\{1,2,\ldots,32,34\}$ ?

  Avec par exemple : $1+2=3$, $4+19=23$, $5+13=18$, $6+25=31$, $7+22=29$, $8+24=32$, $9+21=30$, $10+16=26$, $11+17=28$, $12+15=27$, $14+20=34$.

  Répondre à ce message

• Août 2018, 3e défi

  le 19 août 2018 à 17:47, par Niak

  Je ne sais pas si le critère est suffisant en toute généralité (sous entendu pour des ensembles de nombres consécutifs ici), mais pour l’ensemble $\{2,3,\ldots,34\}$ il y a bien de nombreuses solutions.
  Par exemple : $2+31=33$, $3+11=14$, $4+22=26$, $5+16=21$, $6+24=30$, $7+25=32$, $8+20=28$, $9+18=27$, $10+13=23$, $12+17=29$, $15+19=34$.

  Répondre à ce message
• Août 2018, 3e défi

  le 20 août 2018 à 10:42, par ROUX

  J’avais démontré que la moyenne des entiers seuls devait être exactement égale à 27 (27×11 qui est égale à la moitié de la somme de tous les entiers de 2 à 34).
  Comment avez-vous déterminé ces triplets : ordinateur ou protocole parce que moi au crayon et à la gomme je n’y arrivais pas 😢

  Répondre à ce message
• Août 2018, 3e défi

  le 20 août 2018 à 14:31, par Niak

  J’ai en effet demandé gentiment à mon ordinateur.

  Répondre à ce message
• Août 2018, 3e défi

  le 20 août 2018 à 15:46, par ROUX

  😉😊
  Et au crayon et à la gomme, une idée de protocole ? Comment distribuer les onze entiers seuls par exemple ?

  Répondre à ce message
• Août 2018, 3e défi

  le 20 août 2018 à 17:20, par Niak

  Je ne sais pas. C’est un cas particulier d’Exact Cover, pour des sous-ensembles de taille $3$ définis par une contrainte arithmétique, mais je ne suis pas certain que cela simplifie grandement le problème d’origine pour lequel aucune méthode « efficace » (en un certain sens théorique) n’est connue...

  Répondre à ce message
• Août 2018, 3e défi

  le 20 août 2018 à 21:00, par ROUX

  Ah oui...
  Merci !

  Répondre à ce message

• Août 2018, 3e défi

  le 19 août 2018 à 19:58, par Niak

  En toute généralité, ce n’est pas une CNS, par exemple l’ensemble $\{1,3,4,6,7,9\}$ de taille $6$ de somme $30$ vérifie $6+9 = 1+3+4+7 = 15$ mais n’admet pas de solution car $9 = 3+6$ est un triplet indispensable mais $1+4\neq7$.

  Répondre à ce message
• Août 2018, 3e défi

  le 20 août 2018 à 10:34, par ROUX

  Je vous remercie.

  Répondre à ce message

• Août 2018, 3e défi

  le 21 août 2018 à 20:27, par drai.david

  Pour l’ensemble $\left\{1,...,12\right\}$, il existe $8$ partitions :

  1) 1-5-6 , 2-8-10 , 3-9-12 , 4-7-11
  2) 1-5-6 , 2-9-11 , 3-7-10 , 4-8-12
  3) 1-6-7 , 2-10-12 , 3-8-11 , 4-5-9
  4) 1-8-9 , 2-10-12 , 3-4-7 , 5-6-11
  5) 1-9-10 , 2-4-6 , 3-8-11 , 5-7-12
  6) 1-10-11 , 2-5-7 , 3-6-9 , 4-8-12
  7) 1-11-12 , 2-6-8 , 3-7-10 , 4-5-9
  8) 1-11-12 , 2-7-9 , 3-5-8 , 4-6-10

  Pour l’ensemble $\left\{1,...,15\right\}$, il en existe $21$.
  Pour l’ensemble $\left\{1,...,24\right\}$, il en existe $3\;040$.
  Pour l’ensemble $\left\{1,...,27\right\}$, il en existe $20\;505$.
  Pour l’ensemble $\left\{1,...,36\right\}$, il en existe $10\;567\;748$.
  Pour l’ensemble $\left\{1,...,39\right\}$, il en existe $103\;372\;655$.

  Des partitions existent si, et seulement si l’ensemble est de la forme $\left\{1,...,3n\right\}$ avec $n\equiv 0 \;\mathrm{ou}\;1\; [4]$.

  Répondre à ce message
• Août 2018, 3e défi

  le 22 août 2018 à 22:54, par Niak

  En effet, ces valeurs sont d’ailleurs sur l’OEIS (qui renvoie à Dancing Links, un algorithme pour Exact Cover, comme méthode de calcul, ce qui semble conforter ce que je suggérais plus haut du coup).
  Combien de temps avez-vous mis pour calculer la dernière ?

  Répondre à ce message
• Août 2018, 3e défi

  le 23 août 2018 à 12:46, par drai.david

  Soyons honnête : je débute en programmation et je viens de découvrir l’existence de l’algorithme des liens dansants il y a à peine 3 jours (page 194 du livre « Programmation efficace » de Christoph Dürr et Jill-Jênn Vie, Ellipses 2016) et je ne le maîtrise pas encore. J’ai donc programmé bêtement en itératif jusqu’à n=24, puis j’ai retrouvé ma suite sur l’OEIS.
  Donc les 3 dernières valeurs ne sont pas de moi...
  Conclusion : il faut toujours citer ses sources pour ne pas être pris la main dans le panier ! ;-)

  Répondre à ce message
• Août 2018, 3e défi

  le 23 août 2018 à 14:45, par Niak

  Ah ok, parce que du coup par curiosité j’avais vraiment laissé tourner mon implémentation de Dancing Links (en C++, pas en Python comme celle de tryalgo dont vous parlez) dessus et il a tout de même fallu 1h45 pour obtenir la dernière valeur (calcul sur 1 cœur de CPU à 3.3GHz, code compilé avec g++ -O3) !...

  $ time ./a.out
  103372655
  ./a.out 6285,15s user 1,15s system 99% cpu 1:44:50,64 total
  

  Répondre à ce message
• Août 2018, 3e défi

  le 25 septembre 2020 à 14:29, par Niak

  Petite rectification (je retombe là-dessus deux ans plus tard), il y avait une petite optimisation manquante dans mon énumération des solutions qui réduit cependant très significativement le temps de calcul : moins de 3 min sont en réalité nécessaires pour obtenir la dernière valeur !...

  Répondre à ce message