Question

решите плиз.25 баллов за решение

Answer 1

Т.к. j-ое привидение меняет состояние сундуков с номерами кратными j, то k-ый сундук будет менять свое состояние столько раз, сколько есть делителей числа k меньших 1000. Поэтому после 1000-го приведения, k-ый сундук останется открытым, если количество его делителей будет нечетным числом. Если $k=p_1^{m_1}p_2^{m_2}cdotldotscdot p_r^{m_r}$, где $p_i$ - различные простые, то количество делителей числа k (обозначается $tau(k)$) равно $tau(k)=(m_1+1)(m_2+1)cdot ldotscdot(m_r+1)$. Это число будет нечетным, только если каждое $m_i$ - четное, т.е., когда k - полный квадрат. Итак, открытыми останутся сундуки,  номера которых являются полными квадратами, а значит их количество равно $[sqrt{1000}]=31.$