Exercices sur le principe d'invariance

[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 :

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

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 :

Exercice #4 : On part de l'ensemble {3, 4, 12}. A chaque étape, on choisit deux nombres a, b et on les remplace par et . 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 à ?

[_-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 çà ?

[_-Gaara-_]

Bon exercice 3 =)

http://www124.megaupload.com/files/9d37a108662d0a5055c088144ced64e0/exo.pdf

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

=)

[_-Gaara-_]

Bon let's go pour la 4 =)

[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....

[lapras]

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

[ThSQ]

1 et 4 : somme des carrés

[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)

[Zweig]

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

Exact, mais on pouvait aussi utiliser les invariants :happy2:

[Zweig]

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 dans un espace à 4 dimensions

jhkjhkjhkjhkjh

[Zweig]

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

[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 (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 en en un nombre fini d'itérations ?

[ThSQ]

béhde moin katracé :marteau:

[Zweig]

Lawl :ptdr:

[Zweig]

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

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 ?

[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 . Ainsi l'équation considérée n'admet aucune solution dans les entiers naturels, et donc le dragon ne peut mourir.

[ffpower]

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

[lapras]

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

[Zweig]

Lapras > Oui, on conclut avec ça.

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