Dénombrement schémas Android

[TJ12]

Bonjour,

J'ai un petit problème à vous soumettre, pour s'amuser ! Il ne s'agit pas d'un exercice posé, donc je ne connais pas le niveau de difficulté, mais cela ne m'a pas l'air évident.

Il s'agit de dénombrer le nombre de mots de passe possibles en utilisant les "schémas" proposés par Android pour déverrouiller les portables. Pour ceux qui ne connaissent pas, je rappelle les grandes lignes : un écran de 9 points disposés en carré (3 par 3 donc) qu'il faut relier dans un certain ordre pour déverrouiller, sans lever le doigt. On ne peut passer qu'une fois par un point et surtout, le plus difficile, lorsqu'on survole un point il est automatiquement intégré. Par exemple si je commence par le point en haut a gauche, puis vais vers le point en bas a gauche, le point au milieu a gauche est automatiquement inséré entre les deux points d'extrémité.

A vos neurones, moi je n'ai pas trouvé ! Et pour ceux qui trouveront ça trop facile, ils peuvent l'étendre a un carré de N par N !

tJ12

[Ben314]

Questions :
a) Peut-on se déplacer "en diagonale", c'est à dire passer du point (1,1) au point (2,2) sans passer ni par la case (1,2), ni la case (2,1). Je suppose que oui, mais... ?
b) "On ne peut passer qu'une fois par un point" doit on passer exactement une fois sur chaque point ou bien au maximum une fois ?
c) Les points de départ/arrivé sont quelconques ?

[beagle]

en nxn, c'est Ben314 qui le fait,
pour le 3x3 il n' y a pas beaucoup de possibilités, cela se fait en force brute, non?
Il y a trois cases départ seulement à étudier et on tourne vite en rond...

[TJ12]

a) oui
b) au max
c) oui !

Il faut le trouver mathématiquement, c'est bien plus beau ^^

Questions :
a) Peut-on se déplacer "en diagonale", c'est à dire passer du point (1,1) au point (2,2) sans passer ni par la case (1,2), ni la case (2,1). Je suppose que oui, mais... ?
b) "On ne peut passer qu'une fois par un point" doit on passer exactement une fois sur chaque point ou bien au maximum une fois ?
c) Les points de départ/arrivé sont quelconques ?

[beagle]

ça fait un peu plus mais cela ne semble pas insurmontable,
donc on ne passe pas par tous les points,
il y a un nombre de points minimum ou pas?

les diagos peuvent se croiser?

[nodjim]

Je doute de la possibilité de généraliser un tel dénombrement.
Pour 4 touches, je dénombre déja 424 codes possibles.
Quelqu'un pour confirmer ?

[TJ12]

ça fait un peu plus mais cela ne semble pas insurmontable,
donc on ne passe pas par tous les points,
il y a un nombre de points minimum ou pas?

les diagos peuvent se croiser?

Oui elles peuvent se croiser.

On peut donner un nombre k de points minimum, mais là n'est pas la difficulté.
J'ai déjà la solution par brute force, c'est la démonstration mathématique qui serait intéressante.

[LeJeu]

Questions :
a) Peut-on se déplacer "en diagonale", c'est à dire passer du point (1,1) au point (2,2) sans passer ni par la case (1,2), ni la case (2,1). Je suppose que oui, mais... ?
b) "On ne peut passer qu'une fois par un point" doit on passer exactement une fois sur chaque point ou bien au maximum une fois ?
c) Les points de départ/arrivé sont quelconques ?

pas d'android sous la main Ben ....

a) oui on peut se se deplacer en diagonale
b) on doit choisir au moins 4 points : si on repasse par un point déjà pris," ca ne compte pas" et on ne peut pas tourner exemple

Code: Tout sélectionner

1  .  5
.  2  4
6  .  3

on commence par la digonale descendante 1 , puis 2, là on peut tourner, on va au 3
on remonte au 4 on peut tourner si on veut, on va au 5
Et la on peut aller au 6 en passant par le 2 : mais le 2 ne compte pas, on ne peut pas s’arrêter, pas tourner, on le survole

c) oui on part et on arrive ou on veut

ps
un autre exemple, en direct du net , ou on passe par tous les points ( et deux fois par celui de droite au milieu)

[beagle]

hum , repasser sur le 2 qui devient un élément neutre, voilà qui me semble plus compliquer l'affaire que de simplifier.C'était déjà bein compliqué avec les diagos...

[TJ12]

Ah, c'est une autre version. On peut déjà commencer par "simple", en n'autorisant pas du tout un repassage par un point déjà pris.

Merci pour les illustrations.

[nodjim]

Mince alors, je croyais qu'on devait passer par un voisin immédiat, et en fait non. ça me parait une gageure de passer du 1 au 6 entre les 2 et 5 sans acitiver soit 2 soit 5.
Je n'ai pas d'android sous la main, mais je doute fort que ça fonctionne comme ça.

[LeJeu]

Mince alors, je croyais qu'on devait passer par un voisin immédiat, et en fait non. ça me parait une gageure de passer du 1 au 6 entre les 2 et 5 sans acitiver soit 2 soit 5.
Je n'ai pas d'android sous la main, mais je doute fort que ça fonctionne comme ça.

Si si, je confirme bien que ça marche comme je l'indique dans les deux schémas précédents que j'ai bien testés sur mon android ...
et même avec des gros doigts ; ca passe !

[nodjim]

D'accord, c'était pas évident d'emblée.

[beagle]

ouais, mais c'est juste les portables volés où tu as besoin faire tous les codes,
sinon je crois que tu fais un seul code.
sauf peut-ètre à la livraison du portable, faut le dévérouiller pour avoir accès au code qui a été planqué en mémoire.
Parait que c'est comme cela maintenant les nouveaux ordinateurs avec la windows touche moi l'écran, le mode d'emploi est dans l'ordinateur, et c'est couillon quand tu sais pas le lancer!!!
T'as plus un paplar d'explication!!!!

[LeJeu]

Je doute de la possibilité de généraliser un tel dénombrement.
Pour 4 touches, je dénombre déja 424 codes possibles.
Quelqu'un pour confirmer ?

Bon j'ai codé un peu... sauf erreur, je ne confirme pas

avec 4 chiffres :

- avec les déplacements le plus simples ( cases adjacentes) : 496
( 50 en partant d'un coin, 56 en partant du centre et 60 en partant d'un bord)

- en ajoutant les déplacements "de cavaliers" ( le 1->6 de notre exemple précédent)
1400

- en ajoutant les déplacements "saute mouton" ( comme quand je saute le 2 dans mon exemple précédent)
1624

Avec 9 chiffres
- nombre de combinaisons de neuf chiffres exctement 140 704

- nombre de combinaison android ( >=4 et <=9) 389 112

[nodjim]

C'est normal qu'on n'ait pas les mêmes chiffres, je n'avais pas les mêmes bases de départ, notamment cette possiblité de sauter des touches.

[LeJeu]

C'est normal qu'on n'ait pas les mêmes chiffres, je n'avais pas les mêmes bases de départ, notamment cette possiblité de sauter des touches.

je pense que mon 496 est "comparable" à ton 424 ( compte la même chose) si je t'ai bien suivi

[nodjim]

Oui c'est vrai, j'ai revu et il me manquait des combis. J'ai bien 4*50+4*60+56=496.

[beagle]

Bon j'ai codé un peu... sauf erreur, je ne confirme pas

...

[B]Avec 9 chiffres
- nombre de combinaisons de neuf chiffres exctement 140 704

- nombre de combinaison android ( >=4 et <=9) 389 112

Je n'arrive pas à croire à ton 9 exactement.
Si on place tout au hasard, on a 9! = 362 880 possibilités, et tu nous dit que 1/3 de ces possibilités sont adjacents en H, V, D,
c'est énorme, énorme...

Les combi de 9 exactement sans chevauchements,...
elles démarrent par les combi de 4
des jusqu'à 4 tu as 496, et tu multiplies chaque cas de 496 par un facteur 284 pour arriver au 9,
c'est énorme.Si on place les 5 suivants au hasard on a 5! = 120, or beaucoup vont éjecter...

Could you confirm?

[beagle]

hum, le nombre de 4 serait les combi de 1 à 4,
et le neuf exactement serait l'ensemble des combis de 1 à 9?
déjà comptes-tu comme cela?
cela me semble toujours surcoté mais déjà quoiquestcompté?