Question and Answers Forum

All Questions      Topic List

Permutation and Combination Questions

Previous in All Question      Next in All Question      

Previous in Permutation and Combination      Next in Permutation and Combination      

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

merci

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

Terms of Service

Privacy Policy

Contact: info@tinkutara.com