Combi?
Opgave - IMO 1974 dag 2 vraag 1
Beschouw de ontbinding van een $8 \times 8$ schaakbord in $p$ niet-overlappende rechthoeken, onderworpen aan de volgende voorwaarden:
(i) Elke rechthoek heeft evenveel witte als zwarte vierkanten.
(ii) Als $a_i$ het aantal witte vierkanten in de $i$-de rechthoek is, dan geldt $a_1 < a_2 <
· · · < a_p$.
Vind de maximale waarde van $p$ waarvoor een dergelijke ontbinding
mogelijk is. Bepaal voor deze waarde van $p$ alle mogelijke rijen $a_1, a_2, · · · , a_p$.
- login om te reageren
Oplossing
De oppervlakte van rechthoek $a_n=2a_n$ dus moeten we 32 verdelen in zoveel mogelijk verschillende positieve gehele getallen. Dan moeten we zien dat de gevonden partities ook werk dadelijk een $8\times 8$ bord kunnen verdelen.
Claim:32 kan niet verdeeld worden in 8 of meer (strikt) positieve gehele getallen.
Daar de getallen allemaal verschillend zijn, en strikt positief, is de som minstens $36$ voor $8$ of meer waarden.
Een verdeling in 7 delen is mogelijk: {1,2,3,4,5,8,9}, dus moeten we alle mogelijke verdelingen van 32 in 7 delen vinden.
Ten eerste moeten we opmerken als de eerste 6 getallen minimaal zijn, namelijk: (1,2,3,4,5,6,$n$) kan $n$ maximaal 11 zijn. Maar 11 zelf werkt niet omdat het rechthoek dat 11 representeert zal een zijde 11 hebben, en dat past niet in ons bord. Dus is onze grootste mogelijke waarde 10.
We zullen i.p.v. 7 cijfers zoeken uit (1,2,3,4,5,6,7,8,9,10) die som 32 geven, 3 cijfers zoeken die som 23 geven. Omdat $6,7,8< 23$ moet 9 of 10 zeker in de selectie van 3 cijfers zitten.
Stel een verdeling van 23 heeft zeker 10, dan moeten we twee cijfers vinden die som 13 geven. We krijgen dan: (4,9) , (5,8) , (6,7). Bij andere gevallen krijgen we een getal groter dan 10, of 10 dubbel.
Stel een verdeling van 23 heeft zeker 9, dan moeten we twee cijfers vinden die som 14 geven. We krijgen dan: (6,8). Bij andere gevallen krijgen we een getal groter dan 9 (we hebben de gevallen met 10 al bekeken), of een getal dubbel.
Dit geeft ons dan de volgende verdelingen van 32: (1,2,3,5,6,7,8), (1,2,3,4,6,7,9), (1,2,3,4,5,8,9), (1,2,3,4,5,7,10).
Een rechthoek verdeling van het schaakbord van deze verdelingen is zeer makkelijk te vinden, er zijn veel mogelijkheden voor elke verdeling.
Voorbeelden staan getekend op ML.