Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Как решить задачу
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

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

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com