Дадена е правоъгълна дъска m×nm\times n, разделена на mnmn единични квадратчета. Две квадратчета са съседни, ако имат обща страна, а път е редица от квадратчета, в която всеки две последователни квадратчета са съседни. Всяко квадратче може да бъде оцветено в черно или бяло. Нека NN е броят на оцветяванията, при които съществува поне един черен път от левия край на дъската до десния край, а MM - броят на оцветяванията, при които съществуват поне два непресичащи се черни пътя от левия край до десния край. Докажете, чеN22mnM.N^2\ge 2^{mn}M.
📣НОВО: Добавени задачи от Международната олимпиада по математика 2000-2024
Още задачи при скрол