Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 23-12-2015 04:04:10

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

Petit problème d'ascendan.t..

Bonjour à tous. Je vous soumets un petit problème plutôt simple, mais dont la solution n'est pas dénuée d'une certaine élégance.

Un nombre est dit ascendant, lorsque l'ensemble des chiffres qui le compose sont tous différents, et écrit de la gauche vers la droite dans un ordre croissant.

Ainsi, 5, 34, 478, 1239, ou 23478, sont tous des nombres ascendants.
21, ou 4778, ne le sont pas.

La question est celle-ci.

Après avoir dénombré le nombre total des ascendants possibles, pourrez-vous déterminer combien d'entre eux sont divisibles par 11 et nommer ceux qui le sont?

On évitera le dénombrement systématique, on préférera bien sur une méthode générale de résolution (elle existe et ne nécessite aucun tâtonnements, ou séries de tests par " familles " de nombres ).



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 23-12-2015 07:27:15

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

petit problème d'zscendant...

Je dirais aucun...

Un petit raisonnement par l'absurde :
En prenant le problème à l'envers, on cherche un nombre dont les chiffres soient en ordre croissant si on le multiplie par 11.

Soit ABCDEFGH ce nombre (avec moins de chiffres éventuellement, mais pas plus)

Code:

 ABCDEFGH
+ ABCDEFGH
__________
 croissant

On voit que A+B doit donner un résultat supérieur à A, donc il ne peut pas y avoir de retenue à A+B à moins que A soit égal à 9 ce qui est impossible. De fil en aiguille de gauche à droite, il n'y a pas de retenue dans cette addition vu que A+B est aussi supérieur à B du coup.

Seulement, on voit aussi que G+H doit être inférieur à H
Donc il y a une retenue à G+H et par un raisonnement similaire de droite à gauche
F+G+<G+H-10  ce qui n'est possible qu'avec une retenue à F+G De fil en aiguille de droite à gauche, il y a une retenue à chaque rang de l'addition.

C'est donc impossible.

 #3 - 23-12-2015 08:23:25

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Petit rpoblème d'ascendant...

Bonjour,

Question 1 :
Nombre de nombres ascendants à 1 chiffre  : C(9,1)
Nombre de nombres ascendants à 2 chiffres : C(9,2)
...........................................................................
Nombre de nombres ascendants à 9 chiffres : C(9,9)
Ce qui fait un total de [latex]2^9-1=511[/latex] ([latex]2^9=512[/latex] si on admet le 0)

Édité :
Question 2
Un nombre de [latex]p[/latex] chiffres ([latex]k_1,k_2,...,k_p[/latex]) est divisible par 11 si :
p pair : [latex](k_p-k_{p-1})+...+(k_2-k_1)[/latex] est nul ou multiple de 11
Cette somme est strictement positive (chiffres croissants) et inférieure ou égale à [latex]k_p-k_1[/latex], donc inférieure ou égale à [latex]9-1=8[/latex].
p impair : [latex](k_p-k_{p-1})+...+(k_3-k_2)+k_1[/latex] est nul ou multiple de 11
Cette somme est strictement positive et inférieure ou égale à [latex]k_p-k_2+k_1[/latex].
[latex]k_2>=k_1+1[/latex], donc la somme est inférieure ou égale à [latex]k_p-1[/latex], donc inférieure ou égale à [latex]9-1=8[/latex].

Le seul nombre ascendant divisible par 11 est [latex]0[/latex].

 #4 - 23-12-2015 09:10:48

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

peyit problème d'ascendant...

On découpe un nombre ascendant en couples de chiffres à partir du chiffre unité.
a;bc;de
Les chiffres de rang impair ( 1er à partir de la droite) sont tous supérieurs à leurs conjoints. Donc si Si est la  somme des chiffres de rang impair, et Sp la somme des chiffres de rang pair, alors Si > Sp.
Par ailleurs Si-Sp < au plus grand chiffre donc < 11.

Autrement dit :

Si-Sp =\= 0 [11]

Si=Sp [11] est la condition de divisiblité par 11. Cette condition n'est donc jamais satisfaite, sauf pour 0.

Pour le dénombrement:
123456789: dans cette liste, on prend ou on ne prend pas chacun de ces chiffres. On peut donc associer un nombre binaire de 9 chiffres.
il y a donc 2^9 nombres ascendants, soit 512 en comptant le nombre 0.

 #5 - 23-12-2015 09:22:27

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Petit problème d'ascndant...

Pour le cas des nombres divisibles par 11

Soit un nombre A écrit en base 10 A1A2..An

Considérons que 11*A est ascendant.

Alors A(n-1)+A(n) >9, car sinon les 2 derniers chiffres des 11A sont « en baisse » (au sens large l’un des 2 pouvant être nul

L’avant dernier chiffre s’écrit donc A(n-1)+A(n) – 10

Le chiffre précédent s’écrit A(n-2)+A(n-1) +1 ou A(n-2)+A(n-1) -9

Mais dans le premier cas A(n-2) +1 >= A(n)-10 donc on est dans le deuxième cas.

Et ainsi de suite mais alors A1>=A(1) +A(2)-10 et les 2 premiers chiffres sont donc croissants

Il n’existe donc pas de tels nombres ascendant divisibles par 11

En raisonnant exactement de la même manière, on montre que si les chiffres à la droite du nombre sont décroissants alors les deux premiers chiffres seront croissants.

Il n’existe donc pas non plus de nombre descendants divisibles par 11.

 #6 - 23-12-2015 10:40:02

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 931

Petit problèm ed'ascendant...

123456789
Pour construire un nombre ascendant, je choisis une partie non vide de la liste ci-dessus : 2^9-1 solutions, soit 511.
J'applique le critère de divisibilité par 11 sur abcdef par exemple :
(f-e)+(d-c)+(b-a) est compris entre 3 et 6 donc pas divisible par 11.
De manière générale, cette somme d'écarts - strictement positive - est majorée par 9. On peut toujours y voir une somme d'écarts, quitte à mettre un 0 au début d'un nombre ayant un nombre impair de chiffres.
Donc aucun nombre ascendant n'est divisible par 11.
J'espère que certains seront plus clairs que moi dans la preuve...


Celui qui fuit les casse-tête ne vaut pas un clou.

 #7 - 23-12-2015 11:10:17

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

petit problème d'aqcendant...

Bonjour smile

Le premier problème revient à choisir de 1 à 9 chiffres parmi [[1;9]] il y a donc [latex]C_9^1+C_9^2+...+C_9^9=2^9-1[/latex] solutions . Pour le second , le critère de divisibilité par 11 nous dit que la somme des chiffres de rang pair doit être égale à celle des chiffres de rang impair modulo 11 : c'est bien sûr impossible ( l'écart maximal étant de 8 ) .

Vasimolo

 #8 - 23-12-2015 11:43:50

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2706
Lieu: Luxembourg

petit priblème d'ascendant...

Je ne comprends pas bien: il existe une infinité de nombres ascendants.
Cherche t-on la probabilité qu'un nombre pris au hasard soit ascendant ?
Et celle qu'il soit en plus divisible par 11 ?

 #9 - 23-12-2015 16:11:21

jjango
Visiteur

petit problème d'ascensant...

Pour le dénombrement des nombres ascendants, ça revient à des tirages sans remise, donc avec des "k parmi n".
Nb d'ascendants = 652
Pas de nb ascendant divisible par 11, car la différence entre les chiffres de rang pair & impair < ou égal à 9.

 #10 - 23-12-2015 20:26:35

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

Petit problème 'ascendant...

Gwen27, ta résolution est originale. Mais il manque le dénombrement des ascendants, et que fais-tu du 0?

Nogdim, Portugal, scrablor, Vasimolo, ok. Mais où est passé le 0?
Enigmator, ok. Bravo. smile
C'est à cette résolution que je pensais, en particulier à celle de scrablor, et d'une interprétation géométrique d'une somme d'écart, sur un segment de droite.

Francky1103, tu commets une erreur de raisonnement, les ascendants sont dénombrables.

Jjango, ok pour le critère de divisibilité, mais que fais-tu du 0? En revanche, ton dénombrement n'est pas correct. Ta combinaison ne répond à la problématique. On cherche une somme de combinaison (ou autre moyen efficace de dénombrement).

 #11 - 23-12-2015 20:29:19

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

Petit problèm d'ascendant...

Gwen27, ta résolution est originale. Mais il manque le dénombrement des ascendants, et que fais-tu du 0?

Nogdim, Portugal, scrablor, Vasimolo, ok. Mais où est passé le 0?
Enigmator, ok. Bravo. smile
C'est à cette résolution que je pensais, en particulier à celle de scrablor, et d'une interprétation géométrique d'une somme d'écart, sur un segment de droite.

Francky1103, tu commets une erreur de raisonnement, les ascendants sont dénombrables.

Jjango, ok pour le critère de divisibilité, mais que fais-tu du 0? En revanche, ton dénombrement n'est pas correct. Ta combinaison ne répond à la problématique. On cherche une somme de combinaison (ou autre moyen efficace de dénombrement).

 #12 - 23-12-2015 20:58:31

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Petit problèm ed'ascendant...

Pour le zéro, c'est un oubli si tu considères (au sens strict) les  nombres à un chiffre comme ascendants.

Pour le dénombrement, sauf erreur, c'est assez simple :
0 (à part)

8 à 1 chiffre commençant par 1
7 à 1 chiffre commençant par 2
...

8 + 7 + 6 +5 +4 +3 +2 +1 ==> n(n+1)/2 = 36

A 2 chiffres c'est pareil mais on en a 1 qui empruntent toutes les combinaisons de 2 avec 7 chiffres soit 8*28 puis 1*7*21 ....

De fil en aiguille par récurence :
36*1
28*2
21*3
15*4
10*5
6*6
2*7
1*8

Sans oublier du coup les 10 chiffres : j'arrive à 334
EDIT : j'oubliais 123456789
Un seul est alors ascendant multiple de 11 : ZERO

 #13 - 23-12-2015 21:41:17

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

Petit probllème d'ascendant...

Gwen27, ton dénombrement n'est pas complet. Ta méthode ne dénombre pas l'ensemble des combinaisons, en particuliers parce que tu sautes trop vite de ton exemple de dénombrement des ascendants à deux chiffres, à la récurrence qui dénombre l'ensemble des ascendants par " familles " de nombres.

Mais plus généralement, on peut éviter ce dénombrement fastidieux. Rien ne t'oblige à t'astreindre à une telle tâche.
J'ai sous les yeux une méthode d'une simplicité confondante, et cela sans utiliser la moindre combinaison.

 #14 - 23-12-2015 21:59:50

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Petit problème d'scendant...

Laidzep a écrit:

J'ai sous les yeux une méthode d'une simplicité confondante, et cela sans utiliser la moindre combinaison.

Je crois avoir une idée : pour chacun des chiffres 1 à 9 placés par ordre croissant, on peut le choisir, ou non. Cela fait [latex]2^9=512[/latex] possibilités.

 #15 - 23-12-2015 22:18:18

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

Petit problème d'ascednant...

Exactement Enigmatus. Bravo à toi. smile

 #16 - 23-12-2015 22:27:26

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

pztit problème d'ascendant...

Il me semble que ça fait :
10 + 8*9/2 + 7*8*9/6 + 6*7*8*9/24 + ... = 512 nombres ascendants.

A suivre...


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #17 - 24-12-2015 01:48:21

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

petit problème s'ascendant...

6Une autre méthode bien  plus elegante trouvée par hasard en cherchant un nouveau  problème pour p2t. J'ai d'abord trouvé un résultat sûrement connu :

Un nombre est divisible par 11<=> la somme de ses rangs pairs  et impairs sont égaux modulo 11

Je vous laisse le plaisir de montrer ce résultat plutôt que de l'écrire. C'est tout simple.

Je suis donc revenu à nos moutons...

A part 0.......Un nombre ascendant est une extraction de 123456789

Au passage le nombre de combinaisons d ascendent est la somme du nombre de choix de k dans 9 pour k = 1 à 9. (C n k)
Le calcul est à partir de la formule de probabilité classique.


La différence entre les sommes des rangs pairs et impairs est donc comprises entre 1 et 9 car :

-strictement positive par construction en prenant les chiffres 2 à 2 à partir des unités qui forment une somme de nombre positifs

-inférieure au nombres des unités et donc à 9 en prenant les chiffres  2 à 2 a partir des dizaines qui diminuent le chiffre des unités

Ca résoud notre problème ainsi que celui des descendants en faisant la même chose en regardant le nombres dans l'autre sens.

 #18 - 24-12-2015 06:02:03

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

petit priblème d'ascendant...

Effectivement... Il suffit d'imaginer les chiffres comme un escalier dont on emprunte les marches, ou pas.

2^9 possibilités donc , soit 512.

Pour la seconde partie, on peut aussi prendre le critère de divisibilité par 11 : somme des chiffres de rang pair = somme des chiffres de rang impair modulo 11.

L'égalité est impossible :
Avec un nombre pair de chiffres, rang pair > rang impair.
L'inverse avec un nombre impair de chiffres.
Et l'écart entre les sommes est plus petit ou égal à la différence entre les deux derniers  le premier et le dernier chiffre (voire inégalité ci-dessus) soit 8.

On retombe sur le seul cas particulier permettant d'avoir somme des pairs = somme des impairs : ZERO.

 #19 - 24-12-2015 09:19:01

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Petit problème d'ascendant....

Ah ce 0 qui est divisible par tous les autres sauf lui même....

 #20 - 24-12-2015 17:05:16

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

petit problème d'asczndant...

Fix33, ok pour le dénombrement, mais tu peux faire plus simple que cette somme d'arrangements.

Portugal, même chose, le dénombrement peut se faire plus simplement qu'en employant une somme de combinaisons. En revanche, pour dénombrer les multiples de , c'est bien la solution à laquelle je pensais, cette somme de différence pouvant s'interpréter comme une longueur sur un segment de droite, ce qui permet de s'extraire quasiment d'un problème arithmétique, pour en donnant une résolution avec une démonstration géométrique. C'est à mon avis plus simple que ta première démonstration plus haut, bien qu'elle soit exact elle aussi. Bravo à toi. smile

Gwen27, cette fois, je suis ok. Ta méthode de dénombrement est celle que j'avais en tête, et ok pour les multiples de 11 avec la méthode de la différence. Bravo. smile

Nogdim, cette fois ta solution est complète. Bravo à toi aussi. smile

 #21 - 25-12-2015 14:02:11

dbab3000
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 110

Petit prblème d'ascendant...

On sait que la formule  [latex]C_n^k[/latex] signifie qu'on va utiliser n chiffres sans utiliser le même chiffre deux fois dans k emplacements pour avoir le nombre de tous les combinaisons possibles.
Mais cette formule ne s'intéresse pas à l'ordre des chiffres.
Par exemple  n=3 k=3 (les trois chiffres sont 3,4 et 7)
[TeX]C_3^3=1[/TeX]
Normalement il y a une seule combinaison car il y a 3 nombres et 3 emplacements mais la combinaison peut être (743,734,473,437,374, et 347) le seul nombre ascendant est 347.
Donc on peut dire que la formule [latex]C_n^k[/latex] peut nous donner le nombre des nombres ascendants même si la formule ne s'intéresse pas à l'ordre des chiffres.
On pose N le nombre des nombres ascendants.
[TeX]N=C_{10}^1+\sum_{k=2}^9 C_9^k =512[/TeX]
Lorsque le nombre est un seul chiffre le 0 est inclus dans les 10 chiffres, mais lorsqu'on dépasse un seul chiffre on ne peut plus utiliser le 0 donc on va seulement utiliser 9 chiffres.
Posons X un nombre ascendant qui a p chiffres tel que p≤9
X peut s'écrire de cette façon:
[TeX]X=\sum_{k=1}^p x_{k}10^{k-1} [/TeX]
Tel que [latex]x_{k}<x_{k-1}[/latex]
Un nombre est divisible par 11 lorsque la différence entre la somme des chiffres de rang pair et la somme des chiffres de rang impair est un multiple de 11
On pose:
P la somme des termes pairs
I la somme des termes impair
Si p est pair
x₂<x₁
x₄<x₃
[TeX]x_{p}<x_{p-1}[/TeX]
Alors P<I donc 0<I-P
Posons I'=I et P' tel que
x₂=x₃
x₄=x₅
[TeX]x_{p-2}=x_{p-1}[/TeX]
On remarque P'<P
Alors 0<I-P<I'-P'
avec [latex]I'-P'=x_{1}-x_{p}[/latex]
Alors [latex]0<I-P<x_{1}-x_{p}<9<11[/latex]
Donc 0<I-P<11 ce qui implique que N n'est pas divisible par 11
Si p impair
x₂<x₁
x₄<x₃
[TeX]x_{p-1}<x_{p-2}[/TeX]
Alors P<I donc 0<I-P
Posons P"=P et I" tel que
x₂=x₃
x₄=x₅
[TeX]x_{p-1}=x_{p}[/TeX]
On remarque que I<I"
Alors 0<I-P<I"-P"
avec I"-P"=x₁
alors 0<I-P<x₁<11
Donc 0<I-P<11 ce qui implique que N 'est pas divisible par 11
Conclusion aucun des nombres ascendants n'est divisible par 11 sauf le 0 qu'on peut considérer comme multiple de 11
Bonne journée.

 #22 - 25-12-2015 18:52:48

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2706
Lieu: Luxembourg

petit problème d'ascenfant...

Nombres ascendants à 1 chiffre:      9 (tous)
Nombres ascendants à 2 chiffres:   36
Nombres ascendants à 3 chiffres:   84
Nombres ascendants à 4 chiffres: 126
Nombres ascendants à 5 chiffres: 126
Nombres ascendants à 6 chiffres:   84
Nombres ascendants à 7 chiffres:   36
Nombres ascendants à 8 chiffres:     9
Nombres ascendants à 9 chiffres:     1
On retrouve les coefficients binomiaux du triangle de Pascal.
Au-delà de 10^10, plus aucun nombre ne peut être ascendant.
En additionnant les différences entre deux chiffres de rang consécutif, on
n’obtiendra jamais ni 0 ni 11, donc aucun ne peut être divisible par 11.

On a donc un total de 511 nombres ascendants dont aucun n’est
divisible par 11.

 #23 - 26-12-2015 12:40:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Petit problème d'ascndant...

Ca m'a paru difficile à aborder jusqu'à ce que je repense à "grenouille et escalier".

Sympathique problème. smile

 #24 - 26-12-2015 15:53:22

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Petitt problème d'ascendant...

J'ai pensé à "grenouille et escalier" !! hmm
Mais pas assez fort manifestement ! Ce dernier post a pourtant suffit à m'ouvrir l'esprit ! roll


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #25 - 27-12-2015 01:03:53

Laidzep
Professionnel de Prise2Tete
Enigmes résolues : 35
Messages : 165

Petit problème d'ascendant..

Merci à tous d'avoir participé, et je l'espère pris du plaisir en tentant de résoudre ce problème.

Ce qui à mon sens, rend ce problème plutôt élégant, c'est son degré de difficulté variable selon l'angle avec lequel on s'y attaque, comme le précise Gwen27 (merci pour ta sympathique remarque wink ).

Il me semble que les solutions proposées ici sont suffisamment concises et éloquentes pour ne pas avoir à la formuler encore une fois.


Je reprendrai simplement les méthodes qui me semblent les plus rapides, simples, et efficaces, pour résoudre ce petit problème.


Celle d'Enigmatus concernant le dénombrement :

Je crois avoir une idée : pour chacun des chiffres 1 à 9 placés par ordre croissant, on peut le choisir, ou non. Cela fait 2^9=512 possibilités.

Et celle de scrablor pour la divisibilité par 11 :

J'applique le critère de divisibilité par 11 sur abcdef par exemple :
(f-e)+(d-c)+(b-a) est compris entre 3 et 6 donc pas divisible par 11.
De manière générale, cette somme d'écarts - strictement positive - est majorée par 9. On peut toujours y voir une somme d'écarts, quitte à mettre un 0 au début d'un nombre ayant un nombre impair de chiffres.
Un seul ascendant est divisible par 11 : 0.

Mention spéciale au cryptarithme de Gwen27, qui à défaut d'être intuitif, est original et surprenant.


Il y avait 512 nombres ascendants à dénombrer, et un seul divisible par 11, le 0 (souvent oublié).


Merci à vous tous. smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 20 moutons, ils meurent tous sauf 12, combien en reste-t-il ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete