Probleme 1 tfjm 2019
Autor:
Olivier Lamothe
Letzte Aktualisierung:
vor 6 Jahren
Lizenz:
Creative Commons CC BY 4.0
Abstrakt:
Problème 1 tfjm 2019
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
Problème 1 tfjm 2019
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass[a4paper, 11pt]{article}
\usepackage{cours, hyperref}
\geometry{vmargin=2cm}
\title{Problème 1 \\ Une commande disproportionnée}
\date{}
\author{Les Math'uvu}
\everymath{\dzz}
\usepackage{caption}
\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand\headrulewidth{0 pt}
\fancyhead[L]{}
\fancyhead[R]{}
\fancyfoot[C]{\footnotesize{\thepage \\ problème 1: Les Math'uvu }}
\date{}
\begin{document}
\maketitle
\tableofcontents
\newpage
\section*{R\'esum\'e}
Dans ce problème nous étudierons tout d'abord les conditions pour qu'un plan de maison respect les conditions exprimé dans l'énoncé.\\
Nous verrons ensuite quels sont les dimensions de maison qui autorisent des sorties positionnées dans les angles du bâtiment.\\
Puis nous étudierons quel sont les tailles possible d'une boucle.\\
Nous nous demanderons ensuite si il est possibles pour une maison de ne contenir aucun bimur consécutif.
Nous verrons ensuite en fonction des dimensions de la maison quels sont les case qui peuvent être des sorties.
\section*{Notation}
Pour résoudre ce problème nous utiliserons différentes notations.\\
Tout d'abord, $a$ et $b$ qui seront les dimensions de la maison.\\
Ensuite, dans chaque case, nous écrirons un chiffre qui correspond au nombre de case voisine de cette case.\\
Nous appelons emplacement un endroit ou il est possible de mettre un point ou un cercle et un point.\\
Figure 1:\\
\includegraphics[width=.5\lnw]{1}\\
Nous modéliserons les murs par un point situer a l'intersection d'un trait vertical et d'un horizontal.\\
Par exemple, les deux traits de la figure 1 seront modélisé de la même manière car un trait qu'il soit vertical ou horizontal fera baisser de un le nombre de case adjacente des case aux alentours.
De plus, un croisement de deux murs sera représenter par un petit cercle autour d'un point. Et si il est impossible de mettre un point un emplacement, alors nous devons mettre une croix.\\
Ainsi, la figure 2 modélise les deux constructions de maison des figures 3 et 4:\\
Figure 2:\\
\includegraphics[width=.5\lnw]{2}\\
Figure 3:\\
\includegraphics[width=.5\lnw]{3}\\
Figure 4:\\
\includegraphics[width=.5\lnw]{4}\\
De plus nous considéreront un "mur" comme un des mur présent a l'intérieur dune maison et non les dimensions du bord de la maison de donald.
\newpage
\section{Condition nécessaire a un plan de maison}
\prop{Un plan est constructible avec des bimurs si et seulementt si les différents murs sont de longueur pair, il n'est constructible alors que d'une seule manière.}
\dem{Les murs ne pouvant pas se superposer, un mur de longueur impair ne pourra pas être découpé en un nombre $m$ de segment de longueur 2. Ainsi, si on sépare les murs présent dans le plan de la maison de donald en ne prenant ensemble que les murs consécutifs, nous pouvons mesurer leur longueur et en déduire par leur parité si ils sont constructible avec des bimurs.\\
Par exemple, la maison de la figure 5, nous pouvons séparer les murs comme sur la figure 6.\\
Figure 5:\\
\includegraphics[width=.8\lnw]{5}\\}
\newpage
\dem{
(suite)\\
Figure 6:\\
\includegraphics[width=.8\lnw]{6}\\
Ainsi, nous pouvons mesurer que sur la figure 6, les murs orange, jaune, vert et bleu mesurent 2 de long et sont donc pair, mais que le mur rouge est de longueur 3 et donc impair, le plan n'est donc pas constructible avec des bimurs. Mais le plan de la figure 7 l'est:\\
Figure 7:\\
\includegraphics[width=.8\lnw]{7}\\.
}
\newpage
\dem{
(suite)\\
En effet, les murs orange et rouge sont de longueur 4 et sont donc pair, tandis que les murs vert et bleu sont de longueur bleu et donc pair.\\
Un mur de longueur $2n$ est donc pair et est donc réalisable. Ce mur ne sera réalisable que d'une seule façon car il n'y a qu'une seule façon d'agencer $n$ mur pour qu'ils forment un seul mur de longueur $2n$: en les mettant cote a cote.
Un plan constructible n'aura par ailleurs que des murs de longueur pair sinon il devient inconstructible, cette condition est donc nécessaire.}
\section{Construction d'un plan avec des sorties dans les coins}
\prop{Un plan ne peut avoir des sorties dans chaque coins du bâtiment si et seulement si ses dimensions $a$ et $b$ sont pair.}
\dem{On rappelle que pour qu'une case soit une sortie, il faut que cette case n'ait que une case voisine.\\
Donc pour que une case dans un coins de bâtiment soit une sortie, il faut que il y ait un point a l'emplacement du point rouge de la figure 8.\\
Figure 8:\\
\includegraphics[width=.8\lnw]{8}\\
Or pour que les case adjacente ne soit pas des sorties il n'est pas possible qu'elles soit en contact avec d'autres points. Nous mettons alors des croix sur les emplacements dans l'alignement, comme le montre la figure 5. La troisième case dans l'alignement doit donc réduire de 1 pour passer a 2, il faut donc placer un point sur l'emplacement suivant dans l'alignement.
}
\newpage
\dem{
(suite)\\La quatrième case sera donc elle aussi en contact avec le point et n'aura donc plus que deux cases adjacentes, l'emplacement suivant sera donc une croix. La case suivante devra elle aussi réduire de un, il faut donc que l'emplacement suivant soit un point...\\
Il faut donc faire une alternance entre point te croix sur la première ligne d'emplacement pour que les case du haut respecte la condition.\\
Mais si le nombre $b$ est impair, le nombre d'emplacement sera pair, et l'alternance point, croix, point... se terminera sur une croix.\\
Or si l'alternance se termine sur une croix, alors le coin opposé ne sera pas une sortie. Il n'est donc pas possible pour une maison d'avoir des sortie uniquement dans les coins du bâtiment si les dimensions de la maison ne sont pas toutes les deux pair.\\
Nous avons donc démontrer que si pour qu'une maison ne contiennent des sorties que dans les coins du bâtiment alors elle doit avoir ses dimensions pair. Mais il faut maintenant démontrer que cela reste possible.\\
Les case se trouvant sur le bord de la maison n'ont plus besoin de changer après avoir placer l'alternance de point et de croix. Il faut donc maintenant nous intéressé des cases au centre de la maisons.
Nous pouvons remarquer que les cases au centre du bâtiment on pour nombre de case voisine: 3 si elles touchent les cases au bord ou 4 si elles ne les touchent pas:\\
Figure 9:\\
\includegraphics[width=.8\lnw]{9}\\
On se rend compte alors que nous pouvons refaire la même technique que précédemment: faire une alternance de point et de croix verticalement et horizontalement sur les bords de ce nouveau rectangle en partant de la case du centre en contact avec le point rouge:\\
}
\newpage
\dem{
(suite)\\
Figure 10:\\
\includegraphics[width=.8\lnw]{10}\\
Nous obtenons alors au centre un nouveau rectangle avec la même répartitions des chiffres que le rectangle précédent. Il est donc possibles de répéter l'opération jusqu'à ne plus obtenir que un rectangle de 2 de largeur et pouvoir ainsi remplir la dernière ligne par une alternance de point et de croix.\\
Nous obtenons alors la figure suivante:\\
Figure 11:\\
\includegraphics[width=.8\lnw]{11}\\ }
\newpage
\section{Construction d'une maison sans bimurs consécutifs}
\prop{Pour tout $a$ et $b$ il est possible de construire une maison sans bimurs consécutif.}
\dem{Pour démontrer cette question, nous nous contenterons de donner une construction qui marchera pour n'importe quelle valeur de $a$ et $b$.\\
Pour ce faire nous mettrons sur la première colonne une alternance de point et de croix jusqu'à la fin:
Figure 12:\\
\includegraphics[width=1\lnw]{12}\\
Ainsi la première ligne comportera pour toutes les cases deux cases voisines, sauf pour celles d'en haut qui n'aura que une seule case voisine et pour celles d'en bas qui en aura une ou deux selon la parité de $b$.\\
En suite, nous recommençons la même alternance mais en décalant de un:\\
Figure 13:\\
\includegraphics[width=1\lnw]{13}\\
Ainsi, les case de la deuxième rangée de case auront elles aussi un bon nombre de voisines.\\
En effet, les cases du centre auront forcement deux point en contact: à deux coins opposés.\\}
\newpage
\dem{
(suite)\\
La case d'en haut aura un point en contact: le premier point de la première ligne.\\
La case d'en bas aura aussi un point en contact. Si le nombre $b$ est pair alors ce sera le dernier point de la deuxième colonne et il y aura une croix au dernier emplacement de la dernière colonne. Et inversement si $b$ est impair.\\
En continuant de remplir de la même manières nous obtenons ceci:
Figure 14:\\
\includegraphics[width=1\lnw]{14}\\
Ainsi toutes les cases auront un bon nombre de voisins. Il ne nous reste plus qu'à définir les murs.
Pour ce faire nous mettrons le premier mur de la première colonne vertical, puis le second horizontale pour qu'il ne soit pas en contact avec le premier mur et le troisième vertical, etc... Nous ferons de même pour la seconde colonne. A la troisième colonne nous recommençons mais avec le premier mur a l'horizontale pour qu'il ne soit pas en contact avec le premier mur de la deuxième colonne. ET ainsi de suite jusqu'à finir tout les murs. Nous obtenons alors ceci:\\
}
\newpage
\dem{
(suite)\\
Figure 15:\\
\includegraphics[width=1\lnw]{15}\\
Ainsi, cette construction répond à l'énonce et est faisable pour toute valeur de $a$ et $b$.\\
Par exemple, pour $a=12$ et $b=7$, nous obtenons ceci:\\
Figure 16:\\
\includegraphics[width=1\lnw]{16}\\
}
\newpage
\section{Case externes pouvant contenir une sortie et nombre de sortie d'une maison}
\prop{Si une des longueurs $a$ ou $b$ est impair alors les cases externes non-coin du bord oppose ne peuvent pas être des sorties.}
Ex:
Figure 17:\\
\includegraphics[width=.8\lnw]{17}\\
La longueur $b$ est impair donc les case en rouge ne pourront pas être des sorties.\\
Au contraire,la longueur $a$ est pair, les cases en bleu peuvent donc être des sorties.\\
\dem{Pour qu'une case externe soit une sortie, il faut qu'elle n'est qu'un seul voisin. et pour cela il n'y a que trois manière:
Figure 18:\\
\includegraphics[width=1.2\lnw]{18}\\
Que l'on choisissent n'importe quelle des trois façon, la case adjacente aura elles aussi perdue 2 voisin et donc ne pourra plus en perdre. les deux emplacements suivant seront donc occupé par des croix, comme montré sur la figure.\\
Nous nous retrouvons alors dans la même position que toute à l'heure: il faut baisser la case de deux alors qu'il n'y a que deux emplacements de disponible.\\
Il nous faut donc a nouveau choisir entre les 3 même façon. Et a nouveau la case adjacente sera elles aussi réduit de 2 etc...\\
Il nous faut donc faire une alternance de une des trois façon et de croix;croix et ainsi de suite.\\}
\newpage
\dem{
(suite)\\
Cela peut ainsi donner ceci:\\
Figure 19:\\
\includegraphics[width=1.2\lnw]{19}\\
Or si la longueur opposés est impair, il y aura un nombre pair d'emplacement d'affiler et donc la case se trouvant en face de la case que nous étudions aura alors 2 croix a ses emplacements et ne pourra donc plus descendre, étant forcé de rester a trois, rendant la figure complètement fausse.
De plus, si la longueur opposé est pair, la case en face sera alors constructible mais également une sortie.\\
Ce qui nous amène a une autre propriété:\\
\prop{Chaque case externe non-coin appartenant a un ensemble constructible aura en face d'elle une case appartenant elle aussi a l'ensemble constructible.}
}
\end{document}