omb
Menu principal
Sujets d'articles
Extrait de l'Album
Forum Informations | BxMO 2017 | SBPM  

Sujet :
Nom/Email :
Icône du message :
Sélectionner
Message : URL  Email  Images  Inside images Flash WIKI link  Source code  Quote

Bold Italic Underline Linethrough    EXEMPLE


 [plus...]
Options :Activer les émoticones
Activer les codes Xoops
Activation du line break (Suggérré non activé si le HTML est activé)
Code anti-spam : 
     
Re : Clés pour les olympiades n°7

par Nicolas Radu sur 3/8/2014 18:14:29

Disons que pour les pièces de largeur 1 (en fait, pour les pièces rectangulaires), un simple coloriage suffit généralement (comme tu as pu le voir sur certains exemples et exercices). Tu peux en effet dans un tel cas colorier la surface en n couleurs (où n est le nombre de cases d'une pièce) de sorte que chaque pièce recouvre exactement une case de chaque couleur.

Quand les pièces sont un peu plus compliquées, cela n'est pas possible (du moins je ne vois pas de configuration où cela pourrait marcher). Un coloriage peut toujours se révéler utile mais il faudra peut-être faire une discussion un peu plus complexe (comme pour l'exercice 2). Une autre façon de "colorier" est la suivante : dans la surface, si tu as calculé qu'il faudrait x pièces pour paver le tout, tu peux exhiber x+1 cases (en les coloriant si tu veux, il n'y a juste qu'une seule couleur ici donc ce n'est pas vraiment un coloriage maintenant que j'y repense) qui sont deux à deux "non-recouvrables", en ce sens qu'une pièce ne pourra jamais recouvrir deux cases colorées. Cela peut se faire même pour des pièces qui ne sont pas de largeur 1.

Je n'ai pas là tout de suite d'exemples pour lesquels cela fonctionne (cela ne marche pas bien pour l'exercice 2 : tu ne parviendras pas à trouver 26 cases deux à deux non recouvrables il me semble), mais je sais qu'il en existe
Re : Clés pour les olympiades n°7

par A sur 3/8/2014 17:32:15

Ah ok, pour l'exercice 6, je croyais que board voulait dire bord, du coup je n'avais rien compris !

Maintenant, c'est clair, j'ai la même chose, merci
Re : Clés pour les olympiades n°7

par Damien Galant sur 3/8/2014 16:52:09

J'utilise 2 coloriages car le premier m'indique que si on enlève une case, elle ne peut être qu'un carré rouge du premier coloriage.
Ça ne montre pas que toutes ces cases sont possibles.
Le second coloriage indique que si on enlève une case, elle ne peut être qu'un carré rouge du second coloriage également !
Et, contrairement à ce que j'avais dit, 4 cases sont rouges dans les 2 coloriages (et on constate facilement qu'elles conviennent).

Évidemment, on peut faire encore plus de coloriages mais ça ne sert plus à rien.
Ici, un seul ne résout pas le problème (en tout cas pas celui que j'utilise).

Tu as du te tromper, seules 4 cases en tout peuvent être enlevées. Essaie de paver l'échiquier en enlevant une case de la première ligne, tu te rendras compte que c'est impossible.


Il manque peut-être des exemples mais bon, ça ne changerait pas grand chose.
Le coup de l'échiquier auquel on enlève 2 coins opposés est une des démonstrations les plus magiques que je connaisse.
C'est vraiment : "Bon, et là on colorie, et regardez ça ne marche pas !"

C'est dans un sens très simple car n'importe qui peut comprendre la démonstration, et très compliqué car "Pourquoi colorier cette grille ?"
Sans connaître le truc, c'est quasi impossible à trouver soi-même.

En fait, l'idée est assez puissante pour prouver pas mal de choses du genre.
En effet, il faut faire des essais de coloriage, de divisibilité, ... avant d'arriver à y voir clair et trouver à une solution.

Oui, c'est un peu du coup de bol.
Ça arrive souvent aux olympiades, parfois on peut trouver une question compliquée très naturellement et parfois... on n'a pas cette bonne idée dans le temps imparti.
Dans le genre, il y aussi les problèmes de géométrie où on rajoute des choses improbables sur le dessin et où la démonstration se résume à 5 lignes, les problèmes d'arithmétique où il faut voir que le problème à un lien étrange avec la suite de Fibonacci, ...
Ce sont toujours de jolies démonstrations mais hélas difficiles à trouver.

Une chose est sûre, quand tu auras fait ces exercices, tu sauras résoudre plus facilement d'autres du genre.
Re : Clés pour les olympiades n°7

par A sur 3/8/2014 16:15:20

Autre question pour Nicolas, comment fait-on si on n'avait pas des pièces de largeur = 1 ?

C'est ça que je reproche dans la partie théorie de clés pour les olympiades n°7 : il manque des exemples pour comprendre parfaitement les idées à utiliser... On nous dit pas vraiment pourquoi on colorie le carré d'une certaine manière et pas d'une autre et paf, on tombe sur la bonne solution, ça me semble beaucoup du hasard et du coup de bol tout ça, non ?
Re : Clés pour les olympiades n°7

par A sur 3/8/2014 16:02:37

Merci beaucoup mais pour l'exercice 6, je ne comprends pas pourquoi on pense à deux coloriages, plutôt qu'à une seule ou à plusieurs autres (on aurait pu partir aussi du coin inférieur gauche ou du coin inférieur droit du carré) ?

Est-ce dû à la symétrie de notre problème ?

Et aussi pour la réponse finale, je pensais que toutes les cases de la première ligne sauf les deux des colonnes 3 et 6 étaient valables, ce qui me donne 6 cases (rouges) qu'on peut ne pas occuper au lieu de 4 en suivant votre raisonnement, non ?
Membres
Prénom :

Nom :

Mot de passe : 

Conserver la connexion

Récupérer mot de passe
Recherche
Le site officiel de l'Olympiade Mathématique Belge
Contact webmasters :