omb
Menu principal
Sujets d'articles
Extrait de l'Album
Clés pour les olympiades n°7 [Forum - Questions diverses] Informations | BxMO 2017 | SBPM  


 Bas   Précédent   Suivant Réponse Ecrire un nouveau message



A
Clés pour les olympiades n°7
A
Excusez-moi de déranger mais je tente d'appliquer ce que j'ai appris sur les exercices de pavages dans clés pour les olympiades n°7 mais ça galère vraiment parce que je me demandais comment l'argument de coloriage pourrait s'appliquer dans des situations plus compliquées avec des pièces plus compliquées aussi ? Je trouve qu'il manque des exemples (de diverses difficultés) avant de nous donner les exercices !

Sinon, j'étais bloqué dans les exercices suivants :

Exercice 2 avec le rectangle 10x10 (je n'arrive pas à prouver que le pavage est impossible et je reste persuadé qu'on ne sait pas le faire après plusieurs essais).

Exercice 5 : je ne sais même pas si le pavage est faisable ou pas, j'ai trop de mal à visualiser :(

Exercice 6 : totalement bloqué :(

Exercice 7 : je pensais colorier chaque rectangle 1x8 avec des couleurs de 1 à 8 et donc citer dans le carré 11x11 une case après l'autre les chiffres de 1 à 8 en commençant par 1 à la première ligne. Et j'ai alors des chiffres qui n'apparaissent pas à la même fréquence, je me demandais donc si cet argument suffisait pour la preuve demandée ?


Pardon pour la grosse brique et merci d'avance pour les réponses

Contribution du : 02/08/2014 20:30
Transférer la contribution vers d'autres applications Transférer


Re : Clés pour les olympiades n°7
Groupe A
Inscrit:
03/10/2013 13:49
De La Louvière
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 54
Pour ceux que ça intéresse, les problèmes sont ici en pdf: Clés pour les Olympiades n°7, G. Troessaert
Essayez de résoudre avant de lire les solutions.

Exercice 2
Le carré 10x10 a 100 cases.
Chaque pièce recouvre 4 cases.
Il faut 25 pièces pour un pavage.

On peint le carré en damier et on répartit les pièces du pavage en 2 catégories.
Catégorie A: pièces qui recouvrent 3 cases blanches et 1 noire.
Catégorie B: pièces qui recouvrent 1 case blanche et 3 noires.

Comme le nombre de pièces est impair, une des catégories a plus de pièces que l'autre.
Si c'est la catégorie A, le pavage couvre plus de cases blanches que de noires.
Si c'est la catégorie B, le pavage couvre plus de cases noires que de blanches.

C'est impossible, car il y 50 cases de chaque couleur dans le carré 10x10.

Exercice 5
On divise le cube 6x6x6 en 27 cubes 2x2x2.
On peint ces cubes 2x2x2 en noir et blanc alternativement (on utilise la même couleur pour les 8 petits cubes de chaque cube 2x2x2).
Donc, pour essayer de visualiser, ça ressemble à un cube 3x3x3 peint en damier, mais chaque "case" est en fait constituée de 8 petits cubes de la même couleur.

Il y a 14 cubes 2x2x2 d'une couleur (disons noir), et 13 cubes 2x2x2 d'une autre couleur (disons blanc).
Donc, il y a un plus grand nombre de petits cubes noirs (8x14) que de petits cubes blancs (8x13).

Maintenant, si on s'intéresse à une brique 1x2x4 à l'intérieur du cube 6x6x6, on constate qu'elle est constituée obligatoirement de 4 petits cubes noirs et 4 petits cubes blancs.
Il suffit de regarder "la tranche d'épaisseur 1" qui contient la brique, c'est à dire comment placer un rectangle 2x4 dans un carré 6x6 divisé en 9 carrés 2x2, les carrés 2x2 étant noir et blanc et constituant un damier 3x3 (c'est plus simple que ça en a l'air)

Donc, si on pouvait remplir le cube 6x6x6 avec des briques 1x2x4, on "recouvrirait" exactement le même nombre de petits cubes noirs que de petits cubes blancs (4 cases de chaque couleur avec chaque brique). C'est impossible, car il y a plus de noirs que de blancs.

Exercice 6
Colorions les cases en alternant 3 couleurs (rouge, puis vert, puis bleu) en partant du coin supérieur gauche, en allant d'abord de gauche à droite avant de changer de ligne.
On constate que chaque rectangle 3x1 recouvre exactement une case de chaque couleur, qu'il soit placé n'importe où, horizontalement ou verticalement.
Or, il y a 22 cases rouges, 21 cases vertes et 21 cases bleues.
Donc, si un recouvrement de 63 cases avec 21 rectangles 3x1 était possible, il resterait une case rouge non couverte.

Colorions les cases autrement, encore en alternant rouge, vert et bleu, mais en partant du coin supérieur droit, et en allant de droite à gauche avant de changer de ligne.
Encore une fois, seules les cases rouges peuvent rester inoccupées si un recouvrement par 21 rectangles 3x1 était possible.

Si on réunit nos conclusions, seules les cases qui sont rouges dans les 2 coloriages peuvent rester inoccupées après un recouvrement par 21 rectangles 3x1.
(Or, aucune case n'est rouge dans les 2 coloriages (aucune case n'a la même couleur dans le coloriage 1 et le coloriage 2)
Réponse finale: "There is no field of the board for which that is possible".
)
FAUX !

EDIT : effectivement, 4 cases sont rouges dans les 2 coloriages, et on peut trouver facilement un exemple pour ces 4 cases.

Remarque: pour une preuve plus rigoureuse, utiliser des numérotations modulo 3 au lieu que des coloriages.

Exercice 7
On numérote les lignes et les colonnes de 1 à 11. La case centrale enlevée est en (6,6)
La case juste au-dessus de la case centrale ne peut être couverte par une bande verticale 8x1, il n'y a pas la place.
Donc il y a une bande horizontale 1x8 en ligne 5, qui recouvre obligatoirement la case (5,5).
La case juste à gauche de la case centrale ne peut être couverte par une bande horizontale 1x8, il n'y a pas la place.
Donc il y a une bande verticale 8x1 en colonne 5, qui recouvre aussi obligatoirement la case (5,5).

Les 15 bandes de 8 cases ne peuvent se croiser s'il faut recouvrir les 120 cases restantes, mais on a prouvé qu'il y a obligatoirement croisement en (5,5)
Le recouvrement est donc impossible.

Contribution du : 03/08/2014 14:00

Edité par Damien Galant sur 3/8/2014 14:53:45
Transférer la contribution vers d'autres applications Transférer


Re : Clés pour les olympiades n°7
Professeur OMI
Inscrit:
02/12/2008 15:54
Groupe :
Utilisateurs enregistrés
Professeurs OMI
OMI Groupe Z
Post(s): 403
Pour l'exercice 6, Damien, je pense que tu t'es trompé. Il y a en effet des cases (4, en fait) qui sont rouges dans tes deux coloriages. Et pour chacune de celles-ci, on peut facilement construire un pavage convenant

En ce qui concerne l'exercice 7, je pense qu'il y a aussi moyen de s'en sortir avec un coloriage comme "A" le pensait. En effet, en coloriant le tableau 11x11 avec des couleurs de 1 à 8, exactement comme Damien l'a fait pour l'exercice 6 (de gauche à droite puis en allant à la ligne), on aura 15 fois chaque chiffre, sauf 16 fois le chiffre 1. Or, la case du milieu est coloriée en 5, ce qui permet de conclure. (C'est toujours le même raisonnement : il faut exhiber un coloriage avec 8 couleurs de sorte que chaque pavé éventuel recouvrira une case de chaque couleur. Si les couleurs n'apparaissent pas à la même fréquence, alors il y aura un problème. Il faut cependant faire bien attention à ce que le coloriage soit convenable et que chaque pièce potentielle recouvre exactement une case de chaque couleur! C'est généralement uniquement possible pour les pièces du type 1 x n)

Contribution du : 03/08/2014 14:19
Transférer la contribution vers d'autres applications Transférer


Re : Clés pour les olympiades n°7
Groupe A
Inscrit:
03/10/2013 13:49
De La Louvière
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 54
Effectivement, c'est faux, j'ai édité le premier message.

J'ai encore une question à propos de l'inégalité de Muirhead, mais je vais la poser dans l'autre sujet parce que ça n'a rien à voir avec les pavages.

EDIT : en fait ça sera vraiment trop long et compliqué, je vais l'envoyer par mail.

Contribution du : 03/08/2014 14:56
Transférer la contribution vers d'autres applications Transférer


A
Re : Clés pour les olympiades n°7
A
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 ?

Contribution du : 03/08/2014 16:02
Transférer la contribution vers d'autres applications Transférer


A
Re : Clés pour les olympiades n°7
A
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 ?

Contribution du : 03/08/2014 16:15
Transférer la contribution vers d'autres applications Transférer


Re : Clés pour les olympiades n°7
Groupe A
Inscrit:
03/10/2013 13:49
De La Louvière
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 54
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.

Contribution du : 03/08/2014 16:52
Transférer la contribution vers d'autres applications Transférer


A
Re : Clés pour les olympiades n°7
A
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

Contribution du : 03/08/2014 17:32
Transférer la contribution vers d'autres applications Transférer


Re : Clés pour les olympiades n°7
Professeur OMI
Inscrit:
02/12/2008 15:54
Groupe :
Utilisateurs enregistrés
Professeurs OMI
OMI Groupe Z
Post(s): 403
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

Contribution du : 03/08/2014 18:14
Transférer la contribution vers d'autres applications Transférer



 Haut   Précédent   Suivant

Réponse Ecrire un nouveau message



[Recherche avancée]


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 :