Относно зад. 9. Кои са основите в трапеца AB и CD или AD и ВС. Нашите означения са в посока обратна на часовниковата стрелка, но при повечето държави са по посока на часовниковата стрелка.
Задача 10.
Ще наричаме оранжево-черните квадрати 2×2, „плочки”.
А) Ще докажем, че за всяко естествено число n ≥ 3, съществува такова покритие, че главния диагонал на таблицата – от най-долното ляво, до най-горното дясно квадратче е оцветен в черно, а всички останали квадратчета са оцветени в оранжево. При такова покритие има точно n черни квадратчета.
Доказателството ще извършим по индукция.
1) Нека n = 3.
Първа плочка – в горния ляв ъгъл:
ОЧП
ЧОП
ППП
П – означава празно квадратче.
Втора плочка – в долния десен ъгъл:
ОЧП
ЧОЧ
ПЧО
Трета плочка – в долния ляв ъгъл:
ОЧП
ОЧЧ
ЧОО
Четвърта плочка – в горния десен ъгъл:
ООЧ
ОЧО
ЧОО
Показахме как се реализира търсеното покритие при n = 3.
2) Да допуснем, че твърдението е в сила за някое n = k ≥ 4. Ще покажем, че квадрат (к+1)×(к+1) може да се покрие с плочки така, че само главния му диагонал (долу, ляво – горе, дясно) да е черен.
Първо поставяме две плочки, едната най-горе вляво, а другата най-долу вдясно, така че най-горното ляво и най-долното дясно квадратчета да бъдат покрити в оранжево.
След това, според индуктивното предположение, долният ляв квадрат с размери k×k може да бъде покрит така, че само главния му диагонал да е черен. Получаваме покритие от вида:
ОЧПП . . . ПППП
ОООО . . . ООЧП
ОООО . . . ОЧОП
ОООО . . . ЧООП
. . . . . . . . . . . .
ОООЧ . . . ОООП
ООЧО . . . ОООП
ОЧОО . . . ОООЧ
ЧООО . . . ОООО
Накрая, покриваме горният десен квадрат с размери k×k така, че само главния му диагонал да е черен.
По този начин получихме покритие на квадрат (к+1)×(к+1), при което само главния му диагонал е черен, с което твърдението е доказано.
Б) Да допуснем, че съществува покритие с по-малко от n черни квадратчета. Тогава в таблицата има ред, в който няма нито едно черно квадратче, т.е. всички квадратчета в този ред са оранжеви (в противен случай черните квадратчета ще са не по-малко от n).
Нека означим квадратчетата от този ред, от ляво надясно, с К1, К2, . . . , Кn.
Нека П1 е най-горната плочка, която покрива К1. П1 покрива и К2, но П1 не може да бъде най-горна плочка за К2, защото в такъв случай К2 ще бъде черно.
Нека П2 е най-горната плочка, която покрива К2. П2 не може да покрива К1, защото в противен случай тя щеше да бъде най-горна плочка за К1, а не П1. Следователно П2 покрива К3.
П1 покрива К1 и К2 и е най-горна плочка за К1, но не е най-горна плочка за К2, а П2 покрива К2 и К3 и е най-горна плочка за К2.
Следователно плочките П1 и П2 покриват К2 и П2 е поставена над П1.
С аналогични разсъждения достигаме до извода, че за всяко k = 2, 3, . . . , n-1, плочката Пk, която е най-горна плочка за квадратчето Кk, покрива квадратчетата Кk и Кk+1 и е поставена над плочката Пk-1, която покрива квадратчетата Kk-1 и Кк.
Нека разгледаме плочката Пn-1. Tя покрива Кn-1 и Кn и е най-горна за Кn-1. Частта от плочката Пn-1, която покрива Кn е черна.
Следователно трябва да съществува плочка Пn, която покрива Кn и е най-горна за Кn, но в такъв случай Пn ще бъде най-горна и за Кn-1, a не Пn-1.
Достигнахме до противоречие. Следователно, във всеки ред трябва да има поне по едно черно квадратче, откъдето следва, че черните квадратчета трябва да са най-малко n на брой.
В) Броят на квадратчетата в таблицата е n2.
С разсъждения аналогични на тези в подусловие Б), можем да достигнем до извода, че в таблицата трябва да има поне n оранжеви квадратчета, а с разсъждения аналогични на тези в подусловие А), можем да конструираме таблица, в която има точно n на брой оранжеви квадратчета.
Следователно, максималния брой черни квадратчета е n2 – n = n×(n – 1).