Старый 29.03.2006, 15:34   #27 (permalink)
nik_kg
Увлечённый
 
Аватар для nik_kg
 
Регистрация: 06.02.2005
Адрес: Волгоград
Сообщений: 554
Отправить сообщение для nik_kg с помощью ICQ
Хочется предоставить подробное доказательство первой задачки ...


Пусть 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.



nik_kg вне форума