Enigme Ensemble de 55 éléments ! @ Prise2Tete

Azdod · #1

On considère un ensemble [latex]E[/latex] comprenant [latex]55[/latex] nombres entiers naturels non nuls et qui sont tous inférieurs ou égaux à [latex]100[/latex].
Montrez que E contient deux nombre [latex]n[/latex] et [latex]m[/latex] tels que [latex]m-n=9[/latex].
Bonne chance !

Implicitement ; les nombres sont différents 2 à 2 !

MthS-MlndN · #2

Cette énigme ne marcherait-elle pas avec 51 entiers "seulement" ? Pour moi, le plus grand sous-ensemble de l'ensemble des entiers naturels inférieurs ou égaux (tu peux corriger l'énoncé ) à 100 qui ne respecte pas cette condition est l'ensemble des entiers impairs de 1 à 99 (ou, de manière équivalente, celui des pairs de 2 à 100).

Ah non, au temps pour moi : en gardant les entiers de 1 à 9, puis ceux de 19 à 27, puis ceux de 37 à 45, etc. jusqu'à ceux e 91 à 99, on obtient 54 entiers différents. Donc c'est effectivement à partir de 55 que ça devient impossible.

Pas d'idée de démonstration

L00ping007 · #3

J'arrive à trouver un ensemble de 54 nombres pour lesquels la différence de deux nombres quelconques n'est jamais égale à 9.
Dans E je mets les nombres :
- de 1 à 9
- de 19 à 27
- de 37 à 45
- de 55 à 63
- de 73 à 81
- de 91 à 99
(j'ai 6 groupes de 9 nombres)

Avec cette configuration, je ne peux pas ajouter un 55ème nombre sans qu'il ait une différence de 9 avec un de ceux déjà présents.

Mais je n'arrive pas à montrer facilement que c'est la seule configuration de 54 nombres que je puisse trouver, donc je m'y prends autrement

Soit [latex]F=\{n+9, n \in E\}[/latex]
On a donc évidemment [latex]card(F)=card(E)[/latex], car F est juste l'ensemble des nombres de E auxquels on a ajouté 9.
[TeX]card(E\cap F)=card(E)+card(F)-card(E\cup F)[/TeX]
Or l'élément le plus grand de F vaut 109 au maximum, celui de E vaut 100 au maximum, donc [latex]card(E\cup F) \le 109[/latex]
On en déduite que [latex]card(E\cap F) \ge 55 + 55 - 109 = 1[/latex]

E et F ont donc forcément un élément en commun, appelons-le n.
[TeX]n \in F[/latex] donc [latex] \exists m \in E / n=m+9[/TeX]
On a donc bien trouvé n et m dans E vérifiant n-m=9

clement.boulonne · #4

C'est le principe des tiroirs ! Pas le temps de développer plus !

gwen27 · #5

1 2 3 4 5 6 7 8 9
19 20 21 22 23 24 25 26 27
37 38 39 40 41 42 43 44 45
55 56 57 58 59 60 61 62 63
73 74 75 76 77 78 79 80 81
91 92 93 94 95 96 97 98 99 = 54 nombres pas moyen de faire plus sans une différence de 9.

dhrm77 · #6

Pourquoi 55?
Je trouve que 51 sont suffisant. Par exemple, tous les nombres pair plus un nombre impair quelconque. Le nombre impair est alors l'un des deux nombres n ou m.
corrigé plus bas...

Azdod · #7

@ dhrm77 et MthS-MlndN :
Il existe une combinaison de 54 nombres pour lesquels la différence de deux nombres quelconques n'est jamais égale à 9.

MthS-MlndN · #8

Je sais, je l'ai trouvée (relis mon post). Du coup, il en existe au moins deux.

irmo322 · #9

On peut voir l'ensemble des entiers entre 1 et 100 comme un graphe tel que:
il y a une arête entre deux points i et j ssi |i-j|=9.
En enlevant un point du graphe, on lui retire au maximum 2 arêtes. En en enlevant 45, on retire au graphe un maximum de 90 arêtes.
Or le graphe en contient 91, donc il en reste forcément une.

rivas · #10

Dans n'importe quelle tranche de 18 nombres successifs, on ne peut en prendre qu'au maximum 9 sans qu'un écart ne soit égal à 9. En effet modulo 9, il n'y a que 9 valeurs possibles, une dixième valeur serait forcément égale à l'une des 9 déjà choisies (principe des tiroirs de Dirichlet). Dans une plage de 18 nombres consécutifs, la différence modulo 9 égale à 0 veut dire que la différence des nombres est 9 (les différences vont de -17 à +17).
On peut ensuite choisir effectivement 9 nombres dans chaque plage sans "interférence" d'une plage à l'autre (tous au même endroit dans la plage).
On effectue un recouvrement de [1,100] par 6 plages de 18 nombres consécutifs, la dernière étant tronquée à 10 nombres. Pour chaque plage, on peut choisir 9 nombres et pour la dernière (tronquée), on peut, pour maximiser le nombre de nombres, considérer que les 9 solutions sont dans l'intersection de cette dernière plage avec le segment [1,100]. Il y a donc au plus 54 nombres "indépendants" au vu de la relation m-n=9 dans [1,100].

Si on en prend un 55ème, il est forcément en relation avec l'un des nombres déjà choisis.

On peut effectivement construire un ensemble de 54 nombres indépendants:
[1,9]U[19-27]U[37,45]U[55,63]U[73,81]U[91,99]

Merci pour cette énigme amusante.

Jackv · #11

Penons le problème à l'envers : Peut-on choisir 54 nombres entiers de 1 à 99 tels que aucun d'eux ne soit égal à un autre + 9 ?
Oui, par exemle les 54 nombres classés dans le tableau ci-dessous en 6 rangées de 9 nombres.

1 2 3 4 5 6 7 8 9

19 20 21 22 23 24 25 26 27

37 38 39 40 41 42 43 44 45

55 56 57 58 59 60 61 62 63

73 74 75 76 77 78 79 80 81

91 92 93 94 95 96 97 98 99

L'ajout d'un 55ème nombre dans ce tableau est forcément égal à l'un des précédent + 9.

Azdod · #12

Non c'est à partir de 55 exactement !

dhrm77 · #13

En fait il y a 7 combinaisons de 54 nombres pour lesquels la différence de deux nombres quelconques n'est jamais égale à 9.
La premiere:
1-2-3-4-5-6-7-8-9-19-20-21-22-23-24-25-26-27-37-38-39-40-41-42-43-44-45-55-56-57-58-59-60-61-62-63-73-74-75-76-77-78-79-80-81-91-92-93-94-95-96-97-98-99
La deuxieme:
1-2-3-4-5-6-7-8-9-19-20-21-22-23-24-25-26-27-37-38-39-40-41-42-43-44-45-55-56-57-58-59-60-61-62-63-73-74-75-76-77-78-79-80-81-92-93-94-95-96-97-98-99-100
etc...
Et la derniere:
2-3-4-5-6-7-8-9-10-20-21-22-23-24-25-26-27-28-38-39-40-41-42-43-44-45-46-56-57-58-59-60-61-62-63-64-74-75-76-77-78-79-80-81-82-92-93-94-95-96-97-98-99-100.
J'avais fait une erreur dans ma recherche initiale.
rajouter un nombre quelconque a une de ces suites et il existe forcement deux nombres qui ont une difference de 9 (celui rajouté et un autre).

Nicouj · #14

Je répartis les entiers entre 1 et 18 en 9 couples d'entiers (n, n+9) :
(1 , 10) ; (2 , 11); ... ; (9 , 18)
Je fais pareil pour les 4 paquets de 18 entiers suivants.
Et finalement je fais le couple (91, 100).
J'ai partitionné mes 100 entiers en 46 couples (n, n+9) et 8 singletons

Par le principe des tiroirs, si je tire 55 = 8 + 46 + 1, je vais forcément choisir deux entiers d'un même couple qui auront une différence de 9.

franck9525 · #15

@Nicouj : Ta démo est d'une simplicité brillante, y'a même pas de besoin de connaitre cette histoire de tiroirs.

MthS-MlndN · #16

Ce qui me frustre un peu la-dedans, c'est qu'on ne prouve pas en revanche qu'on peut construire un ensemble de cardinal 54 pour lequel on ne peut pas trouver un couple (n,n+9) -- en considérant le couple (1;10) et le couple (19;28), par exemple, il est clair que prélever un et un seul entier de chaque couple n'est pas un modus operandi satisfaisant.

J'aurais plutôt réparti les nombres par modulo 9 :
(1;10;19;...;100) : 12 éléments
(2;11;20;...;92) : 11 éléments
(3;...;93) : 11 éléments
etc.

On peut choisir au plus 6 éléments dans chacun de ces ensembles pour ne pas avoir de couple de la forme (n;n+9) dans l'ensemble formé, en sautant un élément sur deux (tout simplement), d'où la limite a 54 éléments. Le 55me nous met dedans, et hop.

franck9525 · #17

MthS-MlndN a écrit:
31/01/201 [...] la réponse est l'ensemble des entiers impairs de 1 à 99 (ou, de manière équivalente, celui des pairs de 2 à 100) soit 50. [...] Pas d'idée de démonstration
03/02/2011 et hop.

BRAVO pour le progrès !

MthS-MlndN · #18

Merci beaucoup

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 30-01-2011 23:07:56

Ensemble de 5 éléments !

#0 Pub

#2 - 31-01-2011 11:16:16

Ensemble de 55 élémnets !

#3 - 31-01-2011 11:20:00

Ensemble de 55 ééments !

#4 - 31-01-2011 12:00:46

Ensemble de 55 lééments !

#5 - 31-01-2011 12:40:42

Ensemble de 55 élémnets !

#6 - 31-01-2011 13:20:05

Enssemble de 55 éléments !

#7 - 31-01-2011 13:27:13

Ensmeble de 55 éléments !

#8 - 31-01-2011 13:28:06

Ensemble de 5 éléments !

#9 - 31-01-2011 16:51:28

ensemble se 55 éléments !

#10 - 31-01-2011 19:15:21

ensemvle de 55 éléments !

#11 - 31-01-2011 19:20:36

Ensemble de 55 élément s!

#12 - 31-01-2011 19:40:33

Ensembble de 55 éléments !

#13 - 01-02-2011 01:59:26

Enesmble de 55 éléments !

#14 - 01-02-2011 14:54:53

enszmble de 55 éléments !

#15 - 03-02-2011 09:25:02

Ensemble de 55 éléments

#16 - 03-02-2011 11:56:34

Ensemble de 55 éléments

#17 - 03-02-2011 12:27:20

Ensemle de 55 éléments !

MthS-MlndN a écrit:

#18 - 03-02-2011 13:01:28

Ensemble de 55 élément !

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums