Спасибо!
Кажется, наоборот, в восьмой поменяли условие. Там сначала предлагалось найти (всего лишь) число Рамсея R(3,3,3,3), тогда как в википедии Числа Рамсея написано, что известны значения лишь двух многоцветных (число цветов > 2) чисел Рамсея, а именно, R(3, 3, 3) = 17 и R(3, 3, 4) = 30. После изменения условия (нет вершин с ребрами всех четырех цветов) как раз из R(3, 3, 3) = 17 стала понятна нижняя оценка задачи 8: можно совсем не пользоваться четвертым цветом (раскраска есть в этой же статье вики), раскрасить K16 в три цвета, и условия задачи выполнятся. Эту оценку я и отправил, доказательства, что нельзя больше, у меня нет. Опять две задачи из разряда нерешенных проблем  А в девятой удалось просто найти статью про проблему двух фальшивых монет, где приведен факт существования алгоритма за 8 взвешиваний, самого алгоритма нет.

Статья
В статье, правда, рассматривается задача найти две фальшивые монеты, тяжелые или легкие - неизвестно, но не требуется определить, какие именно, тяжелые они или легкие. Не знаю, существенно ли это, пришлось предположить, что для больших n нет. Из таблицы 1 следует, что 8 взвешиваний хватает даже для n<=81. Возможно, что в процессе доказательства там конструируется и алгоритм, но я, конечно, не стал вникать - там зубодробительная математика пошла. По-прежнему не понимаю, зачем давать такие задачи.