Question-147876

Question Number 147876 by puissant last updated on 24/Jul/21

Answered by Olaf_Thorendsen last updated on 24/Jul/21

On raisonne par recurrence. On considere la propriete suivante : “Si on retire une case quelconque a un damier de cote 2^n ×2^n , il est toujours possible de paver le reste du damier avec des triminos coudes en forme de L”. Montrons cette propriete par recurrence sur n. • Cas de base n = 1 : Un damier de cote 2^1 = 2 auquel on retire une case est couvert par exactement un trimino. C′est un cas trivial. • Recurrence : On suppose qu′un damier de cote 2^n auquel on retire une case peut toujours etre pave par des triminos. Montrons que c′est egalement le cas d′un damier de cote 2^(n+1) auquel on retire une case. Un damier de cote 2^(n+1) est forme de quatre carres de cote 2^n . La case retiree est dans exactement un de ces quatre carres. On peut retirer une case a chacun des trois autres carres en placant un trimino au centre du damier de cote 2^(n+1) . On obtient alors un trimino et quatre carres de cote 2^n auxquels une case a ete retiree. Par hypothese de recurrence, ces quatre carres peuvent etre paves par des triminos donc le damier de cote 2^(n+1) aussi. Conclusion : la propriete est bien verifiee pour tous les damiers de cote 2^n et, au cas particulier, pour un damier avec 1024 cases de cote (car 1024 = 2^(10) ).

$$\mathrm{On}\:\mathrm{raisonne}\:\mathrm{par}\:\mathrm{recurrence}. \\ $$$$ \\ $$$$\mathrm{On}\:\mathrm{considere}\:\mathrm{la}\:\mathrm{propriete}\:\mathrm{suivante}\:: \\ $$$$ \\ $$$$“\mathrm{Si}\:\mathrm{on}\:\mathrm{retire}\:\mathrm{une}\:\mathrm{case}\:\mathrm{quelconque} \\ $$$$\mathrm{a}\:\mathrm{un}\:\mathrm{damier}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}} ×\mathrm{2}^{{n}} ,\:\mathrm{il}\:\mathrm{est} \\ $$$$\mathrm{toujours}\:\mathrm{possible}\:\mathrm{de}\:\mathrm{paver}\:\mathrm{le}\:\mathrm{reste} \\ $$$$\mathrm{du}\:\mathrm{damier}\:\mathrm{avec}\:\mathrm{des}\:\mathrm{triminos}\:\mathrm{coudes} \\ $$$$\mathrm{en}\:\mathrm{forme}\:\mathrm{de}\:\mathrm{L}''. \\ $$$$ \\ $$$$\mathrm{Montrons}\:\mathrm{cette}\:\mathrm{propriete}\:\mathrm{par} \\ $$$$\mathrm{recurrence}\:\mathrm{sur}\:{n}. \\ $$$$ \\ $$$$\bullet\:\mathrm{Cas}\:\mathrm{de}\:\mathrm{base}\:{n}\:=\:\mathrm{1}\:: \\ $$$$ \\ $$$$\mathrm{Un}\:\mathrm{damier}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{\mathrm{1}} \:=\:\mathrm{2}\:\mathrm{auquel} \\ $$$$\mathrm{on}\:\mathrm{retire}\:\mathrm{une}\:\mathrm{case}\:\mathrm{est}\:\mathrm{couvert}\:\mathrm{par} \\ $$$$\mathrm{exactement}\:\mathrm{un}\:\mathrm{trimino}.\:\mathrm{C}'\mathrm{est}\:\mathrm{un}\:\mathrm{cas} \\ $$$$\mathrm{trivial}. \\ $$$$ \\ $$$$\bullet\:\mathrm{Recurrence}\:: \\ $$$$ \\ $$$$\mathrm{On}\:\mathrm{suppose}\:\mathrm{qu}'\mathrm{un}\:\mathrm{damier}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}} \\ $$$$\mathrm{auquel}\:\mathrm{on}\:\mathrm{retire}\:\mathrm{une}\:\mathrm{case}\:\mathrm{peut}\:\mathrm{toujours} \\ $$$$\mathrm{etre}\:\mathrm{pave}\:\mathrm{par}\:\mathrm{des}\:\mathrm{triminos}.\:\mathrm{Montrons} \\ $$$$\mathrm{que}\:\mathrm{c}'\mathrm{est}\:\mathrm{egalement}\:\mathrm{le}\:\mathrm{cas}\:\mathrm{d}'\mathrm{un} \\ $$$$\mathrm{damier}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}+\mathrm{1}} \:\mathrm{auquel}\:\mathrm{on}\:\mathrm{retire} \\ $$$$\mathrm{une}\:\mathrm{case}. \\ $$$$ \\ $$$$\mathrm{Un}\:\mathrm{damier}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}+\mathrm{1}} \:\mathrm{est}\:\mathrm{forme} \\ $$$$\mathrm{de}\:\mathrm{quatre}\:\mathrm{carres}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}} . \\ $$$$\mathrm{La}\:\mathrm{case}\:\mathrm{retiree}\:\mathrm{est}\:\mathrm{dans}\:\mathrm{exactement} \\ $$$$\mathrm{un}\:\mathrm{de}\:\mathrm{ces}\:\mathrm{quatre}\:\mathrm{carres}.\:\mathrm{On}\:\mathrm{peut}\:\mathrm{retirer} \\ $$$$\mathrm{une}\:\mathrm{case}\:\mathrm{a}\:\mathrm{chacun}\:\mathrm{des}\:\mathrm{trois}\:\mathrm{autres} \\ $$$$\mathrm{carres}\:\mathrm{en}\:\mathrm{placant}\:\mathrm{un}\:\mathrm{trimino}\:\mathrm{au}\:\mathrm{centre} \\ $$$$\mathrm{du}\:\mathrm{damier}\:\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}+\mathrm{1}} .\:\mathrm{On}\:\mathrm{obtient} \\ $$$$\mathrm{alors}\:\mathrm{un}\:\mathrm{trimino}\:\mathrm{et}\:\mathrm{quatre}\:\mathrm{carres} \\ $$$$\mathrm{de}\:\mathrm{cote}\:\mathrm{2}^{{n}} \:\mathrm{auxquels}\:\mathrm{une}\:\mathrm{case}\:\mathrm{a}\:\mathrm{ete} \\ $$$$\mathrm{retiree}.\:\mathrm{Par}\:\mathrm{hypothese}\:\mathrm{de}\:\mathrm{recurrence}, \\ $$$$\mathrm{ces}\:\mathrm{quatre}\:\mathrm{carres}\:\mathrm{peuvent}\:\mathrm{etre}\:\mathrm{paves} \\ $$$$\mathrm{par}\:\mathrm{des}\:\mathrm{triminos}\:\mathrm{donc}\:\mathrm{le}\:\mathrm{damier}\:\mathrm{de} \\ $$$$\mathrm{cote}\:\mathrm{2}^{{n}+\mathrm{1}} \:\mathrm{aussi}. \\ $$$$ \\ $$$$\mathrm{Conclusion}\::\:\mathrm{la}\:\mathrm{propriete}\:\mathrm{est}\:\mathrm{bien} \\ $$$$\mathrm{verifiee}\:\mathrm{pour}\:\mathrm{tous}\:\mathrm{les}\:\mathrm{damiers}\:\mathrm{de} \\ $$$$\mathrm{cote}\:\mathrm{2}^{{n}} \:\mathrm{et},\:\mathrm{au}\:\mathrm{cas}\:\mathrm{particulier},\:\mathrm{pour}\:\mathrm{un} \\ $$$$\mathrm{damier}\:\mathrm{avec}\:\mathrm{1024}\:\mathrm{cases}\:\mathrm{de}\:\mathrm{cote} \\ $$$$\left(\mathrm{car}\:\mathrm{1024}\:=\:\mathrm{2}^{\mathrm{10}} \right). \\ $$

Commented by puissant last updated on 24/Jul/21

$$\mathrm{merci}\: \\ $$

Facebook Tweet Pin

Leave a Reply Cancel reply