Узелок 5
Задача. Требуется поставить 3 крестика двум или трем картинам, 2 крестика четырем или пяти картинам и один крестик - девяти или десяти картинам, отмечая одновременно тремя ноликами 1 или 2 картины, двумя ноликами 3 или 4 картины и одним ноликом 8 или 9 картин так, чтобы число картин, получивших оценки, было наименьшим из возможных, а отмеченные картины получили как можно большее число оценок.
Ответ. 10 картин получают 29 оценок, распределенных следующим образом:
X X X X X X X X X 0 X X X X X 0 0 0 0 X X 0 0 0 0 0 0 0 0Решение. Расставив все крестики и заключив в скобки те из них, которые по условиям задачи необязательны, мы получим 10 картин, оценки которых распределены так:
X X X X X X X X X (X) X X X X (X) X X (X)Расставив все нули (но не от начала к концу, как крестики, а в обратном направлении - от конца к началу), мы получим 9 картин с оценками, распределенными так:
(0) 0 (0) 0 0 0 (0) 0 0 0 0 0 0 0 0Единственное, что еще необходимо сделать после этого, - вдвинуть оба клина как можно плотнее друг в друга, чтобы число отмеченных картин было минимальным. Если та или иная необязательная оценка мешает нам загонять клин в клин, мы ее стираем, если же не мешает - оставляем в целости и сохранности. В первом и третьем рядах оказывается по 10 обязательных оценок, а в середине - лишь 7. Следовательно, необходимо стереть все необязательные оценки в первом и третьем рядах обоих клиньев и оставить все необязательные оценки, стоящие в середине.