Commentaire sur l'article

• Décembre 2015, 2e défi

  le 11 décembre 2015 à 08:18, par ROUX

  1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 = 40.
  40 est un multiple de 5.
  Si je dois en extraire sept dont la somme etc. c’est que je dois en soustraire un à 40 pour que le résultat soit encore un multiple de 5...
  Bah alors je réponds volontiers : « Non... » à la question.

  Répondre à ce message
• Décembre 2015, 2e défi

  le 11 décembre 2015 à 08:23, par zgreudz

  Zut ! trop tard...Bravo !
  Cordialement
  Z.

  Répondre à ce message

• Décembre 2015, 2e défi

  le 11 décembre 2015 à 08:48, par mesmaker

  Comme il faut choisir 7 nombres distincts parmi huit cela ne fait que huit possibilités : 39, 38, ..., 31 mais sans le 35 car 5 ne fait pas partie des huit nombres. Donc c’est impossible. Je ne répète que ce qu’à déjà bien montré ROUX en pointant le fait que la méthode brute de tout calculer est la seule possible et ne prend qu’une à deux minutes. Sans vouloir être méchant où est le défi intellectuel ? J’ai l’impression que depuis début décembre, avec l’énigme des cercles, les énigmes deviennent plus (trop) simple. Non ? Je souhaite que cela ne soit qu’un biais statistique qui fasse que deux énigmes faciles se suivent. J’attends la prochaine avec impatience pour me triturer le cerveau un peu plus longtemps :)

  Répondre à ce message
• Décembre 2015, 2e défi

  le 11 décembre 2015 à 16:26, par Christophe Boilley

  On peut toujours chercher à transformer un défi en un autre. Étant donné un ensemble de 5 nombres entiers, peut-on toujours obtenir un multiple de 5 en additionnant les éléments d’une partie non vide de cet ensemble ? Et plus généralement en remplaçant le nombre 5 par un entier naturel non nul quelconque ?

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 00:18, par mesmaker

  J’ai la critique facile mais je reconnaît bien volontiers qu’il n’est pas facile de toujours trouver des énigmes qui soit intéressantes sans être ni trop dur ni trop facile, et mieux qui peuvent être résolues de diverse manières, brutes ou élégantes.
  Concernant le faite de faire des variations sur un problème je suis à cent pour cent d’accord avec vous. Dans votre énoncé, quand vous dîtes ’Étant donné un ensemble de 5 nombres entiers,’, ce peut être n’importe quel nombres positifs de 0 à l’infini ou juste les nombres entre 0 et 10 et de plus peut il y avoir des répétitions ? Dans tous les cas je serai tenter de dire oui car soit un des nombres est un multiple de cinq et l’affaire est réglée ; soit aucun n’est un multiple de cinq. Dans ce cas en utilisant les congruences, on peut réécrire c’est cinq chiffres en fonction de leur congruence modulo 5 ce qui donnera cinq chiffres de 1 à 4 et donc il existe forcément une partie dont la somme vaut cinq.
  Par exemple si je prend les cas (24, 38, 36, 198, 47). Cela donne (4, 3, 1, 3, 2) modulo 5.
  En prenant 4+1 c’est à dire 24+36 = 60 on trouve un multiple de cinq.
  Une exemple extrême serait (6, 66, 26, 31, 41) = (1, 1, 1, 1, 1) modulo 5. Donc il faut tout additionner : 6+66+26+31+41 = 170
  Le fait d’enlever 5 dans les nombres possible ne généralise pas mais diminue les possibilités. Non ? Et puis pourquoi 5 et pas tous les multiples de 5 ?

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 09:26, par Christophe Boilley

  Comme vous l’avez remarqué, les congruences permettent de ramener le problème avec un ensemble (donc sans répétition) de 5 entiers à une liste (avec éventuelles répétitions) d’entiers entre 0 et 4.

  L’étape décisive est votre proposition « cinq chiffres de 1 à 4 et donc il existe forcément une partie dont la somme vaut cinq ». C’est tout sauf évident. Vous traitez deux exemples, ce qui ne démontre pas tous les cas possibles.

  Votre premier exemple se généralise pour valider tous les cas où sont présentes deux valeurs complémentaires (comme 1 et 4). Votre deuxième exemple s’étend à toutes les listes de cinq entiers congrus entre eux modulo 5. C’est déjà ça.

  Il reste à décrire les cas restants et vérifier qu’ils satisfont encore la propriété annoncée. Cela devrait permettre de se rendre compte que l’extension de la propriété requiert une autre approche pour remplacer ensuite 5 par 1000.

  Répondre à ce message

• Décembre 2015, 2e défi

  le 12 décembre 2015 à 09:46, par Daniate

  Bonjour, quelques précisions me semblent nécessaires. Par définition, un ensemble ne contient que des éléments différents 2 à 2, donc les répétitions sont impossibles. Ensuite une somme contient au moins deux termes, donc les multiples de 5 sont parfaitement admis. L’ensemble suivant ne contient aucune somme multiple de 5 : 1, 5, 6, 11, 16 tous congru à 1 sauf un congru à 0. On peut remplacer 1 par 2, 3 ou 4 et généraliser la construction aux autres entiers que 5.

  Pour le défi initial il existe quand même un raisonnement plus élégant que le calcul des 8 sommes possibles.

  La somme des 8 nombres étant multiple de 5 (40), si on pouvait exhiber une somme de 7 nombres également multiple de 5 alors par différence le 8ème nombre serait aussi multiple de 5.

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 09:56, par Christophe Boilley

  Il n’y a pas de répétitions dans un ensemble, mais en utilisant les congruences, on peut simuler la liste (1, 1, 1, 1, 1) avec l’ensemble $\{1, 6, 11, 16, 21\}$.

  Une somme est calculée à partir d’une liste de valeurs qui peut ne contenir qu’un terme voire aucun. Elle est définie par récurrence au moyen de l’addition (qui est bien une opération binaire) mais avec une initialisation sans addition.

  Répondre à ce message

• Décembre 2015, 2e défi

  le 12 décembre 2015 à 10:44, par mesmaker

  Notre discussion est la preuve qu’il n’est pas trivial de bien penser et formuler une énigme mathématique. Je suis d’accord avec tout ce que vous avez dit Daniate et Christophe. Mathématiquement lorsque l’on dit ensemble, la répétition est inutile. Ces deux ensembles 2, 3, 4 et 2, 3, 2, 4 sont les mêmes. Cependant Christophe voulait peut être parler de quintuplet de nombre, c’est à dire 5 nombres tirés aux hasard parmi les entiers naturels, donc les répétitions peuvent exister. Ensuite, Daniate votre contre-exemple 1, 5, 6, 11, 16, est juste si comme vous le dîtes il faut faire ABSOLUMENT une somme et donc avoir au moins deux termes parmi les cinq. Mais bien que cette discussion soit primordiale pour bien définir le problème, tout cela relève plus de la bonne définition des termes que de réflexions mathématiques.

  Je voudrais donc répondre à Christophe sur ma phrase « cinq chiffres de 1 à 4 et donc il existe forcément une partie dont la somme vaut cinq ». Je l’admets par fainéantise hier soir, je ne l’ai pas prouvé mais j’y avais réfléchi et étais venu à cette conclusion. Voilà aujourd’hui la preuve après un bonne réflexion de 5-10 minutes que pour un quintuplet de cinq chiffres allant de 1 à 4, il est toujours possible d’en extraire un sous n-plet dont la somme est un multiple de 5.

  Je vais chercher pour cela un quintuplet qui ne convient pas et montrer qu’il n’en existe pas.
  Je note que les quintuplets qui ont cinq fois le même chiffres, n, peuvent fournir un multiple de 5 en faisant la somme des cinq car 5*n est par définition un multiple de 5.
  De même si un quintuplet à au moins trois chiffres différents sur les quatre possibles alors on peut former une pair (1,4) ou (2,3) donc la somme vaut 5. Donc les seules possibilités de quintuplet n’ayant pas de n-uplet dont la somme vaut 5 doivent être cherchés parmi les quintuplets n’ayant que deux chiffres différents du type (1,2,2,1,1) ou (3,4,3,4,3). Evidemment (3,2,3,2,2) ou (1,4,4,1,1) ne marche pas car on peux faire la somme 1+4 = 2+3 = 5. Mais dans ce cas et comme l’ordre dans les quintuplet ne compte pas dans ce problème alors il n’y a que quatre cas (1,1,2,2,2), (2,2,2,1,1), (3,3,3,4,4), (3,3,4,4,4). Dans chacun de ces quatre cas on peut trouver un n-uplet donnant un multiple de 5 : 2+2+1 = 5 ou 3+3+4 = 10. CQFD.

  Merci Doniate pour la résolution élégante du défi d’aujourd’hui et merci Christophe pour m’avoir poussé à résoudre cette dernière partie qui n’était pas si simple que cela. Bon week-end et à la semaine prochaine pour le prochain défi.

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 11:35, par Christophe Boilley

  Le raisonnement avance, mais il manque des cas. On peut mettre ensemble 1 et 3 ou 2 et 4. On peut aussi avoir quatre fois une valeur et une fois une autre valeur. Cela fait douze cas de plus à tester.

  L’intérêt de cette énigme, comme dans le défi initial, est la réduction combinatoire du problème. Comme l’avait compris ROUX, extraire sept nombres d’un ensemble de huit nombres revient à choisir un nombre parmi huit, ce qui laisse huit possibilités rapidement traitées.

  En revanche, choisir un quintuplet d’entiers entre 0 et 4, même en se restreignant aux listes croissantes, mène à traiter (5 parmi 9) = 126 cas. La présence de 0 concerne (4 parmi 8) = 70 d’entre eux. On évacue quatre listes constantes supplémentaires. Le dénombrement de listes croissantes sans 0 mais avec complémentaires est plus fastidieux : (3 parmi 6) = 20 avec 1 et 4, autant avec 2 et 3, mais 4 d’entre elles ont les quatre nombres 1, 2, 3, 4.

  Les exemples précédents permettaient donc de traiter 70 + 4 + (20*2 - 4) = 110 cas de façon générique. Il restait 16 cas à traiter individuellement (les quatre que vous aviez trouvés et les douze que je vous signale). C’est tout à fait faisable, mais il faut d’une part les traiter, d’autre part vérifier qu’on n’en a pas oublié.

  L’étape suivante serait de remplacer 5 par un autre nombre premier.

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 12:37, par Daniate

  Bonjour,

  En posant le problème de trouver 5 entiers égaux ou non, mais aucun divisible par 5, tels que toute somme partielle ou non ne soit divisible par 5 (ce qui correspond à l’idée du défi modifié) il est possible de démontrer l’impossibilité.
  Je commence par remplacer les 5 nombres par leurs congruences modulo 5 puis je les range dans l’ordre croissant.
  Les congruences ne peuvent pas toutes être égales, puisque la somme des 5 serait divisible par 5.
  De plus une congruence interdit une autre 1—4, 2—3

  Si la liste commence par 1 le suivant peut être 1,2 ou 3. Derrière 2 on ne peut mettre ni 1 (trop petit) ni 2 (1+2+2=5) ni 3 (2+3=5) ni 4 (à cause du 1). Derrière 3 on ne peut mettre que 3 et à l’étape suivante on aura 1+3+3+3=10 donc la suite commence par 1, 1 qui ne peut se poursuivre que par 1 ( 2 et 3 sont des impasses qui restent jusqu’au bout) mais la suite ne peut pas ne contenir que des 1
  Si la suite commence par 2 elle continue par 2 ou 4 mais derrière 4 ne peut venir que 4 or 2+4+4=10 on a 2, 2, 2, 2 forcé et alors ni 2 (tous égaux) ni 4 (2+2+2+4=10)
  Si la suite commence par 3 vient 3 ou 4 , derrière 3 ne reste que 3 (à cause de 3+3+4=10) etc . Après 4 ne peuvent venir que des 4 or 3+4+4+4=15
  La suite ne peut pas commencer par 4 (voir ci dessus)
  Donc la liste ne peut pas exister.
  En fait tout ce bavardage n’est là que pour décrire un arbre

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 14:28, par Christophe Boilley

  Bien tenté, mais il y a un écueil à « 2 et 3 sont des impasses qui restent jusqu’au bout ». En effet, l’impasse avec 2 n’est justifiée que si on peut mettre un terme après. L’impasse en 3 n’est justifiée que si on peut mettre deux termes après. Il faut donc traiter à part les suites (1, 1, 1, 1, 2) , (1, 1, 1, 1, 3), (1, 1, 1, 3, 3).

  La même erreur se produit en commençant par 2 : il faut traiter (2, 2, 2, 2, 4). Et en commençant par 3, il faut traiter (3, 3, 3, 3, 4).

  Bref, oui, on y arrive, mais vous voyez bien que tout le problème de cette méthode est la vérification qu’on n’a pas oublié de cas.

  Vous parlez d’un arbre. L’avez-vous réalisé ? En arrêtant une branche dès que l’on peut obtenir un multiple de 5, je trouve 35 feuilles.

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 20:28, par Daniate

  Après (1,1, ...) on ne peux plus mettre de 3 (1+1+3=5) ni de 4 (1+4=5). Si on met 2 il faudra continuer par 2 jusqu’au bout mais alors au deuxième on aura 1+2+2=5.

  En fait, j’ai fait 4 arbres commençant par 1 , 2 3 ou 4. Je considère une branche achevée lorsque aucun nombre ne peut être placé à la suite.

  1-1-1-1
  1-1-2
  1-2
  2-2-2-2
  2-2-4
  2-4
  3-3-3-3
  3-4-4
  4-4-4-4

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 21:03, par Christophe Boilley

  Il manque (1, 3, 3)

  Répondre à ce message
• Décembre 2015, 2e défi

  le 12 décembre 2015 à 22:55, par Daniate

  Toutes mes excuses pour cet oubli et merci pour la correction.

  Répondre à ce message

• Décembre 2015, 2e défi

  le 13 décembre 2015 à 09:36, par mesmaker

  Suis je bête, en effet, il manque des cas qui bien évidemment permettent tous de faire un multiple de cinq. Merci pour la correction.

  J’ai réfléchi rapidement à une extension du problème pour d’autres nombres premiers comme vous le mentionniez. Par exemple pour p=11, il faudrait tester que tous les 11-uplet n’ayant que des chiffres de 1 à 10 puissent renfermer un n-uplet tel que sa somme soit un multiple de 11. Par exemple pour (1, 8, 2, 4, 4, 8, 6, 2, 4, 6, 8), on peut prendre (8, 1, 2) dont la somme vaut 11 ou (8, 8, 6) avec 22. En reprenant les arguments de ma précédente démonstration pour trouver un contre exemple qui n’existe pas, je peux dire que le 11-uplet ne doivent pas contenir plus de 5 chiffres différents sinon on est sûr de créer un multiple de 11, et ne doit pas non plus contenir 11 fois le même chiffre. Mais après s’il faut faire un travail de combinatoire pour tous les cas entre avoir 2 et 5, cela devient trop fastidieux pour moi. A moins qu’il y ait une façon rapide et maligne que je n’ai pas vu de démontrer que l’on peut toujours avoir un multiple de 11, je laisse ce problème de côté. Question finale pourquoi un nombre premier ? Cela ne marche pas avec les nombres composés ?

  Répondre à ce message
• Décembre 2015, 2e défi

  le 13 décembre 2015 à 10:12, par Christophe Boilley

  J’espérais pouvoir montrer directement que le produit de toutes les sommes partielles non vides sur p entiers est nul modulo p, pour un entier premier p quelconque. Cette approche n’a pas abouti.

  Cependant, je m’étais rendu compte que la démonstration pour les entiers premiers permettrait une extension à n’importe quel entier srtictement positif par récurrence forte. En effet, si n est un entier composé et que la propriété est vraie pour tout entier strictement inférieur à n (et pour tout premier), et si (x_1, ..., x_n) est une famille d’entiers, on écrit n = mp avec p premier et on décompose la famille en p sous-familles consécutives de m termes. Par hypothèse de récurrence, on peut donc extraire p sommes disjointes qui soient des multiples de m, que l’on note (m y_1, ... , m y_p). Or on peut extraire une sous-famille de (y_1, ... , y_p) qui donne une somme multiple de p, donc la somme correspondante des (m y_i) donne un multiple de n = mp.

  C’est hier soir que j’ai trouvé une démonstration de la propriété pour les entiers premiers. Si aucun x_i n’est multiple de p, on montre par récurrence que l’ensemble S_k des résidus modulo p des sommes partielles réalisables sur (x_1, ... , x_k) contient au moins k éléments pour tout k entre 1 et p. En effet, la suite finie (S_k) est croissante par inclusion et si S_k = S_(k+1), cela signifie que pour tout a dans S_k, le résidu modulo p de a+x_(k+1) appartient aussi à S_k. Or les seules parties de Z/pZ stable par ajout d’un élément non nul sont le vide et Z/pZ. Donc on trouverait Card(S_k) = p et la suite est stationnaire. Donc en particulier il existe une somme congrue à 0 modulo p.

  CQFD

  Répondre à ce message
• Décembre 2015, 2e défi

  le 14 décembre 2015 à 15:06, par Daniate

  Remarquable démonstration, avec historique du raisonnement. J’ai eu quelques difficultés avec les « sommes disjointes », devenues pour moi, et sans raison, sommes différentes. De mon côté, j’étais parti dans une voie différente qui, vraisemblablement n’aboutira jamais. Bravo encore.

  Répondre à ce message

• Décembre 2015, 2e défi

  le 17 décembre 2015 à 21:46, par Idéophage

  Bonsoir,

  On peut essayer de trouver deux sous-familles des $x_i$, l’une incluse dans l’autre, et de même somme. En prenant leur différence, on trouvera $0$. Par exemple, posons $s_i = x_1 + \cdots + x_i$. Soit un $s_i$ vaut $0$, soit il y a un doublon $s_i = s_j$ avec $j > i$. Dans ce dernier cas, on prend $s_j - s_i = x_i + x_{i+1} + \cdots + x_j = 0$.

  Concernant votre preuve pour $n$ premier, cela se généralise à lorsque $n$ n’est pas premier (pas besoin de récurrence). (Personnellement, je vois cela de manière algorithmique.) On regarde toutes les sommes que l’on peut faire, en ajoutant un à un les éléments. Si on retombe sur le même ensemble à un moment, c’est que l’on est sur une sous-partie stable par addition d’un certain $x_i$, et cette partie contient $x_i$, donc également $0$.

  Personnellement je préfère votre preuve…

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 07:01, par Christophe Boilley

  Votre première démonstration est bien plus élégante que la mienne, par application du principe des tiroirs aux sommes s_i pour i variant de 0 à n.

  Je suis moins convaincu par votre deuxième remarque. Qu’est-ce qui empêche par exemple d’avoir un ensemble de sommes de la forme $S_k = \{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13\}$ dans Z/14Z et de vouloir ajouter 7 ?

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 13:10, par Idéophage

  Dans ce cas on ajoute simplement 7 à l’ensemble. Si on stagne à un moment donné en ajoutant x ≠ 0, cela veut dire que x est dans l’ensemble, mais aussi 2x, 3x, etc. jusqu’à 0. Si on ne stagne jamais, alors on a n éléments à la fin, donc en particulier 0.

  Au passage, votre solution utilise aussi le principe des tiroirs : si l’ensemble ne contient pas 0 à la fin, alors on a ajouté au plus n-1 éléments en n étapes, donc il y a au moins une étape où on a ajouté 0 élément. D’ailleurs, le voyez-vous : le principe des tiroirs est une application de la méthode probabiliste ?

  Concernant la « beauté » des solutions, je parlais de votre solution sans la récurrence… enfin, je ne saurais pas trop justifier ma préférence. Je vois votre solution un peu comme les « just-do-it proof », comme le dit Tim Gowers (voir https://www.dpmms.cam.ac.uk/ wtg10/justdoit.html ou https://gowers.wordpress.com/2008/08/16/just-do-it-proofs/). Je trouve votre méthode plus générale : on construit progressivement quelque chose, en essayant de respecter certaines contraintes (ne pas contenir 0) à chaque pas… Cela me fait penser au problème suivant : de combien de couleurs au maximum peut-on colorier le plan de telle sorte que chaque droite soit bicolore (au plus) ? La solution que j’ai est similaire. (on peut généraliser à des sous-espaces n-dimensionnels qui sont n-coloriés, dans un espace k dimensionnel sur un corps quelconque)

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 21:46, par Christophe Boilley

  Vous écrivez « Si on stagne à un moment donné en ajoutant x ≠ 0, cela veut dire que x est dans l’ensemble ». Je ne vois pas pourquoi.

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 22:35, par Idéophage

  À moins que j’aie mal compris (mais je ne vois pas d’autre manière de comprendre l’énigme), si on ajoute x comme nombre possible (à une étape donnée), on va ajouter en particulier la somme contenant un seul terme : x. (comme ça commence à être serré, je pense qu’il serait mieux de continuer en dessous)

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 22:56, par Christophe Boilley

  OK. Ça marche effectivement.

  Répondre à ce message

• Décembre 2015, 2e défi

  le 18 décembre 2015 à 13:20, par Idéophage

  Je continue ici car la marge commence à être petite.

  Voici où j’avais trouvé le problème que je mentionne à la fin : http://www.mathoman.com/index.php/1614-colorer-des-points-dans-l-espace (je ne crois pas que ma solution soit mentionnée dans les commentaires).

  Je vois que j’ai écrit $x_i + x_{i+1} + \cdots + x_j$ au lieu de $x_{i+1} + \cdots + x_j$ au passage, dans mon premier commentaire sur cette page.

  Et j’ai mal répondu à votre question : rien n’empêche $S_k$ d’être de cette forme. Par contre, si $S_k$ est de cette forme, c’est qu’il reste au moins deux éléments à ajouter (donc déjà 7, et encore un autre qui va produire 0).

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 19:03, par Idéophage

  Je voulais dire « ncoloriés » au lieu de « n-coloriés » (il y a au plus n+1 couleur apparaissant dans tout sous-espace de dimension n).

  Répondre à ce message
• Décembre 2015, 2e défi

  le 18 décembre 2015 à 19:06, par Idéophage

  Erreur de formatage, j’ignore pourquoi mon texte a été interprété différemment que ce que je voulais… « (n+1)-colorié » au lieu de « n-colorié ». Si j’omets les parenthèses autour de « n+1 » cela donne « ncolorié ». Étrange… en entourant un caractère de + à gauche et - à droite il n’apparaît pas dans le rendu final…

  Répondre à ce message