Nombres "remarquables"

[Ben314]

Salut,
Une petite énigme sans doute déjà connue par certains d'entre vous...

Pour tout , on note le cardinal de la plus grande (au sens du cardinal) partie telle qu'aucun élément de ne soit le double d'un autre élément de .
On dit que est remarquable lorsque .

Combien y-a-t-il d'entiers remarquables entre 1 (inclus) et (exclu) ?

[Ellyana]

Euh... Je crains que cette énigme ne soit pas pour moi, ceci dit, j'aimerais au moins comprendre l'énoncé O_o
N*, ça veut dire quoi ? Je sais que N c'est l'ensemble des nombres naturels, que R+ l'ensemble des réels positifs, mais N*...
Un cardinal, c'est quoi ?
Aucun élément de A n'est le double d'un autre élément de A. Donc dans l'ensemble A, il ne peut y avoir à la fois 1 et 2 ? 3 et 6 ? etc... ?
Si c'est vraiment trop compliqué à expliquer, ce n'est pas grave, sinon, j'aimerais bien comprendre :D

[Ben314]

Non, comprendre l'énoncé, c'est facile (par contre, pour trouver la réponse, c'est... un peu plus dur... :lol3: )

- Concernant N*, c'est simplement l'ensemble des entiers naturels non nul (c'est ça que l'étoile veut dire).

- Le "cardinal" d'un ensemble, c'est le mot un peu technique qu'on emploie en math pour parler du nombre d'élément de l'ensemble. : Ca fait nettement plus pro. de dire que "le cardinal de l'ensemble des élèves de la classe est 38" plutôt que de dire comme tout le monde "y'a 38 élèves dans la classe" (là, je déconne... :zen:)

- Enfin, pour des (trés) petites valeurs de n, c'est assez facile de trouver "à la main" combien vaut d(n).
Par exemple, pour n=4, on veut trouver la plus "grosse" partie de {1,2,3,4} qui, lorsqu'elle contient un élément donné, ne contient pas le double de cet élément. On peut par exemple prendre les 3 entiers 1,3,4 mais il est clair qu'on ne peut pas prendre les 4 entiers 1,2,3,4.
Donc d(4)=3 et, comme 3 est strictement plus grand que , l'entier 4 est "remarquable".
Pour n=6, on part de {1,2,3,4,5,6} et, on peut prendre comme partie A les 4 nombres 1,3,4,5 (ou bien 1,4,5,6), qui ne contiennent aucune paire k 2k. Par contre, si on prend 5 nombres parmi les 6, on est sûr d'avoir pris un nombre et son double (vérifie...) donc d(6)=4 et, comme 4 n'est pas strictement plus grand que , l'entier 6 n'est pas "remarquable".

[Waax22951]

Bonjour,
La solution est-elle accessible à un niveau de terminale en sachant que je connais les bases de la théorie des ensembles et du dénombrement ? :hein:
(En tout cas j'aime beaucoup le principe..!)

[Ellyana]

Merci beaucoup, Ben ^^
Tout de suite, c'est plus compréhensible.

Pour n=6, on part de {1,2,3,4,5,6} et, on peut prendre comme partie A les 4 nombres 1,3,4,5 (ou bien 1,4,5,6), qui ne contiennent aucune paire k 2k. Par contre, si on prend 5 nombres parmi les 6, on est sûr d'avoir pris un nombre et son double (vérifie...)

C'est simple. On part de {1,4,5,6}. Si on y rajoute un nombre, ca veut dire qu'on rajoute soit 2 soit 3. Or, si on rajoute 2, il y a double-problème (1 et 4), et si on rajoute 3, il y a problème (6). Donc si on prend 5 nombres parmi les 6, y'a problème. Voilà ^^

[Ben314]

Pour résoudre entièrement le problème, il faut "un peu plus" que ça : un truc pas bien compliqué, mais qui n'est pas vu au Lycée à ma connaissance (je ne dit pas quoi pour garder le "sel" de l'énigme).

Sans ce "plus", on peut quand même répondre à des question un peu plus simple concernant d(n).
Je me suis inspiré d'un très vieux post. du forum "énigme" où, à la base, il fallait répondre à la question suivante :

Existe-t-il une partie A de l'ensemble {1,2,3,...,3000} contenant 2000 éléments et telle qu'aucun élément de A ne soit le double d'un autre élément de A ?

(i.e. est-ce que d(3000)>=2000 ?)

Pour répondre à cette question là, un bagage type Lycée est largement suffisant (ce qui ne veut pas dire que la réponse est simple, mais que les outils à utiliser sont simples... :zen:)

[Ben314]

C'est simple. On part de {1,4,5,6}. Si on y rajoute un nombre, ca veut dire qu'on rajoute soit 2 soit 3. Or, si on rajoute 2, il y a double-problème (1 et 4), et si on rajoute 3, il y a problème (6). Donc si on prend 5 nombres parmi les 6, y'a problème. Voilà ^^

Au niveau théorique, le raisonnement n'est pas complètement valable vu que les parties à 5 éléments de {1,2,3,4,5,6} ne sont pas toutes obtenues en rajoutant un élément à l'ensemble {1,4,5,6}.
Mais bon, on a vite fait le tour de toutes les parties à 5 élément de {1,2,3,4,5,6} et on constate qu'aucune d'entre elle ne marche...

[beagle]

alors on prend tous les nombres impairs, c'est déjà ça de gagné.
ensuite on bosse la périodicité des doubles sélectionnables
pas les doubles d'impairs bien sur,
on prend les doubles de pairs,
sauf qu'il ne faudra ensuite pas prendre leurs doubles,
faut voir quelle périodicité ce truc ramène
pour compter combien il y en a de 1 à n.

cela doit ètre une suite on prend les x4 moins ceci, puis moins cela puis moins cela .
c'est sweet sweet sweet.

PS: c'est ça ou Thalès, vu que depuis le message avec imod je réponds par Thalès à tous les problèmes...mais pour le moment je ne vois pas bien avec Thalès.

[Waax22951]

Très bien, je vais y réfléchir mais pense que cela pourra plaire à mon prof de spé si il ne connait pas déjà l'énigme..!
Puisque je ne trouverai pas la solution du problème posé, pourrais-tu me dire par message privé ce qu'est ce fameux "plus", s'il n'est pas trop long à expliquer ? (Je comprendrais que tu aurais autre chose à faire que d'expliquer une notion avec un long texte..!)
Bonne soirée !

[Ben314]

Concernant le "plus" qu'il faut pour l'énigme de départ (et que peut-être certains lycéens connaissent plus ou moins : ce n'est pas du tout du "gros bulldozer"), je la donnerais à qui la veut (par m.p.) MAIS... uniquement après que la "plus simple" ait été résolue vu qu'on en a pas besoin pour celle là.... :zen:

[Doraki]

est-ce que c'est ?
j'ai pas encore de preuve complète mais ça a l'air assez surprenant comme problème.

[beagle]

plus modestement que doraki,
dans le :"on prend quoi?"
Les impairs + 4x les impairs + 16x les impairs + ... ?

[Ben314]

est-ce que c'est ?

non

dans le :"on prend quoi?"
Les impairs + 4x les impairs + 16x les impairs + ... ?

oui.

[beagle]

ainsi donc si c'était, on prend:
1x les impairs
4x les impairs
4x4 les impairs
4x4x4 les impairs
4x4x4x4 les impairs
il semblerait alors que l'on approche les 2000 (pour du 3000), ça se joue à l'unité près,
rapidos mon évaluation est echec de peu, mais c'est le problème des piquets et des intervales entre les piquets, j'ai fait vite ...

[Ben314]

@Doraki : Oui :lol3: (preuve ?)
@beagle : Oui :++: (tu trouve combien au max ?)
:ptdr:

[Waax22951]

Concernant le "plus" qu'il faut pour l'énigme de départ (et que peut-être certains lycéens connaissent plus ou moins : ce n'est pas du tout du "gros bulldozer"), je la donnerais à qui la veut (par m.p.) MAIS... uniquement après que la "plus simple" ait été résolue vu qu'on en a pas besoin pour celle là.... :zen:

C'est pas gentil..! :lol3:
Du coup j'y réfléchirai un peu dimanche mais je ne garanti rien..!
Ma réponse viendra surement en fin de semaine prochaine..! (Jusque là il va falloir que je sois patient..! :triste: )

Bonne soirée !

[Doraki]

si x est un nombre impair et qu'on regarde la suite (x, 2x, 4x, 8x, ...) on ne peut prendre qu'un nombre sur deux, donc comme le dit beagle on obtient une partie A la plus grosse possible par exemple en prenant tous les x,4x,16x,...

Et donc, on obtient la relation d(n) = [(n+1)/2] + d(n/4).

Ensuite on regarde l'écriture binaire de n et on s'aperçoit qu'on peut sommer séparément dans d(n) la contribution de chaque chiffre binaire (parceque c'est vrai pour l'expression [(n+1)/2], qui vaut 1,1,2,4,8,... pour n=1,2,4,8,16,... ; et parceque (n/4) décale les chiffres binaires de 2 places)
: d(somme des 2^ai) = somme des d(2^ai)

Après un rapide calcul, on a
si n = 2^2x, d(n) = (2/3)*n +1/3,
et si n = 2^(2x+1), d(n) = (2/3)*n -1/3.

Ainsi, d(n) = (2/3)*n + une somme de termes 1/3 et -1/3 selon si les chiffres binaires de n qui sont des 1 sont en position paire ou impaire.

d(n) > (2/3) * n <=> il y a strictement plus de chiffres 1 en position impaire qu'en position paire.
Et bien sur, d(n) < (2/3) * n dans le cas inverse.

Parmi les nombres de 0 à 2^(2x-1), il y a donc autant de n avec d(n) > (2/3) * n que de n avec d(n) < (2/3)*n, donc il suffit de compter les nombres de n qui ont autant de 1 en position paire qu'en position impaire (pour lesquels d(n) = (2/3)*n)

Choisir k parmi x positions paires et k parmi x positions impaires, c'est la même chose que de choisir k parmi x positions paires et ne pas choisir (x-k) parmi x positions impaires, c'est-à-dire choisir un sous-ensemble de x positions parmi 2x (dont k sont paires).
En regroupant tout ça pour les différents k, le nombre de possibilités est donc le nombre de moyen de choisir x positions parmi les 2x positions.

D'où le nombre de n entre 0 et 2^(2x)-1 pour lesquels d(n) > (2/3)*n est 1/2 * (2^(2x) - (x parmi 2x))

[Ben314]

Nickel chrome :king2:

Je soupçonnerais fort que, comme moi, tu as un peu bricolé sur des exemples voir des sommes un peu "biscornue" pour conjecturer le résultat.
Après, comme ma rédaction était légèrement différentes, je la donne quand même.
Elle repose sur le même résultat que toi (énoncé de façon à peine différente) :

Pour tout (base 2)

Une fois le résultat conjecturé, la preuve la plus simple partait de la constatation que tout le monde à fait concernant le "plus gros" A possible qui implique que
et donc que, si on pose , on a
Le résultat se montre alors par une simple récurrence (évidement, comme tout récurrence qui se respecte, elle a le gros inconvénient qu'il faut connaitre le résultat à démontrer pour la faire alors que ta façon de procéder donne le résultat. Perso, la première preuve que j'avais du résultat passait par des sommes assez compliquées)
Pour la suite j'avais fait comme toi, sauf que je n'avais pas "grugé" concernant le nombre de façon de tirer autant de positions paires que de positions impaires et que ça me donnait dans un premier temps comme nombre d'entiers tels que .
Ta preuve ma permis de me rapeller qu'il y avait (évidement) une preuve "pure combinatoire" du fait que

Je le redit : super bien joué.



EDIT : En fait, dans ma récurrence, il faut "sortir le résultat d'un chapeau" pour pouvoir le démontrer, mais en fait dans la tienne, cette partie là

Ensuite on regarde l'écriture binaire de n et on s'aperçoit qu'on peut sommer séparément dans d(n) la contribution de chaque chiffre binaire...

je sais pas trop si "on s'aperçoit que"... bien facilement... :zen:

[Doraki]

Oui tout le coeur du truc tiens dans cette partie là (c'est un truc que je soupçonnais fort en même temps)

Pour montrer proprement cette propriété on commence par la montrer pour f(n) = [(n+1)/2] :
(si n = somme des 2^ai, f(n) = somme des f(2^ai))

f(n) = (n-1)/2 +1 si n est impair (donc si le dernier bit vaut 1), et n/2 si n est pair.
Donc si n est pair le résultat est direct par distributivité de + sur *, et si n est impair on a f(n) = (n-1)/2 + 1 = f(1) + f(n-1) et n-1 est pair donc il se décompose comme on veut.

Ensuite on montre que c'est vrai pour d(n) par récurrence sur son nombre de chiffres et il suffit de l'écrire :
d(somme des 2^ai) = f(somme des 2^ai) + d(somme pour ai >=2 des 2^(ai-2)) = somme des f(2^ai) + somme pour ai >=2 des d(2^(ai-2)) = somme des d(2^ai)

Mais c'est vrai que c'est pas un truc qu'on fait souvent.

C'est marrant on utilise pas du tout la même formule de récurrence.

[Ben314]

Mon "je sais pas trop si "on s'aperçoit que"... bien facilement" ne voulais pas dire que ce n'est pas facile à démontrer (dans ta preuve, ça me suffisait largement), mais que ce n'est pas facile (il me semble) à conjecturer.