Nombres "remarquables"

[Waax22951]

Bonjour,
J'ai mis un peu de temps parce que je ne me suis pas beaucoup penché dessus, mais je pense avoir trouvé une réponse pour la question plus simple qu'on m'avait posé:

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 simplifier l'écriture, on notera l'ensemble {1, 2, 3, ..., k}.

Montrons que si est un entier remarquable, alors pour tout , est aussi remarquable.
Par définition, si est remarquable, alors il existe une partie de , notée A, telle que tout élément de A, l'entier n'appartienne pas à A et tel que:
.
Considérons l'ensemble nA et montrons qu'il suffit à montrer que est remarquable.. On remarque d'abord que nA est une partie de , en effet pour tout élément k de A, par définition de , on a . De même, puisque tout élément de nA est de la forme nk (avec ) et qu'on a , on peut affirmer que tout élément de nA appartient à , donc nA est une partie de .
Supposons qu'il existe un élément q de nA tel que . Puisque q et 2q appartiennent à nA, il existe deux entiers p et p' appartenant à A tels que:
et
Soit encore:

Donc r n'est pas remarquable, ce qui est absurde. Donc aucun élément de nA n'est le double d'un autre.
De plus, on a:

Donc on a bien montré que si r est remarquable, alors nr l'est aussi.

On remarque ensuite que 3 est remarquable, puisque l'ensemble {1, 3} est une partie de , donc .
Ainsi, est aussi remarquable.

Il existe donc bien une partie A de telle que tout élément de A ne soit pas le double d'un autre élément de A.

Bonne après-midi ! :lol3:

[beagle]

1 x les impairs = 1500
4 x les impairs = 375
4x4 x les impairs = 94
4x4x4 x les imapirs = 23
4x4x4x4 x les impairs = 6
4x4x4x4x4 x les impairs = 1

cela donne 1999 éléments sans double.
alors qui se trompe?

[beagle]

sachant que Ben314 avait mis en début de fil de discussion quelques exemples dont le 6:
"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"

Donc l'affirmation:
"Donc on a bien montré que si r est remarquable, alors nr l'est aussi."
hum ...

[Waax22951]

sachant que Ben314 avait mis en début de fil de discussion quelques exemples dont le 6:
"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"

Donc l'affirmation:
"Donc on a bien montré que si r est remarquable, alors nr l'est aussi."
hum ...

En fait je n'avais pas vu que l'inégalité était stricte, puisque dans mon problème, l'inégalité est au sens large. Si on considère l'inégalité au sens large, on peut dire que 6 est remarquable (dans le cas de mon problème, évidemment..).
Mais par contre je me demande comment j'ai pu écrire "" !!
Du coup je pense qu'on peut conjecturer que , et je pense que ça peut se démontrer par récurrence (j'ai une idée mais je préfère ne pas trop m'avancer..!

Bonne soirée ! :lol3:

[beagle]

En fait je n'avais pas vu que l'inégalité était stricte, puisque dans mon problème, l'inégalité est au sens large. Si on considère l'inégalité au sens large, on peut dire que 6 est remarquable (dans le cas de mon problème, évidemment..).
Mais par contre je me demande comment j'ai pu écrire "" !!
Du coup je pense qu'on peut conjecturer que , et je pense que ça peut se démontrer par récurrence (j'ai une idée mais je préfère ne pas trop m'avancer..!

Bonne soirée ! :lol3:

J'ai comme un doute.
Si on va de 3 en 3, si le multiple de 3 est impair,
alors on va avoir deux impairs et un pair, soit du +2 déjà avec les deux impairs,
que se passe-t-il si le nombre pair est un 4x impairs = prenable,
en allant de nx3 à (n+1)x3 le suivant, on rajoute 3/3 prenables, hum ca va merdouiller

Cherchons un multiple de 3 tel que 3n-1, le précédent soit un 4ximpair
dans les premiers nous avons 4x5x+1= 21 et 4x11+1=45

sauf erreur vu que je ne sais pas reproduire deux fois le mème résultat sur deux calculs différents:
pour le 21: comment peut-on passer de 18 répond au problème à je rajoute 19, 20 et 21 ce qui me donne trois à prendre sur le suivant,
pour 18 on trouve le bon rapport
impairs=9
4ximpairs =2
4x4ximpairs =1
soit 12/18

alors on va compter le 21
21 = 11 impairs + 3 4ximpairs + 1 4x4ximpairs = 15
ce qui fait du 15/21 contre 2/3= 14/21
et bien voilà un de plus , un de trop

Pour le 4x11+1= 45
je vais avoir par rapport à 42, les deux impairs 43 et 45 + le 4ximpairs, je suis à +3 par rapport à 42
alors calculons le 42:
impairs =21
4ximpairs= 5
4x4ximpairs =1
soit 27/42 alors que le 2/3=28/42
il en manque 1

[beagle]

Si on prend le 3000 - 3, le 2997
les 3 derniers sont: 2995 2996 et 2997,
2996 est 4x749 donc sur ces trois derniers nombres, on peut prendre les 3
alors il y a:
impairs :1499
4ximpairs: 375
4x4ximpairs:94
4x4x4ximpairs:23
4x4x4x4ximpairs:6
4x4x4x4x4ximpairs:1
soit 1998 et 1998/2997 = 2/3

Pour les 3 suivants de 2998 à 3000,
je peux prendre l'impair
mais 2998 est 2x1499 et 3000 est 4x2x375 sont non prenables
donc je ne pourrais avancer que de 1 sur les 3, je ne pourrais pas garder du 2/3.