Kombinatorik: Övertäckning av brickor
Frågan lyder:
Det är hur lätt som helst att övertäcka ett16×16-rutnät med1×4-brickor på ett sådant sätt att 32 av brickorna ligger horisontellt och 32vertikalt. Men, om det ska vara olika antal horisontella och vertikala brickor, vilken är den minsta möjliga differensen mellan dessa två tal?
Min tanke var att :
Om en 1x4 bricka skulle läggas vertikalt så kommer hela den 4x4rutan att behöva läggas med vertikala brickor för att kunna fylla ut tomrum-met. Detta upprepas med varannan horisontellt och varannan vertikalt tillsman kommer till den sista 4x4 rutan där man då kan välja att antingen läggabrickorna horisontellt så att det blir lika många horisontella som vertikala,eller att placera fyra vertikala på sista platsen så att det blir fyra mer av dem. Detta resulterar i att den minsta möjliga differensen mellan vertikala och horisontellt lagda brickor blir fyra för att kunna fylla upp hela brädet.
Detta var dock inte helt korrekt så skulle behöva hjälp med att förstå hur man ska lösa detta.
Nu vet jag inte vad som är rätt svar (eller rätt metod), men med din approach blir väl differensen 8, inte 4? Du delar in rutnätet i 16 kvadrater. Minsta möjliga differens är om du har 9 kvadrater av ena sorten och 7 av andra. Fyra brickor i varje kvadrat ger att du har 8 fler i ena riktningen.
Juste det har du rätt i, men funderar även på om det blir rätt svar eller om det skulle finnas en annan lösning då man inte specifikt måste lägga brickorna i 4x4 rutor?
Ditt svar, 28 av den ena och den 36 av den andra, är korrekt, det går inte att få mindre differens, men återstår för dig att bevisa det.
Om du vill ha ledtråd placerar jag den i spoiler här under.
Visa spoiler
Färglägg rutnätet radvis i fyra färger, första raden svart, andra vit, tredje röd, fjärde blå sen börjar du om, femte svart, sjätte vit osv.
Undersök hur de olika sätten att lägga ut brickorna täcker brickor av olika färg. Du bör komma fram till att antalet horisontella och vertikala brickor måste vara delbart med 4.
