Enigme Le retour des 3 sous-ensembles @ Prise2Tete

Ebichu · #1

L'ensemble {1, 2, ..., 24} est divisé en 3 sous-ensembles.

Prouvez qu'au moins un de ces sous-ensembles contient 3 nombres distincts a, b, c tels que a+b=c.

Source : http://www.prise2tete.fr/forum/viewtopic.php?id=9941

À l'époque, l'énigme avait été proposée avec 49 au lieu de 24... mais on peut faire mieux que 49.

dylasse · #2

A: 1,2,4
B: 3,5,6,7
C: 8,9,10,11,12,13,14,15,16

Je n'ai pas un seul triplé qui vérifie a+b=c. J'ai du rater un truc.

enigmatus · #3

Bonjour dylasse,
D'après ce que je comprends, les 3 sous-ensembles doivent former une partition de l'ensemble initial.

gwen27 · #4

Il te reste à loger 17 18 19 20 21 22 23 24

Ebichu · #5

Tout à fait : l'énoncé serait faux si dylasse pouvait faire la même chose avec tous les nombres entiers de 1 à 24.

Klimrod · #6

En tout cas, avec 23, ça a l'air d'être possible :

1-2-4-8-11-22
3-5-6-7-19-21-23
9-10-12-13-14-15-16-17-18-20

Ebichu · #7

Bien vu : Klimrod a trouvé une des 3 possibilités pour répartir les 23 premiers entiers.

Et au fait, quelles sont les deux autres ?

enigmatus · #8

Pour 23, j'obtiens 5 solutions (dont celle de Klimrod #6), avec un script en python3.

Code:

1) {1, 2, 4, 8, 11, 22}     {3, 5, 6, 7, 19, 21, 23} {9, 10, 12, 13, 14, 15, 16, 17, 18, 20}
2) {1, 2, 4, 8, 11, 16, 22} {3, 5, 6, 7, 19, 21, 23} {9, 10, 12, 13, 14, 15, 17, 18, 20}
3) {1, 2, 4, 8, 11, 17, 22} {3, 5, 6, 7, 19, 21, 23} {9, 10, 12, 13, 14, 15, 16, 18, 20}
4) {3, 5, 6, 7, 19, 21, 23} {1, 2, 4, 8, 11, 16, 22} {9, 10, 12, 13, 14, 15, 17, 18, 20}
5) {3, 5, 6, 7, 19, 21, 23} {1, 2, 4, 8, 11, 17, 22} {9, 10, 12, 13, 14, 15, 16, 18, 20}

Ajouté :
Si ce calcul est juste, il prouve du même coup que ce n'est pas possible pour 24, car on ne peut ajouter ce nombre dans aucun des sous-ensembles obtenus avec 23.
A fortiori, c'est impossible aussi pour les valeurs supérieures.

Édité :
Comme le fait remarquer Klimrod en #9, les solutions 2) et 4) sont identiques, ainsi que 3) et 5)

Klimrod · #9

Les solutions 2 et 3 sont identiques aux solutions 4 et 5. Il y a donc bien 3 solutions en tout !

Ce qui est intéressant c'est qu'elles sont toutes les 3 basées sur le même schéma :
1-2-4-8-11-22, seuls, ou avec le 16, ou avec le 17
3-5-6-7-19-21-23 uniquement,
9-10-12-13-14-15-18-20 avec le 16 et le 17 ou l'un des deux seulement.

enigmatus · #10

Ah oui Klimrod, tu as raison, je n'avais pas bien regardé…

Ebichu · #11

Félicitations à enigmatus : c'est également avec un programme que j'avais résolu ce problème. En identifiant les solutions identiques (comme l'a fait Klimrod), j'obtiens 8067 répartitions "maximales" (pour lesquelles on ne peut plus ajouter de nombre, comme 1.6.8.11.13 - 2.4.7.12 - 3.5.9.10) : ça pourrait permettre de vérifier que nos programmes trouvent la même chose.

enigmatus · #12

@Ebichu : Que représente ton 8067 ?
Voici le nombre de partitions différentes que j'obtiens pour un nombre d'éléments variant de 3 à 23 :

Code:

  Nombre     Nombre de partitions 
d'éléments        différentes
     3                 1
     4                 6
     5                21
     6                58
     7               133
     8               289
     9               525
    10               920
    11              1438
    12              2009
    13              2603
    14              2856
    15              2929
    16              2452
    17              2010
    18              1176
    19               710
    20               357
    21               151
    22                32
    23                 3
 Total             20679

Ebichu · #13

@enigmatus

Mon programme m'a permis de trouver les mêmes valeurs que toi, ce qui est rassurant.

Concernant 8067, c'est le nombre de partitions "maximales", pour lesquelles on ne peut plus rien ajouter. Par exemple, il y a une seule partition maximale pour 6 éléments, c'est 1.6 - 2.5 - 3.4.

Code:

  Nombre   Nb de partitions
d'éléments   "maximales"
    6            1
    7            2
    8           21
    9           49
   10          141
   11          277
   12          509
   13          920
   14         1065
   15         1302
   16         1082
   17         1234
   18          629
   19          449
   20          231
   21          123
   22           29
   23            3
Total         8067

Mais il ne t'est peut être pas facile de vérifier ces valeurs, suivant comment ton programme fonctionne.

enigmatus · #14

@Ebichu : Je trouve en effet les mêmes valeurs que toi, après avoir adapté mon script.

dylasse · #15

Comme vous le voyez, j'ai du mal à compter jusqu'à 24 ! ! !
La raison est simple : je ne maîtrise aucun logiciel de code dont certains de nos amis sont friands. Et je deviens jaloux, car Excel, que je chéris, atteint parfois ces limites..

J'ai donc 2 questions diamétralement opposées :
1. Que recommandez-vous comme programme pour faire vos codes ?
2. A part l'essai systématique de toutes les partitions possibles, peut-on "prouver" qu'aucune ne marche à partir de 24 ?

enigmatus · #16

@dylasse #15 :

1. Personnellement, j'utilise python, que je trouve relativement facile à prendre en main pour se mettre à la programmation

2. Ça doit être possible, mais je ne sais pas faire

Si on part des 3 solutions pour 23, on peut facilement vérifier à la main qu'on ne peut pas placer le 24

Ebichu · #17

@dylasse

1. J'utilise C++, pour des raisons historiques, mais je ne le conseillerais pas pour commencer. Il doit exister bien des langages plus simples, mais je ne les connais pas.

2. Quand on voit la difficulté pour trouver une preuve manuelle qui ne permet de prouver le résultat "que" pour 49, il y a de quoi être pessimiste quand à l'existence d'une telle preuve pour 24. Mais qui sait...

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 27-02-2015 18:48:44

Le retour des 3 sous-eensembles

#0 Pub

#2 - 28-02-2015 01:01:46

Le retour des 3 sous-ensembbles

#3 - 02-03-2015 10:40:57

Le retour des 3 sus-ensembles

#4 - 02-03-2015 11:01:20

eL retour des 3 sous-ensembles

#5 - 02-03-2015 20:37:19

le retour ses 3 sous-ensembles

#6 - 03-03-2015 02:06:09

Le retour des 3 sous-ensemble

#7 - 03-03-2015 15:58:24

Le retour des 3 sous-nesembles

#8 - 04-03-2015 04:24:58

le retour des 3 sous-ensemblzs

Code:

#9 - 04-03-2015 08:05:46

me retour des 3 sous-ensembles

#10 - 04-03-2015 08:12:24

Le retuor des 3 sous-ensembles

#11 - 04-03-2015 15:09:19

Le retour des 3 ssous-ensembles

#12 - 04-03-2015 17:56:07

Le retour des 3 sous-ensebles

Code:

#13 - 04-03-2015 18:41:20

le retour dzs 3 sous-ensembles

Code:

#14 - 04-03-2015 19:29:24

Le reour des 3 sous-ensembles

#15 - 05-03-2015 13:22:54

le rrtour des 3 sous-ensembles

#16 - 05-03-2015 13:58:32

Le retour des 3 sous-ensembbles

#17 - 05-03-2015 16:37:26

Lee retour des 3 sous-ensembles

Réponse rapide

Sujets similaires

Pied de page des forums