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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Le retuor des 3 sous-ensembles

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.

  • |
  • Répondre

#0 Pub

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

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Le retour des 3 sosu-ensembles

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.

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

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Le retour des 3 sous-ensemblles

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

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

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,993E+3

Le retou des 3 sous-ensembles

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

lz retour des 3 sous-ensembles

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

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

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4050
Lieu: hébesphénorotonde triangulaire

le retour deq 3 sous-ensembles

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


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Le retour des 3 souus-ensembles

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 ?

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

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

le retoue des 3 sous-ensembles

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)

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

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4050
Lieu: hébesphénorotonde triangulaire

le retour fes 3 sous-ensembles

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.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

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

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Le etour des 3 sous-ensembles

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Le retour des 3 sous-ensembls

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.

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

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

le retout des 3 sous-ensembles

@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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

le retour des 3 sous-ensemvles

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

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

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

me retour des 3 sous-ensembles

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

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

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Le retour des 3 sous--ensembles

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 ?

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

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Le retour des 3 sous-nesembles

@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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Le retour des 3 sous-ensemlbes

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

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 31ème, en quelle position êtes-vous ?

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