Деревня рыцарей и лжецов на карте имеет вид клетчатого квадрата 9×9, в каждой клетке живет один человек – рыцарь или лжец. рыцари всегда говорят правду, а лжецы всегда врут. соседними считаются клетки, примыкающие друг к другу по стороне или углу. каждый житель сказал: среди моих соседей нечётное число лжецов. чётно или нечётно количество лжецов в деревне?

разобьем доску на девять квадратов 3×3. докажем, что в каждом таком квадрате нечетное количество лжецов. рассмотрим жителя из центральной клетки. если он рыцарь, то среди его соседей нечётное число лжецов и значит и во всём квадрате их нечётное число. если он лжец, то среди его соседей - чётное число лжецов, да еще он сам и в итоге в квадрате - нечётное число лжецов. 

так как сумма девяти нечётных чисел нечётна, значит нечётно и общее число лжецов.

 

Пятизначное число имеет вид . всего пятизначных чисел, которые состоят из этих неповторяющихся цифр, 120. на месте десятков тысяч будет любая цифра из пяти, на месте тысяч будет любая цифра из оставшихся четырех, на месте сотен будет любая из оставшихся трех цифр, на месте десятков будет любая из двух оставшихся цифр, на месте единиц будет последняя цифра, следовательно, 5*4*3*2*1= 120 пятизначных чисел, которые составлены из цифр 1, 2, 3, 4, 5 всего пятизначных чисел, которые начинаются с 45, будет 6. на месте десятков тысяч будет только 4, на месте тысяч будет только 5, на месте сотен будет любая из оставшихся трех цифр, на месте десятков будет любая из двух оставшихся цифр, на месте единиц будет последняя цифра, следовательно, 1*1*3*2*1=6 пятизначных чисел, которые начинаются с числа 45. 120-6= 114 пятизначных чисел, которые не содержат одинаковых цифр и не начинаются с числа 45.

Пусть n = 2k n/12 + n^2/8 + n^3/24 = k/6 + k^2/2 + k^3/3 = k/6 * (1 + 3k + 2k^2) = k/6 * (k - 1)(2k - 1) = k (k - 1)(2k - 1) / 6 осталось доказать, что при любом целом k число k (k - 1)(2k - 1) делится на 6. 1)  числа k, k  -  1 - разной чётности, поэтому одно из них делится на 2, а значит, и всё произведение делится на 2. 2) докажем делимость на 3. пусть ни k, ни k - 1 не делятся на 3 (иначе утверждение заведомо верно). тогда k представимо в виде k = 3m + 2, m - целое. подставим такое k в выражение 2k - 1. 2k - 1 = 2(3m + 2) - 1 = 6m + 3 = 3(2m + 1) то, что стоит в скобках, - целое число, поэтому 2k - 1 делится на 3. для завершения доказательства отметим, что если число делится на 2 и на 3, то оно делится и на 6.