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