Lyubava
Удален
|
    
1000 студентов имеют 1000 замков.
Первый студент открывает все замки.
Второй студент открывает каждый второй замок.
Третий студент открывает каждый третий замок (если был закрыт) и закрывает каждый третий ( если был открыт).
Четвертый - открывает каждый четвертый (если закрыт) и закрывает каждый четвертый (если был открыт).
И так далее...
Сколько всего замков было открыто?
Заранее огромное спасибо.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 21 окт. 2004 5:14 | IP
|
|
Lyubava
Удален
|
Извините, описка в условии задачи.
Правильно будет : второй студент закрывает каждый второй замок.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 21 окт. 2004 14:40 | IP
|
|
dm
Удален
|
До Вашего исправления можно было подумать, что задача на вероятности. А так получается задача на распутывание рекуррентности.
Я думаю, здесь должен быть и другой (более элементарный) путь решения, но , например, можно решать так:
пусть x_k, y_k - количества открытых и закрытых замков после k-го студента.
Тогда x_k+y_k=1000
x_0=1000 y_0=0
x_1=0 y_1=1000
x_2=500 y_2=500
и т.д., причем рекуррентные соотношения такие:
x_k=x_(k-1) - x_(k-1)/k + y_(k-1)/k
y_k=y_(k-1) - y_(k-1)/k + x_(k-1)/k
то есть вектор-столбец z_k=
x_k
y_k
получается из вектор-столбца z_(k-1)=
x_(k-1)
y_(k-1)
умножением на матрицу: A_k=
1-1/k 1/k
1/k 1-1/k
Теперь осталось посчитать произведение
z_1000 = A_1000 * A_999 * ... * A_2 * A_1 * z_0 .
Ситуация упрощается тем, что у всех матриц A_k есть один и тот же базис из собственных векторов (т.е. не зависящий от k), а именно:
1
1
и
1
-1
Поэтому просто переходим в него, все матрицы диагонализируются, перемножаются они перемножением диагональных элементов.
Ну, и останется вернуться в исходный стандартный базис
1
0
и
0
1
Всё.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 21 окт. 2004 17:16 | IP
|
|
Guest
Новичок
|
Вот решение задачи. На самом деле она оказалась довольно очевидной. Она имеет олимпиадный характер, я конечно в олимпиадах участвовал, но не очень хорошо, опыта маловато, поэтому приходится решать другими методами (методами высшей математики). Гы)))) Хотя ничего сложно в доказательстве не будет.
Известно, что каждое число единственным образом раскладывается в произведение простых. Например : 555 = 3 * 5 * 37.
Так вот, рассмотрим это представление. Пусть N = (p_1}^{k_1}*...*{p_n}^{k_n}. {p}_{1} - это p c индексом 1 и т.д. ^ - это знак степени, {p}_{1},...,{p}_{n} - это простые, которые входят в разложение числа N, a {k}_{1},...,{k}_{n} - их степени (причём все они натуральные числа, то есть отличны от 0). Посмотрим, что будет происходить с замком под номером N. Его будут открывать или закрывать те студенты, номер которых делит число N, то есть номер замка должен делиться на номер студента (возьмём 555 = 3*5*37, его будут трогать только 1, 3, 5, 15, 37, 111, 185, 555 студенты). То есть замок под номером N будет открываться или закрываться столько раз, сколько делителей у числа N. Из представления числа N в виде произведения простых, очевидно следует, что число делителей числа N, которое обозначается как тау(N)=({k}_{1}+1)*...*({k_n}+1). Делителями N будут все числа вида {p_1}^{l_1}*...*{p_n}^{l_n}, где каждое
{l_i}: 0<={l}_{i}<={k}_{i}. Их как раз и будет столько. Теперь заметим, что замок будет закрыт после 1000 студента, если число делителей чётное. Действительно, первый студент открывает N, следующий закрывает, следующий открывает и т.д. Значит нам надо найти все такие N, что тау(N) нечётное, то есть ({k}_{1}+1)*...*({k}_{n}+1) нечётное. Известно, что произведение нескольких чисел чётное, если хотя бы один множитель будет чётным, значит нам нужно, что бы все множители {k}_{i}+1 были нечётными при любых i. Отсюда следует, что {k}_{i} чётное (Если сумма числа и 1 нечётная, то число чётное).
Значит каждое {k}_{i} = 2 * {m}_{i}.
Тогда N = ({p_1}^{2*{m}_{1}})*...({p_n}^{2*{m}_{n}). Отсюда видно, что
N = [({p_1}^{{m}_{1}})*...({p_n}^{{m}_{n})]^2, следовательно, все такие N только полные квадраты, они и только они, очевидно, удовлетворяют условию задачи, то есть после 1000 студента замки с такими номерами будут открыты. Осталось только посчитать их число:
n*n<=1000 => n<=31
Ответ: 31.
Для сомневающихся :
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961.
Всего 31.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 28 окт. 2004 1:08 | IP
|
|
dm
Удален
|
Мда... похоже, я решал другую задачу. У меня k-ый студент закрывал k-ую часть открытых замков и открывал k-ую часть закрытых замков, причем я не учитывал, что эти части должны быть целыми числами.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 28 окт. 2004 19:57 | IP
|
|
|
Форум
Как решить задачу
