exercice d'olympiades

[invited8d9e610]

Bonjour a tous
Il y a un exercice d'olympiades que j'ai pu solutionner rapidement mais sans être sur
Et je veux aussi voir les différents raisonnements et logiques pour le faire
Voila l'enoce :
Martin a voulu constituer des nombres 1,2,3,4,5,........,2016 , une liste en sorte qu'il n y a pas deux
Nombres la différence entre eux est égale a 17, par exemple, si Martin décide de choisir dans sa
Liste le nombre 1880 ,il ne peut donc ni choisir 1863 ni 1897
Combien y a t il de nombres dans la liste la plus longue que Martin peux constituer ?

Et bien voilà je n'ai pas pris beaucoup de temps pour raisonner
J'ai juste trier les nombres et avec des petits calcul basic j'ai trouver que la liste la plus longue
Contient 1013 nombres mais c'est juste que je ne suis pas sur
Ce que je demande c'est une confirmer ainsi que la méthode que vous avez utilisé
Car je doute qu'il y ait une seul méthode et les raisonnement sont nombreux
J'aimerais donc avoir un appercu de comment des personnes intelligentes et matheuses
Aurait solutionner ce problème
Merci d'avance
PS : je n'ai pas donner de détails sur mon raisonnement pour ne pas influencer lz votre mais si
Vous y tenez je vous le posterais après
Encore merci
-----

[invite3498e9a5]

A priori, je ferai de la manière suivante

Une première manière est de découper l'intervalle fourni (1 .. 2016) en sous ensemble de 17 de long, et de ne pas mettre deux intervalles successifs dans la liste finale. Pour cela on prend les intervalles de rang impair.

On trouve qu'il y a 118 intervalles de 17 de long et il reste 10 nombres, on peut en choisir la moitié, soit 59 (le 1er, 3eme, ... 2n+1 ème).
Donc au total on obtient (17 * 59) + 10 nombres soit 1013 comme tu as semble-t-il trouvé.
On vérifie mentalement que le dernier intervalle n'est pas juste antérieur au reste de la division précédente (ici c'est bien le cas, le dernier intervalle est le 118 eme, donc de rang pair, et comme on ne prend que les impairs, ça colle) sinon on prendrait les intervalles de rang pair.

[invited8d9e610]

Bonjour Fregoli
Et bien je vois que tu as exactement au détail près que tu as fais exactement comme moi
Meec pour la réponse aussi rapide
Ceci dit je voudrais voir d'autres logique

[zenxbear]

vous êtes sur qu'on peut prendre la totalité des 10 points restants? Je pense que si vous alterner les intervalles à coup de pack de 17, les derniers 10 vont être distants de 17 de l'intervalle précédent.
Je pense que la réponse est plus grande que 17x59=1003, mais inférieure à 1013. Je pense que c'est 1008, si on alterne les nombres.

[A voir en vidéo sur Futura]

[invite75a796c1]

Salut

je trouve au moins 1013 aussi , en distinguant 2 cas par symétrie : l'intérieur et les bords

A l'interieur : alterner 118 bandes de 17. Comme 118 est pair ( alternance ), il y a 17 interdits avant l'intérieur et 0 interdits après.
Ajustons le début de l'intérieur avec le début de la bande pour se passer des 17 premiers interdits et pour prendre tout le reste à la fin, soit 10. Donc 118*17/2 + 10 , soit 1013

A partir de là, faut trouver l'astuce qui permettrait d'en prendre plus puisque c'est un exo d'olympiade et que là, c'était encore du niveau du CM2. Mais je peux me tromper. Pour l'instant, je ne vois pas à moins que l'imparité de 118/2 y soit pour quelque chose , faut voir ...

Démontrer que 1013 est le maximum est une autre paire de manches. Il y a peut être une astuce pour éviter 2 sous démos minutieuses ...

[invite3498e9a5]

vous êtes sur qu'on peut prendre la totalité des 10 points restants? Je pense que si vous alterner les intervalles à coup de pack de 17, les derniers 10 vont être distants de 17 de l'intervalle précédent.

oui car le nombre d'intervalles est pair, or on ne prends que les intervalles de rang impair, donc le dernier intervalle pris (le 59eme de rang impair) est suivi par le 59eme de rang pair (soit le 118 eme au total) qui n'est pas pris, donc le 1er nombre des 10 restant se situe à 18 du dernier pris.

Par contre comment démontrer qu'il n'y a pas de solution plus efficace, c'est toute la question.

[invite3498e9a5]

. Je pense que c'est 1008, si on alterne les nombres.

Si on remarque que chaque nombre x choisi élimine un autre nombre (celui égal à x+17), on peut dire que le nombre est supérieur ou égal à N / 2 soit 2016 / 2 soit encore 1008.

1008 est donc un minimum.

En réalité le nombre est supérieur à 1008 car les derniers nombres choisis n'élimineront pas d'autre nombre, le décalage de 17 générant un nombre plus grand que 2016.

[invite3498e9a5]

un petit début de brouillon de projet de raisonnement.


Supposons que j'ai la liste de N nombres tels que définis, pour l'ensemble 1 .. 2016.

Pour mon ensemble N, soit 2016 en fait partie, soit pas.

H1: j'ai 2016, alors 1999 n'y figure pas et je reste à N. donc de 1 à 2015 je n'ai que N-1 nombres.
H2: je n'ai pas 2016, et donc j'ai 1998, sinon je pourrai y ajouter 2016 et j'aurai donc N+1 nombres dans mon ensemble, ce qui est en contradiction avec les hypothèses.

donc de 1 à 2015, j'ai exactement N-1 nombres.

Soit 2015 en fait partie, soit pas.

... en raisonnant de la même manière, je vais arriver à la conclusion que 1998 ne fait pas partie de l'ensemble, et donc que H2 est fausse.

en continuant ainsi, on va éliminer tous les nombres de 1999 à 1973 et construire les paquets de 17 nombres qui aboutissent au calcul précédent.

[zenxbear]

ok, j'avais fait un dessin avec un nombre impair d'intervalles de 17 éléments consécutifs, d'ou l'erreur.

Pour le max. Si vous isolez 34 éléments consécutifs entre 1 et 2016 du reste, vous ne pourrez pas choisir parmi cette liste, 18 éléments tel que la difference entre eux ne fasse pas 17. Ceci est logique, vient du principe des tiroirs car il y a 17 classes modulo 17.
Du coup si je partage les elements entre 1 et 2016 par intervalles de 34, et considère chaque intervalle séparément. 2016= 59 x 34 +10. Je peux choisir au maximum 17 pour les 59 intervalles de 34, et pour le dernier intervalle de 10, je prends la situation la plus favorable (pouvoir choisir tous les 10 éléments). J'obtiens un max de 59 x 17 + 10 =1013

[invited8d9e610]

Et bien a priori j'étais juste
Et voilà comment j'ai raisonné
Je mis dans une ligne les nombres de 1 a 17
Et sous cette lgne une autre ligne de 18a 35
J'ai trouvé que 2016/17 me donner 118 lignes de 17 nombres et une autre de 10 nombres
Et là comme j'ai vue que dans chaque 2lignes il y avait une qui partez et donc
118/2 *17 +10 =2013
Merci a tous pour votre attention
A bientot