Inscription / Connexion Nouveau Sujet
Trois ensembles
Bonjour aux survivants 
Un exercice plus élémentaire que le précédent mais qui prend assez vite la tête .
Montrer que pour trois ensembles A , B et C de même cardinal 24 , il existe toujours un ensemble X tel que le cardinal de son intersection avec A , B et C soit toujours 12 .
On s'amuse sans blankage excessif .
Imod
Bonjour,
Bravo de persévérer alors que le précédent sujet n'a pas provoqué une multitude de réactions.
Premières pierres
Si les ensembles A, B et C sont disjoints, c'est facile.
Idem s'ils sont égaux.
Je ne suis pas particulièrement déçu par le manque de participation à mes problèmes . J'aime bien proposer des exercices difficiles dont je n'ai pas de solution complète pour solliciter des réactions mais ça ne marche pas toujours . Il doit d'ailleurs rester un problème que j'ai posé ici sans fournir de solution alors que j'en ai une . Il faudra que je revois ça
Je suis bien plus inquiété par la disparition complète de propositions sur un site qui certes fonctionne au ralenti mais qui fonctionne toujours .
Pour ajouter une petite pierre à tes remarques , si les trois ensembles ont au moins 12 éléments en commun , c'est facile aussi .
Imod
hello
exact Imod...ce matin par exemple, les 2 sites pilotés par ce même serveur, aucun bug...fluidité nickel
amusez vous bien
En fait ce matin j'ai trouvé une solution élémentaire et très courte . La réponse tient en quelques lignes , sans calcul ou multiples disjonctions des cas .
Je donnerai un indice si besoin
Imod
Bonsoir,
mon message précédent n'est pas passé alors que je me réjouissais d'être enfin connecté.
Pour répondre à la question.
On prend un sous ensemble A' de A ayant douze éléments, un sous ensemble B' de B ayant douze éléments et un sous ensemble C' de C ayant douze éléments.
On prend enfin X=A'
B'C'.
Bonjour Verdurin
Pour éviter les désagréments que tu évoques , il suffit de copier le message que tu veux envoyer avant de le poster . Si la diffusion échoue , il suffit de recommencer , en général ça marche dès la deuxième fois .
Pour ta réponse , il faudrait que A'UB'UC' ait 36 éléments ce qui n'est pas garanti .
Imod
Oui, faire un CTRL+C avant de poster
Et il m'est arrivé d'oublier, et alors à plusieurs reprises, le simple fait de rafraîchir la page dans la barre d'adresse fait que le message alors apparaît
Je donne le schéma qui a fait tilt chez moi :
Cliquez pour afficher
Je vous laisse le décrypter
Imod
Bonsoir,
je suis étonné par le choix des cardinaux.
Il me semble qu'étant donné trois ensembles à n éléments on peut toujours trouver un ensemble ayant exactement k éléments, k inférieur ou égal à n, en commun avec chacun des trois ensembles de départ.
J'ai sans doute raté quelque chose, mais je ne vois pas quoi.
Si il y a un contre-exemple à cette conjecture, merci de me le donner.
En effet dans ma démonstration , je n'utilise absolument pas le fait que 12 soit la moitié de 24 . Je vais tout de même regarder s'il ne faut pas exiger la parité de n .
Imod
Bonjour,
un contre-exemple à ma conjecture.
Soit A={1, 2, 3, 4}, B={3, 4, 5, 6} et C={5, 6, 1, 2}. On ne peut pas trouver d'ensemble ayant exactement trois éléments en commun avec chacun d'eux.
Mais on peut en trouver un ayant exactement deux éléments en commun avec chacun d'eux, par exemple {1, 3, 5}.
Pour être plus précis :
En reprenant le schéma d' Imod si tous les éléments sont dans une intersection entre deux ensembles et aucun dans une intersection entre trois ensembles et que l'on cherche un ensemble ayant exactement k éléments en commun avec chacun d'eux alors k est pair.
Bravo Verdurin , il est toujours bon de trouver des gardes fous .
Après ton interrogation , j'ai revu un peu ma copie qui n'était pas franchement claire mais l'idée tient toujours . Je cherche une illustration rendant les choses plus limpides .
PS: J'ai préparé ce message avant de découvrir le tien .
Imod
Je donne le schéma de ma démonstration .
On note et
son cardinal . si
alors on construit
avec 12 éléments de
. Dans le cas contraire on a la figure suivante dans laquelle on a retiré les éléments de
:
En notant les cardinaux de
et
celui des portions rouges , on a :
. D'après le principe des tiroirs
ou
. Dans les deux cas on peut compléter
pour trouver
avec la propriété voulue .
Imod
Bonjour,
Ce problème m'a embêté. J'ai trouvé une voie pas très commode, mais qui démontre beaucoup plus que la question de départ.
PDF - 79 Ko
J'avoue que je ne comprends pas la démonstration de Imod
Les cardinaux de A, B, C sont tous 24, non ? Ou alors tes A, B, C ne sont pas A, B, C ?
C'est quoi les portions rouges ?
Comment on fait pour compléter ?
J'ai retiré du dessin la partie commune aux trois ensembles , ils conservent un cardinal commun sans cette intersection . Après j'ai réparti les différents morceaux en sachant que A signifie A avec aucun élément de B ou C . Pour la suite , on combine les éléments de A, B,C, A&B,A&C, B&C pour remplir le disque . Les parties rouges ne sont qu'un reliquat et il est facile de voir qu'elles sont égales . Pour la façon d'ajouter des éléments à Y sans déséquilibrer le compteur A,B,C , je ne vois pas où est le problème .
Imod
1°) Donner le même nom à deux ensembles différents, ça ne facilite pas la compréhension.
2°) Même avec cette ambiguïté levée, je ne comprends toujours pas. Les parties rouges reliquat de quoi ? Quant à compléter, si toi tu ne vois pas de problème, moi je ne vois pas ce que tu fais.
Mais si tu ne veux pas expliquer de façon plus compréhensible, tant pis. Je suis content avec ma solution, même si elle est bourrin.
Je reconnais que mon message n'est pas clair , j'ai voulu évité d'envoyer un nouveau PDF et intégrer du LaTeX sur le site devient problématique . J'ai simplement survolé ton PDF , il me semble que nos idées sont voisines . Je vais essayer d'en préparer un lisible et compréhensible .
Imod
Je ne vois pas grand chose de commun entre mon pdf et ton message, à part bien sûr la décomposition de la réunion en sept morceaux.
Comme je l'ai déjà dit , j'ai simplement survolé ton message , je me suis surtout attaché à essayer à rendre le mien compréhensible .
Je joins un PDF
Imod
PDF - 63 Ko
Merci, c'est plus clair. Je comprends ton argument, mais il me semble présenter un gros trou : tu supposes implicitement |A| <= |BC| et les deux autres inégalités par permutation circulaire. Pourquoi aurait-on ces inégalités ?
Je fais l'effort de comprendre ce que tu écris. Puis-je espérer la réciproque ?
Je comprends ton agacement , je vais lire ton message de plus près , tes automatismes ne sont pas les miens
Imod
J'insiste lourdement :
Si j + b + v ≥ 12 , on construit X avec six éléments de A ∪ B ∪ C et six éléments dans la partie complémentaire . Par exemple , si on prend deux éléments dans A , on en prend deux dans BC .
Pourquoi est-on sûr de pouvoir en trouver deux dans BC ? N'utilises-tu pas ici ton hypothèse qu'il y a au moins autant d'éléments dans BC que dans A ?
Bonjour GBZM
J'ai pris un moment avant de répondre car je voulais vérifier ta proposition . Tout est correct mais je ne vois pas comment tu peux en déduire une solution à la question initiale . D'autre part tu es à fond dans les disjonctions de cas , ce que je voulais éviter , c'est efficace mais difficile à suivre surtout si on a une fâcheuse tendance à l'étourderie . J'étais plutôt parti sur une solution globale mais tu as mis le doigt sur un problème que j'avais aussi repéré avec les différences de cardinaux mais que j'avais oublié en me disant qu'on pourrait toujours s'en sortir en symétrisant . En bref , en échangeant et
, le même schéma fonctionne .
Sauf erreur bien entendu 😊
Imod
Tout est correct mais je ne vois pas comment tu peux en déduire une solution à la question initiale .
Voyons ! Je montre qu'on peut enlever exactement 2 à chaque ensemble. Partant de 24, j'arrive à 22. Je recommence : j'arrive à 20 ... et finalement j'arrive à 12. E, fait, je peux arriver à n'importe quel nombre pair.
Je te laisse préciser ce que tu fais dans le cas où ton
Rebonjour GBZM
Pour mon deuxième cas , ce n'est pas plus difficile , on a le schéma suivant :
|A|+|B|+|C|=B+J+V+3R=24+2R et |A&B|+|A&C|+|B&C|=24-R .
Si on prend 6 éléments dans AB , AC , BC et 6 autres dans la partie de même couleur . Si
alors |A|+|B|+|C| > 48 , il suffit de prendre 12 éléments dans chaque ensemble pour conclure ( on rappelle que A représente les éléments du A initial et d'aucun autre ) .
Pour ta démonstration , j'ai enfin compris comment tu fais marcher ta descente en pas de 2 . Tu gardes ton X et tu mets entre parenthèses les deux éléments de A , B et C communs avec X . Après j'ai encore un doute sans doute ridicule sur le fait qu'il pourraient appartenir à plusieurs ensembles .
Sinon c'est plus solide que ce que j'ai proposé
Imod
Dans tes égalités, tu oublies A&B&C. Ça serait mieux d'en tenir compte. Et puis je ne suis pas d'accord avec tes comptes :
"on prend 6 éléments dans AB , AC , BC et 6 autres dans la partie de même couleur" , ça fait 6 dans le A original, 6 dans le B original et 6 dans le C original. Tu es sûr que c'est ce que tu voulais ?
Peux-tu remettre tout d'aplomb ?
Mes non-dits ne sont pas pires que les tiens 😊
Il me semble que j'ai déjà évacué l'intersection des trois ensembles A,B,C qui ne présente aucun intérêt . En prenant 6 éléments dans AB , AC et BC , on trouve aussi 6 éléments de la même couleurs ailleurs , je ne vois pas où est le problème .
Imod
À mon avis, il ne s'agit pas uniquement de non-dits. Par exemple, évacuer l'intersection ABC est une erreur. Je trouve dommage que tu ne travailles pas ta belle idée avec suffisamment de soin. Voici la façon dont je vois les choses :
Avec les notations de Imod : A désigne ceux qui sont uniquement A et ni B ni C, AB ceux qui sont à la fois A et B mais pas C etc.
On a A + AB + CA + ABC = 24, et les trois autres égalités par permutation circulaire. Si ABC >= 12 on gagne en prenant 12 éléments dans ABC. On suppose donc ABC = 12 - k avec k>0. On a A + AB + CA = 12+k, et les deux autres par permutation circulaire
On a A - BC = B - CA = C - AB, on note r cette quantité.
Si r>=0 , alors AB + BC + CA + r = 12 + k. Donc AB + BC + CA >= 12, ou r >= k. Dans le premier cas on peut prendre c éléments dans AB et c dans C, a dans BC et a dans A, b dans CA et b dans B avec a+b+c=12, et c'est gagné. Dans le deuxième on peut prendre k éléments dans A, k dans B, k dans C et avec les 12-k dans ABC c'est gagné.
Si r<0, alors A + B + C + 2 |r| = 12 + k. Donc A+B+C >= k, ou |r| >=6. Dans le premier cas on peut prendre c éléments dans C et c dans AB, a dans A et a dans BC, b dans B et b dans CA avec a+b+c=k et avec les 12-k dans ABC c'est gagné. Dans le deuxième cas on peut prendre 6 éléments dans AB, 6 dans BC et 6 dans CA et c'est gagné.
Bonsoir,
Je suis content avec ma solution, même si elle est bourrin.
J'essaie le brute-force.
Le script ci-dessous énumère tous les profils possibles des 7 régions de Venn compatibles avec
|A| = |B| = |C| = 24, puis teste pour chacun s'il existe un X tel que
|X ∩ A| = |X ∩ B| = |X ∩ C| = 12.
Résultats :
- Nombre de profils X possibles : 2401
- Profils de Venn testés : 28561
- Nombre de contre-exemples : 0
Conclusion : X existe toujours pour le cas demandé.
Cliquez pour afficher@mdr_non : et si tu voulais démontrer qu'étant donnés trois ensembles de même cardinal 2 976 058, il existe un ensemble qui intersecte chacun des trois en exactement 1 318 726 éléments, tu procéderais aussi avec ta "brute force" ?
Bien sûr que non, @GBZM.
Le problème initial 24/12 est suffisamment petit pour qu'on puisse énumérer tous les profils de Venn, puis vérifier qu'un X existe pour chacun d'eux, en quelques secondes.
Pour des cardinaux comme 2 976 058, l'énumération des profils n'a évidemment plus d'intérêt.
Là, une réponse naturelle est ton lemme par blocs de 2, appliqué 659 363 fois successivement.
Trois solutions différentes pour un petit problème sans prétention , on ne va pas se plaindre
@GBZM J'ai une fâcheuse tendance à la paresse depuis quelques temps et je crains que le phénomène ne soit pas réversible .
Imod
Bonsoir,
@GBZM,
Merci et bravo pour ta démonstration ainsi que pour avoir réussi à adopter les notations de Imod.
@Imod,
Bien sur que c'est réversible !
Canicule plus problème perso rendent difficile la concentration.
Mais ça revient !
C'est vrai qu'il est étonnant qu'un problème d'énoncé aussi simple soit aussi compliqué à résoudre.
@mdr_non : et si tu voulais démontrer qu'étant donnés trois ensembles de même cardinal 2 976 058, il existe un ensemble qui intersecte chacun des trois en exactement 1 318 726 éléments, tu procéderais aussi avec ta "brute force" ?
On a A - BC = B - CA = C - AB, on note r cette quantité.
Pour aller au-delà de l'énumération par ordinateur et traiter les grands cardinaux, je repars de cette égalité en conservant ta notation r.
En reprenant le codage binaire du PDF, j'ordonne les sept régions de Venn ainsi : [100, 010, 001, 110, 101, 011, 111],
puis considère les six vecteurs élémentaires suivants :
e_1 = [0, 0, 0, 0, 0, 0, 1] = 111,
e_2 = [1, 0, 0, 0, 0, 1, 0] = 100 + 011,
e_3 = [0, 1, 0, 0, 1, 0, 0] = 010 + 101,
e_4 = [0, 0, 1, 1, 0, 0, 0] = 001 + 110,
e_5 = [1, 1, 1, 0, 0, 0, 0] = 100 + 010 + 001,
e_6 = [0, 0, 0, 1, 1, 1, 0] = 110 + 101 + 011.
Par exemple, e_2 signifie que l'on choisit un élément dans la région 100 et un dans 011.
Chacun des vecteurs e_1, ..., e_5 ajoute exactement 1 à chacun des trois compteurs |X ∩ A|, |X ∩ B| et |X ∩ C|, tandis que e_6 ajoute exactement 2 à chacun d'eux.
Écrivons le vecteur des cardinalités des sept régions sous la forme V = [x_100, x_010, x_001, x_110, x_101, x_011, x_111].
Les contraintes |A| = |B| = |C| = N donnent, par soustraction deux à deux : r = x_100 − x_011 = x_010 − x_101 = x_001 − x_110.
Si r ≥ 0, alors x_100 = x_011 + r, x_010 = x_101 + r et x_001 = x_110 + r, d'où :
V = x_111 × e_1 + x_011 × e_2 + x_101 × e_3 + x_110 × e_4 + r × e_5.
Si r < 0, alors x_011 = x_100 − r, x_101 = x_010 − r et x_110 = x_001 − r, d'où :
V = x_111 × e_1 + x_100 × e_2 + x_010 × e_3 + x_001 × e_4 + (−r) × e_6.
Tous les coefficients sont donc des entiers ≥ 0.
Chaque terme c × e_i signifie que l'on effectue c fois la sélection décrite par e_i, en utilisant à chaque fois des éléments distincts dans les régions concernées.
Dans la décomposition obtenue ci-dessus, notons q le nombre de répétitions de e_6 : q = 0 si r ≥ 0, et q = −r si r < 0.
Comme chaque répétition de e_6 contribue pour 2 à chacune des trois cardinalités, tandis que chaque répétition de e_1, ..., e_5 contribue pour 1, le nombre total de répétitions disponibles parmi e_1, ..., e_5 est N − 2 × q.
Cherchons maintenant une partie X telle que |X ∩ A| = |X ∩ B| = |X ∩ C| = m, avec m pair et 0 ≤ m ≤ N.
Si q ≥ m ∕ 2, il suffit de choisir m ∕ 2 répétitions de e_6.
Si q < m ∕ 2, on choisit les q répétitions de e_6, puis m − 2 × q répétitions parmi e_1, ..., e_5.
Il y en a suffisamment puisque : N − 2 × q ≥ m − 2 × q.
La réunion des éléments ainsi choisis fournit donc la partie X recherchée.
Pour le problème initial, N = 24 et m = 12.
Si q ≥ 6, on choisit six répétitions de e_6. Sinon, on choisit les q répétitions de e_6, puis 12 − 2 × q répétitions parmi e_1, ..., e_5.
De même, pour ton exemple, N = 2 976 058 et m = 2 × 659 363. L'on applique exactement la même alternative selon que q ≥ m ∕ 2 ou q < m ∕ 2.
Concernant la parité de m, tous les m pairs compris entre 0 et N sont toujours réalisables.
Pour m impair, deux cas se présentent.
S'il existe au moins une répétition parmi e_1, ..., e_5, on en fixe une ; alors toutes les valeurs m comprises entre 0 et N sont réalisables.
Si m ≤ 2 × q + 1, on choisit une répétition parmi e_1, ..., e_5 et (m − 1) ∕ 2 répétitions de e_6.
Si m > 2 × q + 1, on choisit les q répétitions de e_6, puis m − 2 × q répétitions parmi e_1, ..., e_5, ce qui est possible puisque m ≤ N.
Inversement, si V = q × e_6, seules les régions 110, 101 et 011 sont non vides.
L'égalité des trois intersections impose alors de choisir le même nombre d'éléments dans chacune de ces trois régions ; chaque intersection en contient donc deux fois ce nombre, et m est nécessairement pair.
Concernant la parité de m, tous les m pairs compris entre 0 et N sont toujours réalisables.
Pour m impair, deux cas se présentent.
S'il existe au moins une répétition parmi e_1, ..., e_5, alors toutes les valeurs impaires de m comprises entre 1 et N sont réalisables.
Si m ≤ 2 × q + 1, on choisit une répétition parmi e_1, ..., e_5 et (m − 1) ∕ 2 répétitions de e_6.
Si m > 2 × q + 1, on choisit les q répétitions de e_6, puis m − 2 × q répétitions parmi e_1, ..., e_5, ce qui est possible puisque m ≤ N.
Inversement, si V = q × e_6, seules les régions 110, 101 et 011 sont non vides.
L'égalité des trois intersections impose alors de choisir le même nombre d'éléments dans chacune de ces trois régions ; chaque intersection en contient donc deux fois ce nombre, et m est nécessairement pair.
Bonsoir,
J'ai l'impression que la démonstration de GBZM, celle du 20 à 22h15, fonctionne en remplaçant 24 et 12 par deux entiers naturels v et d tels que v-d soit un entier naturel pair.
Je me trompe ?
Rebonjour
Je suis nul dans les réactions immédiates , il me faut toujours un moment pour laisser reposer les choses comme pour une pate à crêpes .
Le problème revient à réduire la configuration initiale qui se résume en trois paramètres à la configuration finale , chacune d'elles devant satisfaire l'égalité des parts . On passe en fait d'une position à une autre en réduisant certains éléments et en conservant les contraintes .
J'essaierai d'être plus clair quand le temps me le permettra
Imod
Pour préciser les choses :
On se donne trois ensembles A , B et C de même cardinal n ( pas nécessairement pair ) . On cherche une condition nécessaire et suffisante sur ces ensembles pour qu'à chaque p entre 0 et n , on puisse trouver un ensemble X dont les intersections avec A , B et C soient toutes de cardinal p .
Si je n'ai pas fait d'erreurs , il y a très peu de situations où il sera impossible de trouver X .
Tout d'abord on peut schématiser la situation avec le diagramme suivant :
Les notations sont celles des messages précédents . Les entiers sont tous positifs sauf k qui peut être négatif .
L'idée est de construire X à partir de la réunion des trois ensembles de départ en réduisant les morceaux tout en conservant l'égalité des cardinaux . Notons s = x + y + z et plaçons nous dans le cas où k est positif ou nul . On diminue d'une unité l'intersection de X avec chacun des trois ensembles en diminuant i , s ou k d'une unité . Il est clair qu'on peut décrire ainsi tous les cardinaux de 0 à n .
Je n'ai pas encore détaillé le cas où k est négatif .
Imod
Bonjour,
Je réponds d'abord à mon message du 22 :
Je me trompe pour le cas r positif ou nul.
Ensuite, je propose pour clarifier de démarrer avec trois ensembles T, U, V de même cardinal n.
On peut alors définir les ensembles ABC, BC, AC, AB, A, B , C.
Bonjour imod,
je suis d'accord avec cette solution qui me parait claire.
C'est justement dans le cas où k est négatif qu'on ne peut pas obtenir un ensemble X avec tous les entiers de 0 à n.
Comme cardinal de X on peut obtenir seulement les entiers n, n-1, ... , 2|k|, puis 2|k|-2, ... , de 2 en 2 jusqu'à 0.
Merci Jandri
J?étais sur la même idée et je cherchais à illustrer car un k négatif ne me parlait pas .
On peut toujours réduire i et s =x+y+z en pas de 1 avec la même action sur X mais une réduction de 1 sur k réduit les parts à pas de 2 . En bref quand on a épuisé les i et les s , les pas comptent double .
Imod
* Sylvieg > Message édité pour les illustrations répétées *
Pour illustrer le résultat de Jandri
Donner un exemple de trois ensembles de même cardinal ( le plus petit possible , s'il existe ) pour lesquels aucun ensemble ne peut intersecter chacun d'entre eux en un seul point .
Imod
Annuler
connectez vous