SOS-MATH

les faces de 40 dés cubiques sont numérotées avec des entiers naturels quelconques de façon que :
- chaque dé comporte 6 numéros distincts.
- deux dés ont toujours un et un seul numéro commun.
Existe-t-il forcément un numéro commun à tous les dés ?



J'ai essayé de faire des schémas en arbres mais je n'arrive pas à prouver que la réponse est affirmative.
J'ai pensé à faire un raisonnement par l'absurde pour arriver à une contradiction en ayant envie de construire une suite de termes entiers positifs décroissante mais je n'arrive pas à démarrer concrètement.
Pourriez-vous m'indiquer, si je suis sur la bonne voie, quelle suite il serait ici intéressant de construire ?
Par ailleurs, ce qui me semble surprenant, c'est que nous n'avons pas encore abordé le chapitre sur les suites (en 1S); y aurait-il une autre façon d'aborder le problème ?
Infiniment merci pour la qualité de vos indications ou réponses.
Eric

bonjour,

J'ai mis un peu de temps à répondre car c'est un sacré problème, et qu'il faut laisser murir la réflexion. Je n'ai pas l'impression que l'on puisse résoudre ce problème avec des suites, mais plutôt qu'il faille essayer d'utiliser ce qu'on appelle "le principe de Dirichlet" ou encore "le principe des tiroirs" qui dit en gros que :
si vous avez n tiroirs et n+1 chemises à ranger, alors au moins 1 tiroir contient au moins 1 chemise.
ou encore mieux :
Si vous avez n tiroirs et np+1 chemises à ranger alors au moins 1 tiroir contient au moins p chemises.

Ceci dit, la difficulté dans votre pb, c'est d'identifier ce que sont les chemises et les tiroirs.


Pour simplifier, je vais prendre un dététraèdrique à 4 faces et essayer de construire ces dés en respectant l'énoncé et en essayant d'éviter tant que je peux qu'un numéro soit commun à plus de 2 dés.

1èr dé : 1-2-3-4
2ème dé : 1-5-6-7
3ème dé : 2-5-8-9
4ème dé : 3-6-8-10
5ème dé: 4-7-9-10

On voit par construction que pour construire le 6ème dé, il ne sera plus possible de respecter la condition qu'un numéro est au plus commun à deux dés.

6ème dé :1-9-10 tiens coup de théatre , je n'arrive même pas à construire le 7ème dé, en respectant la règle : 2 dés ont un et un seul numéro commun. Bizarre.

je vous envoie ces premières réflexions, et je continue à y penser.
Est ce vous qui avez proposé l'exercice sur les entiers bons ou mauvais ?
Bon courage

Si je ne me trompe, le principe des tiroirs est le suivant :
si vous avez n tiroirs et n+1 chemises à ranger, alors au moins 1 tiroir contient au moins 2 (et non 1 ) chemises.
ou encore mieux :
Si vous avez n tiroirs et np+1 chemises à ranger alors au moins 1 tiroir contient au moins p + 1 ( et non p ) chemises.
Puis-je dire que si on a n chemises à ranger dans k tiroirs alors au moins 1 tiroir contient au moins m chemises où m est le plus petit entier supérieur ou égal à n/k.
Je comprends votre indication avec des dés tétraédriques mais, après quelques soirées de réflexion, je n'arrive pas à avancer rigoureusement tout en ayant le sentiment qu'intuitivement il y a forcément un numéro commun à tous les dés. En tous cas, il me semble être très loin de réussir à appliquer ce principe de Dirichlet.

Merci pour un coup de pouce supplémentaire.
C'est bien moi qui ai proposé l'exercice avec les nombres bons et mauvais.
J'essaye de m'entraîner à la participation des olympiades mathématiques mais ce type de problème est tellement différent des mathématiques "académiques" qu'on nous enseigne que j'ai l'impression de fournir 10 fois plus d'efforts sans arriver à rien. C'est assez désespérant.

Excusez-moi de cette petite digression et merci encore pour votre écoute.
Très cordialement, Eric

Bonsoir,

Bien sur tu as rectifié mes erreurs d'étourderie, ça prouve que tu t'accroches bien.
J'avoue que je n'ai pas eu le temps de me replonger dans ce pb de dés.
Dans ma classe, il y a 5 élèves qui participent à ces olympiades. Vous serez en compétition.
Bon courage, donc et bonne chance. Quand j'aurai un peu de temps, je reprendrai ce pb. A un moment donné, je me suis demandé s'il n'y avait pas une erreur d'énoncé.

sosmaths

J'ai vérifié : il n'y a pas d'erreur d'énoncé, a priori. Mais cet exercice comporte 3 étoiles (c'est-à-dire de difficulté la plus élevée) parmi l'ensemble des exercices de ce type proposés.
Je serais vraiment très heureux si vous pouviez m'offir le plaisir de la solution (je vous assure qu'il me semble avoir tenté tout ce qui était en mon "pouvoir" d'humble lycéen, j'ai noirci des dizaines de pages mais en vain, mon cerveau bloque ....).
Permettez-moi de vous dire combien je suis rassuré de savoir que vous allez reprendre le problème quand vous aurez plus de temps.
Merci encore pour tout (j'ai parlé de ce problème autour de moi et si quelqu'un venait à me communiquer une esquisse de solution, je vous en ferais immédiatement part ).
Très cordialement, Eric Taous

Voici une solution qu'un prof que je n'ai pas en cours m'a rapidement donné :
Solution:
Soit D1 à D40 les 40 dés comportant chacun 6 numéros distincts et tels que
l'intersection de 2 dés quelconques soit toujours réduite à un nombre et un
seul.
Supposons que D1 soit constitué des nombres 1, 2, 3, 4, 5, 6.

1er cas :
Dans un premier temps, on construit les autres dés en introduisant le
chiffre 1 pour tous les dés D2 à D40 et en complétant chacun de ces dés par
des nombres strictement croissants autres que {1, 2, 3, 4, 5, 6}.
Par exemple : D2 = 1, 7, 8, 9, 10, 11
D3 = 1, 12, 13, 14, 15, 16
D4 = 1, 17, 18, 19, 20, 21
...
Di = 1, 5i-3, 5i-2, 5i-1, 5i, 5i+1

On a bien les hypothèses requises :
- les faces de 40 dés cubiques sont numérotées avec des entiers,
- chaque dé comporte 6 numéros DISTINCTS,
- et deux dés ont toujours UN ET UN SEUL numéro COMMUN = {1}.


2ème cas
Plus généralement, supposons que D1=1, 2, 3, 4, 5, 6.
D1 a un élément commun avec D2, D3, ..., D40.
Or il y a 39 intersections entre D1 et les 39 autres dés et le nombre
intersecté appartient nécessairement à {1, 2, 3, 4, 5, 6}.
Donc dans la liste précédente, si le nombre intercepté n'apparaissait pas
tout le temps de façon identique, il apparaitrait 39/6 = 6,5 fois
(impossible).
Donc ce nombre est commun à tous les dominos.


Mais je ne comprends pas le dernier passage, pourriez-vous me le détailler s'il vous plaît :
"Donc dans la liste précédente, si le nombre intercepté n'apparaissait pas
tout le temps de façon identique, il apparaitrait 39/6 = 6,5 fois"
Merci beaucoup,
Eric

Bonjour,

Si j'examine le 1er cas , il prouve seulement que l'on peut numéroter les 40 dés, en mettant un numéro commun à tous les dés, et tous les autres différents. C'est évident, puisqu'il ya 240 faces à numéroter, et qu'on dispose d'une infinité de nb entiers.

quant au 2ème cas, il ne prouve pas l'impossibilité.
Par contre, il prouve la chose suivante :
Supposons pour fixer les idées que le premier dé est numéroté 1-2-3-4-5-6
Ce dé à un numéro commun avec chacun des 39 autres dés. imaginons qu'au lieu de 39, ils soient 36. Alors en répartissant de la façon la plus égale possible, on aura : le nombre 1 commun à 6 autres dés, le nombre 2 commun à 6 autres dés,...., le nombre 6 commun à 6 autres dés.Voilà : 6x6=36.
Donc chaque numéro du premier dé apparait au moins 7 fois.
Oui, mais il ya 39 dés.
Conclusion ( principe de dirichlet évoqué plus haut) : Il y a au moins 1 numéros du premier dé qui est commun a au moins 8 dés( en tout).
Voilà ce qu'on peut conclure et non pas ce qui était conclu dans le raisonnement que vous n'avez pas compris.
J'avais déjà réfléchi à touit ça, mais je suis maintenant bloqué. Comment faire évoluer ce raisonnement? J'ai ma petite idée , mais elle n'est pas mûre.

Je vous laisse donc pour le moment , avec une petite idée. Ce raisonnement a été fait en prenant un dé particulier en référence, mais il y en a 39 autres .

bon courage

Sosmaths

Bonjour,

J'ai une autre petite idée.

Il ya 40 dés . Si on les groupe par paires, on peut faire correspondre à chaque paire le nombre que ces deux dés ont en commun.
Par exemple si D8 et D21 ont en commun le nombre 17 alors , à la paire (D8, D21) on peut faire correspondre le nombre 17.
Combien y a til de paires de dés ? : réponse : 40x39/2 = 7800 ( on divise par 2 , car la paire D8, D21 est la même que la paire D21, D8

Combien, y a -t-il de nombre sur les 40 dés ? réponse : AU MAXIMUM 6x40= 240

En fait 240 est très supérieur au nombre réel de nombres puisque des nombres sont communs à plusieurs dés.

Si l'on divise 7800 par 240 on trouve 32,..
C'est dire que ( Principe de Dirichlet) il existe au moins un nombre qui apparait 33 fois, donc commun à 33 dés.

Oui , mais c'est pas 40. Donc il faudrait affiner le nombre 240 et trouver un majorant plus petit.
J'ai pas le temps, mais je pense que je suis très proche de la solution.( je crois déjà l'avoir en tête en écrivant ces lignes)
Bonne chance pour les olympiades.

sosmaths

merci infiniment de me pas m'avoir oublié et de m'apporter bientôt la solution. J'ai un peu laissé tombé le problème pour l'instant tout en attendant de vous lire précisément et avec jubilation la semaine prochaine ;(a lieu actuellement l'épreuve des TPE, du bac blanc français, des olympiades (merci également pour vos mots très gentils !!!), ...)
Très cordialement, ERIC

A bientôt

sos math

Au pire, le même nombre apparaît 40 fois et alors il y aurait 240 - 39 nombres différents pour les 40 dés, ce qui réduirait le majorant à 201 et le rapport de 7800 par 201 est environ de 38,8 donc 39 dés auraient en commun un même nombre. Comment faire mieux ?

Par ailleurs, en revenant à la résolution CAS 1, CAS 2 qui comportait des erreurs, on vient de m'apporter le rectificatif suivant à propos du cas 2 (mais je ne comprends pas tout ) :
Dans le 2ème cas, il y a un numéro du 1er dé qui est commun à au moins 8 dés.
Considérons le sous-ensemble constitué par ces 8 dés (famille 1) , chacun possède 5 nombres qui diffèrent entre eux,
puisque l’intersection de deux dés se réduit à un nombre unique.
On en déduit, que pour constituer les 8 dés, il faut un nombre commun X et 5 x 8 = 40 numéros différents.
Dé1 = 1-2-3-4-5-6 pour fixer les idées (X = 1)
On peut prendre les 40 numéros de 7 à 46.

Considérons les 40 -8 = 32 dés restants.
S’il existe parmi les dés restants, un dé qui n’a pas le nombre X (=1)en commun , ce dé (dé 2) doit avoir en commun un autre numéro du 1er dé, mettons Y (=2 pour fixer les idées). Le dé est alors constitué de Y et de 5 numéros qui diffèrent de ceux du 1er dé.

Les 31 dès restant interceptent ce dernier dé en un singleton.
Ils ne peuvent pas tous l’intercepter en Y car Y n’est présent que pour un seul dé de la famille 1.
Il y a donc un autre numéro que Y du dé 2 commun à d’autres dés et qui diffère de X.

Donc il existe des dés du type dé 3 = Z nombre 1 nombre 2 nombre 3 nombre 4 nombre 5 avec Z=3, 4, 5, 6
Nombre i > 6

Regardons l’intersection du dé 3 avec les 8 dés de la famille 1.
Comme tous les éléments de la famille 1 sont différents à part X , les nombres nombre 1, nombre 2, nombre 3, nombre 4, nombre 5 ne peuvent apparaître au plus que dans 5 dés différents, donc l’intersection du dé 3 avec 8-5-1= 2 dés dès de la famille 1 est vide.
D’où la contradiction.

Donc tous les dés ont un élément commun.
Cordialement, ERIC

Bonjour,
Pourriez-vous me dire,
premièrement, si vous avez une autre solution ( puisque vous étiez sur le point d'aboutir déjà la fois dernière et cela m'intéresserait beaucoup parce que votre exposé de résolution est le seul qui ne laisse aucune zone d'ombre en vous lisant et en vous suivant dans votre démarche ),
deuxièmement, la solution avec le CAS 1 et le CAS 2 est-elle entièrement correcte ?
Merci beaucoup de me permettre de mettre un terme à cet exercice.
Cordialement, Eric

Bonjour

j'ai lu vos deux messages et j'ai essayé de conclure sur mon raisonnement... sans y arriver. Je me suis alors laissé enmmener sur d'autres voies, en essayant de réoudre le problmème avec des dés à 2 faces, à 3 faces( en fait simplifier le problème pour trouver des pistes) mais sans grand succès, j'ai essayé de trouver une piste avec un tableur. Bref, ce n'est pas simple et ça peut encore demander du temps.
Par contre j'ai lu les solutions cas 1, cas2 mais ne les ai pas complètement analysées, ce que je vais faire maintenant.
Une remarque : On ne choisi pas le moment de mettre un terme à un exercice ouvert, à moins d'abandonner la partie.
Et les olympiades, ça c'est passé comment ?

sosmaths

Bon j'ai relu votre raisonnement et il ya des choses qui me semblent très flous, il faudrait les préciser.
La famille F1 est l'ensemble des dés qui ont en commun le nombre 1( pour fixer les idées) avec le dé D1. F1 contient au moins 8 dés (dont D1)
F2 est le famille constituée des dés qui ont commun le nombre 2. F1 et F2 ont un dé en commun, c'est D1.
Je ne comprends pas le raisonnement à partir de :

Les 31 dès restant interceptent ce dernier dé en un singleton.
Ils ne peuvent pas tous l’intercepter en Y car Y n’est présent que pour un seul dé de la famille 1.
Il y a donc un autre numéro que Y du dé 2 commun à d’autres dés et qui diffère de X.

Je serai d'accord, si le nombre 31( qui en fait est au plus 31) était remplacé par 39.

Mais alors ça ne mène pas à grand chose, et je ne comprends pas la suite.
mais je continue à chercher dans cette direction, en rédigeant rigoureusement car c'est essentiel.
sosmaths

ça y est, j'y suis arrivé, ou plutôt j'ai compris le raisonnement exposé dans votre message. IL a fallu faire un peu de ménage, comme vous allez le voir.

PROBLEME DES 40 DES
Les 40 dés sont appellés D1, D2, ...D40

Considérons le dé D1, il a en commun un numéro avec chacun des 39 autres dés, donc au moins un de ses numéros est sur au moins 7 dés parmi ces 39 dés. Donc au moins un numéro du dé D1, apparaît au moins 8 fois en tout.
Pour fixer les idées supposons que D1={1,2,3,4,5,6} et sans nuire à la généralité du problème on peut supposer que 1 fait partie des numéros apparaissant au moins 8 fois sur l'ensemble des 40 dés.

Soit F1 l'ensemble des dés contenant le nombre 1. F1 contient au moins 8 éléments.


Attention : Raisonnement par l'absurde: On suppose que :"F1 ne contient pas les 40 dés."


Alors il existe au moins un dé qui n'est pas dans F1.
Soit D* un dé n'appartenant pas à F1
Soit D*={a1, a2, a3, a4, a5, a6 } avec tous les ai différents de 1.

D* a un numéro commun avec chaque dé de F1. Or il y a 6 numéros sur D* et au moins 8 dés dans la famille F1. Donc d'après le principe des tiroirs, au moins 2 dés de la famille F1, ont le même numéro en commun avec D*. Mais ce n'est pas possible, puisque ces deux dés de la famille ont déjà 1 en commun.

Donc la supposition : « F1 ne contient pas les 40 dés. » est fausse.
Donc F1 contient les 40 dés. Et donc il existe un numéro commun aux 40 dés.

Et voilà, c'était difficile, et en même temps, une fois fini et rédigé, c'est d'une clarté aveuglante.
C'est en tout cas un magnifique problème, qui utilise 2 fois successivement le principe des tiroirs de Dirichlet. J'aimerais bien connaitre l'origine de ce problème( si vous la connaissez), dont je devine beaucoup de prolongement. Ca ressemble à un problème d'olympiade internationale.
bonne lecture
SOSmaths