Exercices sur le principe d'invariance

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Zweig

Suite à l'interrogation de _-Gaara-_ sur un autre post sur "le principe d'invariance" je propose l'ouverture de ce topic qui distillera uniquement des exercices utilisant ce principe. N'hésitez pas à l'enrichir avec vos propres exercices en laissant néanmoins les autres réfléchir ("blancotez" vos réponses). Avant tout, une présentation de ce principe s'impose.

Principe d'invariance :

Ce principe s'applique aux algorithmes (jeux ou transformations) : certaines tâches sont exécutées de manière répétitive. Quelle quantité reste la même ? Quel objet reste invariant ? Voici une maxime simple à retenir :

S'il y'a une action qui se répète, cherchez ce qui ne change pas !


Exercice # 1 : Soient quatre entiers a, b, c, d. On suppose qu'ils ne sont pas tous égaux. En partant de (a, b, c, d) et en appliquant des itérations de la transformation qui remplace (a, b, c, d) par (a - b, b - c, c - d, d - a), montrer qu'au moins l'un des quatre nombres deviendra arbitrairement grand.

Exercice #2 : Au parlement de Sikinie, chaque député a au plus trois ennemis. Montrer qu'il est possible de séparer le Parlement en deux sous-parlements de sorte que chaque député ait au plus un ennemi dans son propre sous-parlement.

Exercice #3 : Résoudre l'équation dans R : (x^2 - 3x + 3)^2 - 3(x^2 - 3x + 3) + 3 = x

Exercice #4 : On part de l'ensemble {3, 4, 12}. A chaque étape, on choisit deux nombres a, b et on les remplace par 0.6*a - 0.8*b et 0.8*a + 0.6*b. Peut-on obtenir en un nombre fini d'étapes :

i) l'ensemble {4, 6, 12} ?
ii) l'ensemble {x, y, z} où |x - 4|, |y - 6|, |z - 12| sont tous inférieurs à 1/\sqrt{3} ?


Posted by: _-Gaara-_

Salut Zweig =)

C'est super ce que tu fais héhé çà permet à tout le monde de comprendre des notions incompréhensibles dans un bouquin.. :D


Pour ma part j'attaque l'exo 3 qui me semble (^^) le plus facile =)

pour écrire en transparent je mets l'écriture en White c'est bien çà ?


Posted by: _-Gaara-_

Bon exercice 3 =)

http://www124.megaupload.com/files/...ced64e0/exo.pdf

J'ai pas trouvé de truc où balancer le fichier donc voilà

=)


Posted by: _-Gaara-_

Bon let's go pour la 4 =)


Posted by: ffpower

le 4 est facile si tu reconnais a quoi correspond la transformation mais chaud sinon.j ai aussi fait le 3,mais juste théoriquement lol(pas envie de faire les calculs).la je cherche le 1....


Posted by: lapras

Pour le 3) il y a des racines évidentes et on peut factoriser à l'aide de la méthode de Horner !


Posted by: ThSQ

1 et 4 : somme des carrés


Posted by: ffpower

ca y est aussi pour le 1,mais je vois pas le rapport avec les invariants(je diagonalise la matrice).reste plus que le 2,qui a pas l air evident(me fait penser un peu au lemme des mariages)


Posted by: Zweig

Citation:
Posté par lapras
Pour le 3) il y a des racines évidentes et on peut factoriser à l'aide de la méthode de Horner !


Exact, mais on pouvait aussi utiliser les invariants


Posted by: Zweig

Citation:
Posté par ffpower
ca y est aussi pour le 1,mais je vois pas le rapport avec les invariants(je diagonalise la matrice)


Indice : On pose P_n = {a_n, b_n, c_n, d_n} l'ensemble après n itérations, n >= 1. On remarque que pour tout n >= 1 : a_n + b_n + c_n + d_n = 0 (notre invariant), d'où l'idée d'utiliser le carré de la distance du point P_n à l'origine d'un repère d'un espace à 4 dimensions


Posted by: Zweig

J'en rajoute un que je viens juste de réussir ^^ Bon, il n'est pas insurmontable, à condition qu'on ait les bonnes idées dès le départ ^^ Donc comme d'hab, "regardez ce qui ne varie pas aux cours des manip' autorisées" :

Exercice #5 : On peut appliquer les opérations suivantes au polynôme ax^2 + bx + c (a, b et c des réels) :

i) échanger a avec c
ii) remplacer x par x + t, avec t un réel.

Peut-on transformer le polynôme x^2 - x - 2 en x^2 - x - 1 en un nombre fini d'itérations ?


Posted by: ThSQ

béhde moin katracé


Posted by: Zweig

Lawl


Posted by: Zweig

Un autre pour la route. Je posterais ma solution demain car je ne suis pas très sûr de ma démo

Exercice #6 : Un dragon a 100 têtes. Un chevalier peut couper exactement soit 15, soit 17, soit 20, soit 5 têtes en un coup d'épée. Il repousse alors respectivement 24, 2, 14 et 17 nouvelles têtes. Si toutes les têtes sont coupées, alors le dragon meurt.

Peut-il mourir ?


Posted by: Zweig

Quoi que, je la poste vite fait :

On applique les transformations autorisées :

15 -> 24 => -15 + 24 = +9
17 -> 2 => -17 + 2 = - 15
20 -> 14 => -20 + 14 = - 6
5 -> 17 => -5 + 17 = +12

Ainsi, en appliquant les coups d'épée, le dragon gagne soit 9 ou 12 têtes, ou en perd 15 ou 6. Si le dragon meurt, alors il existe des itérations (a, b, c, d) pour chaque coup d'épée telle que l'équation suivante admet des solutions dans les entiers positifs :

9a - 15b - 6c + 12d = -100

Or clairement, 9a - 15b - 6c + 12d = 0[3] et 100 = 1 [3]. Ainsi l'équation considérée n'admet aucune solution dans les entiers naturels, et donc le dragon ne peut mourir.


Posted by: ffpower

Une notion originale du lendemain^^.J ai obtenu le meme resultat et la meme demo


Posted by: lapras

salut,
pour le #5, l'invariant est le discriminant delta.


Posted by: Zweig

Lapras > Oui, on conclut avec ça.

Ffpower > Oui, j'avais pas envie d'attendre "demain" pour savoir si j'avais juste ou non ! Bon, content que se soit juste alors !










-