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 - 10-10-2016 13:20:20

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

Changer un nobre

Bonjour à tous.

A combien d'échanges entre chiffres voisins (par exemple ...12... --->...21...) doit on procéder pour passer du 1er nombre suivant au 2ème nombre suivant ?

1738250439674693522047619814376099540
4977627055940117836238494393504612069

Le résultat exact est bien sûr demandé, mais ce n'est pas le plus important: La méthode l'est davantage, pour la généralisation qu'elle permet.

Tout ça à la main, bien entendu.

Bon amusement.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 10-10-2016 15:31:41

Agid1915
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 44

Changer un nombree

[HS]J`avais travaille sur ce probleme avec un carre (n*n). Le but etait cryptographique. Les nombres des 0 et des 1. Cle symetrique sous forme algorithmique. Les 2 personnes possedent le meme algorithme de "permutation".
L`algorithme permet de "melanger" et de reconstruire le message original.

Ce probleme est infiniment interessant.
Si apres manipulation d`une suite connue U(n) et complexe moyennant quelques parametres on peut retrouver une autre suite que l`on peut genere moyennant une formule explicite on touche la jackpot en matiere de "compression"
Formule explicite + quelques parametres et on reconstitue une suite determinee.

 #3 - 10-10-2016 19:41:25

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 143

Changerr un nombre

On procède par tri par insertion.
Cet algorithme est de complexité [latex]O(n^2)[/latex] en moyenne donc je vote pour une réponse proche de [latex]37^2=1369[/latex] lol

EDIT : Après application je trouve [latex]187[/latex] roll

 #4 - 10-10-2016 19:48:19

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

chznger un nombre

@ Sydre : il n'y a pas que Wikipédia dans la vie....

Je me doute bien que, poser une telle question en aveugle, c'est un risque d'avoir des réponses connues par les mathématiciens- informaticiens.

Pour l'instant, c'est encore calme....

 #5 - 10-10-2016 20:06:18

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Chhanger un nombre

Il faut procéder à 151 échanges.

Comment y arriver?

Etape 0: Prendre E=0, n=1;
Etape 1: Prendre le nième chiffre de b, notons ce chiffre x;
Etape 2: Compter le nombre de chiffres avant la première apparition de x dans a (notons ce nombre k),
Etape 3: Ajouter k à E;
Etape 4: Supprimer x de a;
Etape 5: Augmenter n d'une unité;
Etape 6: Si b est vide alors E est le nombre d'échanges, sinon retourner à l'étape 1.

Ma méthode résout le problème, mais est ce le nombre minimum? Je ne saurai l'affirmer.

.

 #6 - 10-10-2016 20:40:17

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

Changer u nombre

Bonsoir,
En optant pour une méthode simple (pas forcément optimale), en amenant successivement chaque nombre à sa place, je trouve 151.

 #7 - 10-10-2016 20:55:33

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 67

Cahnger un nombre

Bonjour, supposons dans un premier temps que tout les chiffres soient distants.
Prenons l'exemple 946375182->123456789
On compte le nombre de chiffres supérieurs à un chiffre donné situé à sa droite, et ce pour chaque chiffres.
Ici, 1 va devoir passer au dessus de 946375, 2 au dessus de 9463758
3 va devoir passer au dessus 946
4 va devoir passer au dessus de 9
5 va devoir passer au dessus de 967
...
On obtient au final un certain nombre n de chiffres à "passer"
Chaque transposition augmente ou diminue n de 1:
Si on passe un grand au dessus d'un petit (79->97), la valeur de 7 augmente de un, mais pas celle de 9.
Inversement, un petit au dessus d'un grand diminue la valeur de 1.
Si l'on procède dans l'ordre (placer le 1, puis le 2...), la valeur de n diminue de 1 à chaque fois (le 1 ne peut passer qu'au dessus de valeurs plus grandes, le 2 aussi, à part 1, mais il est déjà au bout, et ainsi de suite)

Si l'on place les chiffres l'un après l'autre, il n'y a pas de mouvements supplémentaires, chaque mouvement "trie" le nombre, c'est le principe du tri par insertion.

Dans le cas où les chiffres peuvent être identiques, il faut associer chaque chiffre à un chiffre unique, deux chiffres identiques mais à deux endroits différents du mot étant associer à un nouveau chiffre distinct l'un de l'autre. On peut alors appliquer notre procédé précédent.
Il faut donc trouver quel "étiquetage" donne une valeur de n la plus petite possible. La réponse est intuitive, il suffit de le faire dans l'ordre:
Par exemple, pour 1232143 -> 1122334
On ré-étiquette le deuxième nombre 1234567.
Le premier sera donc étiqueté 1354276.
On voit bien que proposer un autre étiquetage donnera une valeur de n plus élevée, car pour toutes les instances du chiffre k, le chiffre k ne sautera que pour les valeurs strictement inférieures à k dans le cas proposé ici, mais devra sauter au dessus de valeurs égales à k dans les autres cas. (A noter que changer l'étiquetage entre les valeurs de k ne change pas les valeur associées aux autres chiffres)

Application:
Dans notre, si on étiquette le deuxième nombre 1|2|3|...|37, on trouve pour le premier la permutation 14|3|18|17|6|9|8|1|21|2|5|4|12|19|11|26|10|20|34|13|23|7|32|15|24|22|33|25|28|16|36|30|27|37|29|31|35.
La somme des sauts donne:
1+1+3+3+4+7+8+7+8+4+1+6+8+2+8+2+15+1+9+3+5+1+4+3+14+4+6+6+5+2=151 ce qui nous donne 151 transpositions à effectuer afin de modifier notre nombre (sauf erreur de calcul)

 #8 - 11-10-2016 08:24:24

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

Chnger un nombre

@kossi-tg, Enigmatus, Caduk: vous avez tous la bonne réponse, bravo !

@kossi_tg: Ta méthode de calcul semble efficace, mais par manque de clarté (b ? a ? ) je ne peux pas pour l'instant valider. Preuve qu'on ne peut pas faire mieux? 
@Enigmatus: Reste à prouver qu'on ne peut pas faire mieux.
@Caduk : C'est de la même façon que j'ai calculé, et par là même tu donnes aussi la preuve qu'on ne peut pas faire mieux.

 #9 - 11-10-2016 08:26:30

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

Changer un nobmre

@ tous : il existe une preuve assez expéditive, comme les aime Vasimolo, qui montre qu'on ne peut pas faire moins d'échanges que le nécessaire.

 #10 - 13-10-2016 17:02:41

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

Chagner un nombre

Le temps est maintenant écoulé, et pour ces 3 bonnes réponses, encore un bravo aux auteurs.

Comme promis, la preuve courte (et visuelle) de l'optimisation du nombre d'échanges:

On écrit le nombre Départ en haut d'une page et le nombre Arrivée en bas de page. On trace un segment entre chaque paire de chiffres identiques, l'un en haut, l'autre en bas.
Le nombre d'échanges est égal au nombre de croisements entre les segments !

En effet, on montre facilement:
1) Le final est quand il n'y a plus de croisement.
2) Il existe toujours au moins un croisement entre 2 chiffres voisins du haut (donc aptes au décroisement par échange)
3) Un échange entre 2 chiffres voisins correspond à un unique décroisement.

La seule précaution à prendre est, au moment des tracés, de ne pas croiser 2 paires de chiffres identiques.

La démarche de kossi_tg est remarquable pour la façon efficace de calculer le nombre d'échanges. En réalité, c'est comme s'il avait construit ses 2 nombres chiffre après chiffre, l'un des nombres étant construit en ajoutant chaque chiffre à une extrêmité (toujours la même).

 

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 : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
Suite de la DHR par Gwydyon
25-07-2015 Enigmes Mathématiques
P2T
Divisibilité par perceval
07-05-2008 Enigmes Mathématiques
P2T
Fog N°1 par Vasimolo
18-12-2009 Enigmes Mathématiques
P2T
Infiniment pair ? par nodgim
31-07-2016 Enigmes Mathématiques
P2T
Le congrés des myopes. par PRINCELEROI
05-08-2013 Enigmes Mathématiques
05-02-2009 Enigmes Mathématiques
07-07-2016 Enigmes Mathématiques
P2T
24-10-2009 Enigmes Mathématiques
01-12-2008 Enigmes Mathématiques

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