Хочется предоставить подробное доказательство первой задачки ...
Пусть n - количество дверей.
1-й изменяет статус всех дверей (т.к. 1 делит n для любого n)
2-й изменяет статус четных дверей (2 делит n)
(2,4,6,8,10,12,14,16,...)
3-й изменяет статус каждой 3-й двери (3 делит n)
(3,6,9,12,15,...)
......
n-й изменяет статус только n-й двери (n делит только n)
Т.е. чтобы слуга изменил номер двери, НОМЕР СЛУГИ должен быть делителем НОМЕРА ДВЕРИ.
Далее. Если дверь меняет свой статус четное количество раз, то она в итоге будет закрытой; если же нечетное - открытой.
Таким образом, задача сводится к следующей: найти все такие числа, которые имеют НЕЧЕТНОЕ количество делителей. Эти числа и будут номерами открытых дверей.
ПРЕДЛОЖЕНИЕ: Числа, являющиеся полными квадратами целых чисел и только они имеют нечетное количество делителей.
Доказательство:
Т.к. тривиальные делители любого числа (1 и само это число) не меняют четности делителей, то мы их не учитываем.
I. Пусть b не является полным квадратом ни одного целого числа.
Пусть a делит b. Тогда существует c (единственное) такое что b=ac.
Но тогда c делит b.
а<>с, т.к. иначе бы b=a^2, т.е. b - полный квадрат числа а, что противоречит условию.
Следовательно, для каждого делителя числа b найдется единственный парный ему делитель. Т.е. число делителей четно.
II. Пусть теперь b является полным квадратом некоторого числа a.
Тогда b=a*a. Т.е. a делит b.
Любой другой делитель числа b будет иметь парный делитель. Т.к. иначе b=c*c для некоторого c, но тогда c=a.
Таким образом b имеет только один делитель у которого нет пары. Т.е. число делителей у b - нечетно.
Все a,b,c из множества Z.
Доказано.
Итак. Остается выяснить сколько чисел меньших либо равных n являются полными квадратами. Для n=1000 их будет 31.
31*31=961.