[Maths] Marathon de problèmes

a marqué ce sujet comme résolu.
Banni

Je sais pas si plonger autant dans de la topologie générale soit utile/souhaitable. À partir du moment où on connait le TVI … pourquoi aller si loin ? C’est peut-être pas la peine de redémontrer le TVI?

Holosmos

Heu, j’en sais rien… :( C’est surtout que le TVI usuel n’est pas formulé de la manière que je voulais (i.e. on a une fonction d’un connexe vers $\{0,⊥,1\}$ muni de la topologie adaptée, prenant $0$ et $1$ comme valeurs, alors ça prend aussi la valeur $⊥$ ; dans le cas de la connexité par arcs au lieu de la connexité, l’énoncé analogue est le TVI usuel). Les fonctions continues vers $\{0,⊥,1\}$ représentent les couples d’ouverts disjoints. Je préfère prendre les deux ouverts $\{(x,y) ∈ ℝ^2\,|\,x>y\}$ et son symétrique plutôt que de faire avec l’application $(x,y) ↦ x-y$. En fait l’application $(x,y) ↦ x-y$ est juste l’analogue du point de vue de la connexité par arcs. Et puis je ne trouve pas que ce soit aller "si loin" que ça… Utile ou souhaitable, ça dépend du point de vue.


Pour l’exercice de melepe, je ne vois pas l’utilité de l’hypothèse de ne pas avoir trois points alignés. Parce qu’on est quand même obligé de gérer le cas « deux points alignés » qui est forcé d’arriver (à moins de dire qu’il n’y a jamais deux points alignés ? ^^ ).

+0 -0

. Et puis je ne trouve pas que ce soit aller "si loin" que ça… Utile ou souhaitable, ça dépend du point de vue.

Moi je compte en termes de temps de travail. Rédiger 15 lignes pour un alias du TVI alors que c’est pas absolument nécessaire … je sais pas si c’est le bon choix

je ne vois pas l’utilité de l’hypothèse de ne pas avoir trois points alignés

"Un train peut en cacher un autre"

Considérons $2018$ points dans le plan. Et notons $M$ le point qui à l’abscisse la plus petite $m$. Si deux points ont pour abscisse $m$ (il ne peut y en avoir trois sinon on a trouvé trois points alignés), alors on prend celui qui à la plus petite ordonnée. Nous noterons maintenant $\theta$ l’angle entre la droite passant par $M$ et la droite d’équation $x =m$. (Pour la droite d’équation $x = m$ (orienté vers le bas)on a $\theta = 0$ et pour la droite d’équation $x= m$ (orienté vers le haut, comme dans le cercle trigo) on a $\theta = \pi $) Parmis les $2016$ points restant que l’on note $a_i$, on note $\theta_i$ l’angle $\theta$ associé à la droite passant par $M$ et $a_i$. Notons qu’une telle droite ne peut passer par deux points. Ainsi chaque $a_i$ a un unique $\theta_i$. Maintenant l’idée c’est de faire comme dans une "horloge". On note $a_j$ celui qui a |le plus petit angle $\theta$, ainsi il y a $2018$ points "au dessus" de la droite |passant par $M$ et $a_j$. Maintenant on considère le deuxième point $a_k$ parmis les $2017$ qui à le deuxième |plus petit $\theta_k$. Au dessus de la droite passant par $M$ et $a_k$, on a alors |$2015$ points (ceux dont l’angle $\theta$ est supérieur à $\theta_k$) et "en dessous" |on a un seul point. On continue le procédé, et puis qu’à chaque fois on "tourne les aiguilles d’une montre" |(et donc on laisse un point en dessous à chaque fois qu’on tourne) au bout de la $1007$ |opérations, on aura trouver une droite qui passe par $M$ et un $a_i$ tels que on a |séparé les $2018$ points.

+0 -0

Ok je viens de trouver une idée de résolution rapide

On commence par centrer un des points en l’origine en faisant une translation.

On projette les autres points sur le cercle unité. Cela est possible car chaque autre point définit bien un point sur le cercle et deux points ne donnent pas la même projection car trois points ne sont jamais alignés (n’oubliez pas le point en $0$).

Maintenant sur un cercle on peut bêtement chercher la droite passant par l’origine qu’il faut pour séparer, et cette droite convenait dès le début, car la projection sur le cercle ne change pas la position par rapport à la droite.

Pour trouver une telle droite séparatrice … on peut énumérer jusqu’à la 2018/2 - 1. Maintenant on perturbe légèrement la droite pour mettre l’origine dans le sac minoritaire. Cela est possible car les points sont discrets sur le cercle et donc perturber la droite ne change pas la séparation des points du cercle.

+0 -0
Banni

@Holosmos

J’aime bien ta preuve avec l’utilisation de la perturbation.

Moi je compte en termes de temps de travail.

Mais voyons, quand on aime, on ne compte pas ! :D

Rédiger 15 lignes pour un alias du TVI alors que c’est pas absolument nécessaire … je sais pas si c’est le bon choix

Mon raisonnement, c’est que c’est pas de ma faute si c’est pas standard, et que ça devrait l’être (dans un monde idéal où tout le monde dispose d’un temps infini). ^^

"Un train peut en cacher un autre"

Oui justement, j’ai voulu justifier ce que je disais dans la phrase qui suivait, mais je n’avais pas pensé à d’autres manières de procéder, comme la tienne, en fait. Voici la mienne.

On considère toutes les directions. Il existe un nombre fini de directions selon lesquelles il existe deux points alignés. On peut donc sélectionner une direction selon laquelle il n’y a pas deux points alignés. Quand on projette sur $ℝ$ selon cette direction, les images des points sont totalement ordonnées. On prend un point qui sépare l’ensemble des images en deux parties de même cardinal, et on prend l’image réciproque de ce point par la projection. Ça donne une droite séparant les points.


@InaDeepThink

Alors ne le prends pas mal mais j’ai buté sur ta phrase

Nous noterons maintenant $\theta$ l’angle entre la droite passant par $M$ et la droite d’équation $x =m$.

En fait tu voulais dire qu’on identifie une droite passant par $M$ par l’angle $𝜃$ entre elle et la droite d’équation $x=m$, c’est ça ?

Ensuite ta preuve a un petit problème car on ne demande pas de montrer que parmi $2020$ points, il en existe toujours $2018$ qui peuvent être séparés par une droite. On fixe les $2018$ points à l’avance.

+0 -0

Je me permet de mettre le prochain problème.

Problème 20 :

Soit $n\ge1$ un entier et $\mathcal F$, une classe de sous-ensembles de $[\![1,n]\!]$ telle que $|\mathcal F|=2^{n-1}$ et, pour tout triplet $A$, $B$, $C\in\mathcal F$, $A\cap B\cap C\ne\emptyset$. Montrer que $\bigcap_{A\in\mathcal F}A\ne \emptyset$.

Bon ben y a plein qui de bonnes réponses, et effectivement l’hypothèse de "non-alignabilité" était superflue (d’ailleurs la solution que j’avais lue, très semblable à celle de blo ygh, ne s’en servait pas).

@InADeepThink, je voulais juste signaler que tu n’as pas corrigé les nombres comme il fallait (il y a encore un 2019 qui traîne), mais sinon c’est bon !

J’ai l’impression que pour ton problème il y a des hypothèses assez superflues. Quelqu’un a un contre-exemple à :

Si $\mathcal F$ est une famille de sous-ensembles de $[1,n]$ telle que trois éléments ont une intersection jamais vide ; alors l’intersection de tous les éléments est non vide.

?

Banni

@InaDeepThink D’accord mais il faut quand même invoquer le même argument que Holosmos à la fin pour que la droite finale ne passe plus par $M$, n’est-ce pas ?

Il y a le théorème du sandwich au jambon qui généralise le problème 19.

@Holosmos :

On peut reformuler l’énoncé en considérant les complémentaires des $A ∈ \mathcal{F}$ et en prenant la contraposée. Ça donne que si on a un recouvrement $\{A_i\}_i$ de $[\![1,n]\!]$ avec $2^{n-1}$ parties, alors on peut extraire un sous-recouvrement à $3$ éléments. Mais on peut facilement construire des recouvrements avec moins de $2^{n-1}$ parties ne vérifiant par ça. Par exemple, en prenant $n=4$ et les singletons (dans l’énoncé original, ça donne donc $\mathcal{F} = \{X ⊆ [\![1,4]\!]\,|\,|X|=3\}$). Mais je ne sais pas s’il y a des contre-exemples avec $|\mathcal{F}| = 2^{n-1}-1$ pour tout $n$.

Pour moi le problème ne demande pas une droite qui ne passe par aucun point mais juste une droite qui sépare les points, tels que de chaque côté de la droite il y a le même nombre de points, en l’occurrence même si elle passe par $M$ alors elle sépare bien les points. Après j’ai peut-être mal compris le problème.

Pour le problème je ne sais effectivement pas si $2^{n-1}$ est la plus petite borne.

@Holosmos tout est correct, puisque j’ai une solution au problème.

On peut juste prendre $\{1,2, 3, 4\}, \{1,2,3\}, \{2,3,4\}, \{1,3,4\}, \{1,2,4\}$

InaDeepThink

Sauf erreur, ça n’est pas ce que je demande.

Ce qui m’intéresse c’est un contre-exemple pour vérifier la minimalité des hypothèses.

@blo : je comprends pas comment tu formes ta contraposée

+0 -0

@Holosmos tout est correct, puisque j’ai une solution au problème.

On peut juste prendre $\{1,2, 3, 4\}, \{1,2,3\}, \{2,3,4\}, \{1,3,4\}, \{1,2,4\}$

InaDeepThink

Sauf erreur, ça n’est pas ce que je demande.

Ce qui m’intéresse c’est un contre-exemple pour vérifier la minimalité des hypothèses.

Holosmos

Ok dans ce cas là, je ne sais pas si $2^{n-1}$ est toujours la borne la plus petite. Note quand même que ce n’est pas ce que tu as voulu dire ici : :)

J’ai l’impression que pour ton problème il y a des hypothèses assez superflues. Quelqu’un a un contre-exemple à :

Si $\mathcal F$ est une famille de sous-ensembles de $[1,n]$ telle que trois éléments ont une intersection jamais vide ; alors l’intersection de tous les éléments est non vide.

?

Holosmos

@Holosmos En fait je pense que la plus petite borne qu’on peut trouver pour $n \geq 4$ est : $5 \cdot 2^{n-4}$ mais faut que je vérifie la preuve que j’ai en tête.

+0 -0
Banni

@Holosmos

Déjà, on reformule la question en terme des complémentaires des éléments de $\newcommand{\Fc}{\mathcal{F}}\Fc$. Soit $\Fc' := \{∁ X\,|\,X ∈ \Fc\}$. On suppose que $|\Fc'|= 2^{n-1}$. On veut montrer que si pour tout $A, B, C ∈ \Fc'$, on a $A∪B∪C \neq [\![1,n]\!]$, alors on a $⋃_{A ∈ \Fc'} A \neq [\![1,n]\!]$. En passant à la contraposée, ça donne qu’on veut montrer que si $⋃_{A ∈ \Fc'} A = [\![1,n]\!]$, alors il existe $A, B, C ∈ \Fc'$ tel que $A ∪ B ∪ C = [\![1,n]\!]$.

Une solution en prenant cette reformulation :

(J’écris $\Fc$ au lieu de $\Fc'$.) Soit $𝛺 ≔ [\![1,n]\!]$. On considère la relation d’équivalence induite par la partition $\{\{A,∁A\}\,|\,A⊆𝛺\}$ de $2^𝛺$. Comme $|\Fc| = |2^𝛺|/2$, soit il y a deux éléments de $\Fc$ qui sont dans la même classe d’équivalence, soit chaque classe d’équivalence contient exactement un élément. Dans le premier cas, on a $A, ∁A ∈ \Fc$ et donc c’est terminé car $A ∪ ∁A ∪ A = 𝛺$.

Si on est dans le deuxième cas, alors pour tout $A⊆𝛺$, on a $A ∈ \Fc$ ou $∁A ∈ \Fc$. Soit $A ∈ \Fc$ maximal (aucun élément de $\Fc$ ne contient $A$). Si $A = 𝛺$, on a terminé. Sinon, il existe $a ∈ 𝛺⧵A$. Par hypothèse de maximalité, $A ∪ \{a\} ∉ \Fc$, et donc $A' := 𝛺⧵(A ∪ \{a\}) ∈ \Fc$. On a donc trouvé deux parties donc l’union contient tout sauf $a$. Mais comme $\Fc$ couvre $𝛺$, il existe $B ∈ \Fc$ contenant $a$, donc $A ∪ A' ∪ B = 𝛺$.

(En fait on a même que si l’union de deux éléments de $\Fc$ n’est jamais $𝛺$ entier, alors $\Fc$ est un segment initial de l’ensemble des parties de $𝛺$.)

+1 -0

J’ai deux trois commentaires et une incompréhension sur ta preuve.:)

@Holosmos

Déjà, on reformule la question en terme des complémentaires des éléments de $\newcommand{\Fc}{\mathcal{F}}\Fc$. Soit $\Fc' := \{∁ X\,|\,X ∈ \Fc\}$. On suppose que $|\Fc'|= 2^{n-1}$. On veut montrer que si pour tout $A, B, C ∈ \Fc'$, on a $A∪B∪C \neq [\![1,n]\!]$, alors on a $⋃_{A ∈ \Fc'} A \neq [\![1,n]\!]$.

Ici je trouve qu’il serait judicieux/nécessaire de dire que tu utilise la loi de Morgan, parce que sinon le passage au complémentaire peut ne pas paraître immédiat (en tout cas pour moi).

| (J’écris $\Fc$ au lieu de $\Fc'$.) Soit $𝛺 ≔ [\![1,n]\!]$. On forme la partition $\{\{A,∁A\}\,|\,A⊆𝛺\}$ de $𝛺$.

Je vois ce que tu veux dire ici, mais on est d’accord qu’il y a une erreur car $\{\{A,∁A\}\,|\,A⊆𝛺\}$, n’est pas une parition de $𝛺$.

Comme $|\Fc| = |2^𝛺|/2$, Petite typo ici, on a plutôt : $\mathcal{F} \mid = \mid P(𝛺) \mid /2$ (déjà je crois que tu as corrigé par rapport à hier car tu avais marqué juste $ 𝛺$. Ou alors la notation $2^{𝛺}$ existe, mais ça je ne sais pas.

soit il y a deux éléments de $\Fc$ qui sont dans la même classe d’équivalence

Pour moi avoir une partition ne suffit pas pour parler dune classe d’équivalence, pour parler d’une classe d’équivalence il faut une relation et l’ensemble quotient par cette relation.

| Dans le deuxième cas, soit $A ∈ \Fc$ maximal (aucun élément de $\Fc$ ne contient $A$).

Ici, il faut que tu définisse mieux $A$, car là $A$ n’est pas bien défini, pourquoi il n’y aurait pas deux élément de $\mathcal{F}$ ayant cette propriété ?

et donc $A' := 𝛺⧵(A ∪ \{a\}) ∈ \Fc$.

Je ne comprends pas cette déduction, peut être que je loupe un truc évident, mais le fait que : $\cup_{ B \in \mathcal{F} } B = 𝛺$ ne permet pas de déduire le résultat au dessus, (on peut très bien avoir une union de $B$ qui donne $𝛺⧵(A ∪ \{a\})$ et non pas un seul ensemble). EDIT : ok, je crois que j’ai compris. En fait comme : $\mathcal{F}' \cup \mathcal{F} = 𝛺$ et que (dans $\mathcal{F}$ il n’y a pas un élément et son complémentaire) alors ce que tu dis au dessus est vrai.

J’ai remarqué que tu aime bien passer au complémentaire (cf problème sur les e.v ou tu passe au codomaine):) Sinon, ta preuve est plutôt élégante, bravo.

Une autre idée se faisait par récurrence, en disant que dans une telle famille $\mathcal{F}$, on a toujours deux ensembles : $A$ et $B$ tels que : $\mid A \cap B \mid = 1$

+0 -0
Banni

| (J’écris $\Fc$ au lieu de $\Fc'$.) Soit $𝛺 ≔ [\![1,n]\!]$. On forme la partition $\{\{A,∁A\}\,|\,A⊆𝛺\}$ de $𝛺$.

Je vois ce que tu veux dire ici, mais on est d’accord qu’il y a une erreur car $\{\{A,∁A\}\,|\,A⊆𝛺\}$, n’est pas une parition de $𝛺$.

Tout à fait, c’est une partition de $2^𝛺$ et non $𝛺$. Je rectifie.

Comme $|\Fc| = |2^𝛺|/2$,

Petite typo ici, on a plutôt : $\mathcal{F} \mid = \mid P(𝛺) \mid /2$ (déjà je crois que tu as corrigé par rapport à hier car tu avais marqué juste $ 𝛺$. Ou alors la notation $2^{𝛺}$ existe, mais ça je ne sais pas.

Oui, j’ai corrigé dans la nuit. La notation $2^𝛺$ existe, oui. Dans cette notation, $2$ désigne l’ensemble à deux éléments $\{0,1\}$ et quand on a deux ensembles $A$ et $B$, la notation $B^A$ désigne l’ensemble des fonctions de $A$ vers $B$. En utilisant le fait qu’une fonction de $𝛺$ vers $\{0,1\}$ peut être identifiée par l’image réciproque de $1$, on peut identifier $2^𝛺$ et $P(𝛺)$.

soit il y a deux éléments de $\Fc$ qui sont dans la même classe d’équivalence

Pour moi avoir une partition ne suffit pas pour parler dune classe d’équivalence, pour parler d’une classe d’équivalence il faut une relation et l’ensemble quotient par cette relation.

Ah ouais dans ma tête c’était implicite que par « on forme la partition blabla », je voulais dire qu’on considère la relation d’équivalence associée. Je reformule.

| Dans le deuxième cas, soit $A ∈ \Fc$ maximal (aucun élément de $\Fc$ ne contient $A$).

Ici, il faut que tu définisse mieux $A$, car là $A$ n’est pas bien défini, pourquoi il n’y aurait pas deux élément de $\mathcal{F}$ ayant cette propriété ?

Tout ensemble ordonné fini a un élément maximal. J’en prends un quelconque, pas besoin de définir $A$ uniquement.

et donc $A' := 𝛺⧵(A ∪ \{a\}) ∈ \Fc$.

Je ne comprends pas cette déduction, peut être que je loupe un truc évident, mais le fait que : $\cup_{ B \in \mathcal{F} } B = 𝛺$ ne permet pas de déduire le résultat au dessus, (on peut très bien avoir une union de $B$ qui donne $𝛺⧵(A ∪ \{a\})$ et non pas un seul ensemble). EDIT : ok, je crois que j’ai compris. En fait comme : $\mathcal{F}' \cup \mathcal{F} = 𝛺$ et que (dans $\mathcal{F}$ il n’y a pas un élément et son complémentaire) alors ce que tu dis au dessus est vrai.

Par hypothèse (cf. plus haut dans la preuve), on a toujours soit $X ∈ \Fc$, soit $∁ X ∈ \Fc$. Ici on n’a pas $A∪\{a\} ∈ \Fc$, c’est donc que $∁(A∪\{a\}) ∈ \Fc$.

J’ai remarqué que tu aime bien passer au complémentaire (cf problème sur les e.v ou tu passe au codomaine):)

Oui j’aime bien essayer de trouver des reformulations qui me parlent plus (que ce soit des problèmes, des définitions, etc.).

Sinon, ta preuve est plutôt élégante, bravo.

Merci.

Une autre idée se faisait par récurrence, en disant que dans une telle famille $\mathcal{F}$, on a toujours deux ensembles : $A$ et $B$ tels que : $\mid A \cap B \mid = 1$

Tu te places dans la formulation originale ? Par récurrence sur $n$ ? Ce que tu dis est le dual de ce que j’ai prouvé avec $A$ et $∁(A∪\{a\})$ (dont l’union est de « cocardinal » $1$) ? (Dans ma preuve il y a aussi une récurrence cachée dans le « soit $A ∈ \mathcal{F}$ maximal ».)

Quelle est ta preuve avec laquelle tu obtiens une borne de $5 · 2^{n-4}$ ?

edit : J’ai un peu réorganisé la rédaction.

+0 -0

Oui, j’ai corrigé dans la nuit. La notation $2^𝛺$ existe, oui. Dans cette notation, $2$ désigne l’ensemble à deux éléments $\{0,1\}$ et quand on a deux ensembles $A$ et $B$, la notation $B^A$ désigne l’ensemble des fonctions de $A$ vers $B$. En utilisant le fait qu’une fonction de $𝛺$ vers $\{0,1\}$ peut être identifiée par l’image réciproque de $1$, on peut identifier $2^𝛺$ et $P(𝛺)$.

Marrant, je ne savais pas :)

Tout ensemble ordonné fini a un élément maximal. J’en prends un quelconque, pas besoin de définir $A$ uniquement.

Ok je vois, si tu note $B$ l’ensemble des éléments ayant cette propriété tu en prends un quelconque.

A l’inverse : $(P(\Omega), \subset))$, n’’est pas ordonnée, c’est juste un treillis.

Tu te places dans la formulation originale ? Par récurrence sur $n$ ? Ce que tu dis est le dual de ce que j’ai prouvé avec $A$ et $∁(A∪\{a\})$ (dont l’union est de « cocardinal » $1$) ?

Voilà ce que j’avais en tête : (en essayant d’être le plus clair possible :D)

Pour $n = 1$ la propriété est clairement vraie. Si il existe $A, B$ dans $\mathcal F$ tels que : $\mid A \cap B \mid = 1$ alors on a pour tous $C$ dans $\mathcal F$ : $\mid A \cap B \cap C \mid = 1$ et donc $\displaystyle \bigl\vert \bigcap_{A \in \mathcal F} A \bigl\vert = 1$, et donc la propriété est vraie.

$\star$ On va montrer le résultat par récurrence sur $n$. On note $P_n$ la propriété : "Si $n \geq 2$ et $\mathcal F_n$, une classe de sous-ensembles de $[\![1,n]\!]$ telle que $|\mathcal F_n|=2^{n-1}$ et, pour tout triplet $A$, $B$, $C\in\mathcal F$, $A\cap B\cap C\ne\emptyset$ alors il existe $A, B \in \mathcal F$ tels que $\mid A \cap B \mid = 1$"

Initilisation : Si $n = 2$ alors on doit avoir deux sous-ensembles $A$ et $B$ de $[\![1, 2]\!]$ tels que $A \cap B \ne \emptyset$. Puisque $A \ne B$, alors on clairement : $\mid A \cap B \mid= 1$.

Hérédité : Supposons la propriété vraie au rand $n$ et montrons qu’elle est vraie au rang $n+1$. Ecrivons : $\mathcal F_{n+1} = \mathcal G \cup \mathcal H$ ou $\mathcal G$ représente l’ensemble des $A \in \mathcal F$ tels que $n+1 \in A$ et $\mathcal H = \mathcal F_{n+1} \setminus \mathcal G$. On a donc $\mathcal H \cap \mathcal G = \emptyset$. $\mathcal H$ représente donc l’ensemble des éléments de $\mathcal F_{n+1}$ qui ne contiennent pas $n+1$.

$\star$ Si $\mid \mathcal H\mid \geq 2^{n-1}$ alors par hypothèse de récurrence il existe $A, B \in \mathcal H$ tels que $\mid A \cap B \mid = 1$, et la propriété est vraie au rang $n+1$.

$\star$ Si $2^n>\mid \mathcal G \mid > 2^{n-1}$ alors puisque chacun des éléments de $\mathcal G$ est distinct et que l’on a $\displaystyle \mid \mathcal G \mid > \frac{1}{2} \cdot\sum_{k = 0}^{n} {n \choose k} = \frac{1}{2} \cdot 2^n = 2^{n-1}$ alors il existe deux éléments $A, B$ de $\mathcal G$ tels que : $A \setminus\{n+1\} \cap B \setminus \{n+1\} = \emptyset$ (car dans $\mathcal P([\![1, n ]\!])$ chaque élément à un unique complémentaire et donc on peut regrouper les éléments par paire mais par le principe des tiroirs puisque $\mid \mathcal G \mid > 2^{n-1}$ alors on peut bien trouver $A, B$ respectant la propriété ci-dessus). Or cela voudrait dire $A \cap B \cap C = \emptyset$ ou $C$ est un élément de $\mathcal H$, contradiction.

$\star$ Si $\mid \mathcal G \mid = 2^n$ alors chaque élément de $\mathcal F_{n+1} $ vaut $[\![1, n+1]\!]$ et donc les éléments de $\mathcal F$ ne sont pas distincts, contradiction.

On conclut par récurrence en utilisant la remarque au dessus de la preuve.

Quelle est ta preuve avec laquelle tu obtiens une borne de $5 · 2^{n-4}$ ?

C’est pas vraiment une preuve, c’est juste qu’on peut montrer que c’est un minorant pour que la propriété soit vraie.

Effectivement pour tout $n \geq 4$, on peut prendre : $\mathcal{F} = \{ A \cup B \mid A \subseteq \{1, 2, 3, 4\}, \mid A \mid \geq 3 \text{ et } B \subseteq \{5, ..., n \} \}$. Trois éléments de cet ensemble ont une intersection non vide, et pourtant l’intersection de tous ces éléments est vide, et $\mid \mathcal{F} \mid = 5 \cdot 2^{n-4}$. C’est la même idée d’un de tes posts en haut si je ne me trompe pas.

Je trouve ça toujours marrant ces exos sur les ensembles, parcequ’on a un peu du mal à voir comment ça marche et c’est difficile de vraiment bien se représenter le problème, même si ici en reformulant l’énoncé paraît plus "intuitif".

Sinon à toi la main.

+0 -0

@InaDeepThink.

L’exemple que tu donnes à la fin n’est pas un exemple, mais un contre-exemple. Il prouve que si on prend un nombre p d’ensembles trop petit, la propriété n’est plus vraie.

Est-ce que le seuil est à 2(n-1) , ou un peu plus bas, on ne sait pas, mais il est au-dessus de 5*2(n-4) .

+0 -1

Je ne suis pas un grand fan de l’approche par partitions de l’ensemble initial.

Parce que même si on regarde les parties de l’ensemble initial $[1,n]$ et qu’on passe à $[1,n+1]$, la propriété, d’avoir une triple intersection jamais nulle et donc une intersection totale non nulle, reste vraie

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte