Пусть в пер­вый цвет по­кра­ше­ны клет­ки диа­го­на­ли, иду­щей из ле­во­го верх­не­го угла в пра­вый ниж­ний. Обо­зна­чим через C_i мно­же­ство цве­тов, в ко­то­рые по­кра­ше­ны клет­ки i-й стро­ки, рас­по­ло­жен­ные левее диа­го­на­ли еди­нич­но­го цвета. До­ка­жем, что при Дей­стви­тель­но, клет­ка, рас­по­ло­жен­ная в i-й стро­ке и j-м столб­це, имеет цвет, не вхо­дя­щий в Но в такой же цвет по­кра­ше­на и клет­ка, рас­по­ло­жен­ная в j-й стро­ке и i-м столб­це, а ее цвет вхо­дит в C_j. Таким об­ра­зом, мно­же­ства C₁, C₂, ..., C₂₀₁₆  — раз­лич­ные под­мно­же­ства мно­же­ства Тогда их не более, чем 2^k штук. Стало быть,

По ин­дук­ции по­ка­жем, как тре­бу­е­мым об­ра­зом по­кра­сить доску в k цве­тов. Этого будет до­ста­точ­но, по­сколь­ку, оста­вив лишь стро­ки с 1-й по 2016-ю и столб­цы с 1-го по 2016-й, мы по­лу­чим доску 2016 × 2016 с тре­бу­е­мой по­крас­кой.

База оче­вид­на, по­сколь­ку доску можно по­кра­сить в один цвет. Пе­ре­ход от k к Если мы уже умеем кра­сить тре­бу­е­мым об­ра­зом доску то доску по­кра­сим так: раз­ме­стим две копии доски одну в левом верх­нем угле, дру­гую в пра­вом ниж­нем, а осталь­ные клет­ки по­кра­сим в -й цвет.

Ответ: 11.