Пятничные задачки для brain разминки ;)

← →
Alx2 © (2006-06-16 18:42) [40]

> 2. Последовательность положительных вещественных чисел задана
> так:
> a(0) = 1
> a(n+2) = 2*a(n) - a(n+1), для n = 0, 1, 2, ... .
> Найти a(2005).

Общее решение: a(n)=(1-a(1))/3*(-2)^n+(2+a(1))/3
(-2)^n гасим условием a(1)=1.
Получается, a(n)=1
a(2005)=n

← →
Alx2 © (2006-06-16 18:51) [41]

> [40] Alx2 © (16.06.06 18:42)
> a(2005)=n

Фиг знает что пишу. :)

a(2005)=1

← →
Alx2 © (2006-06-16 18:58) [42]

> Alx2 16.06.06 18:36)
> Тройка.

Вдогонку. Еще и остальные восемь цифр :)

← →
Alexis © (2006-06-16 21:19) [43]

> tesseract © (16.06.06 17:29) [33]
> > 9. Какая 1000-я цифра справа от запятой в десятичном представлении числа
>
> > (1 + Sqrt(2))^3000 ?
>
>
> должна быть 0.

2 MBO & tesseract - а можно небольшой хинт насчет 9 задачи? В ней для решения нужно использовать бином Ньютона либо теорему Тейлора или для получения ответа можно обойтись без них?

← →
default © (2006-06-16 21:49) [44]

6. раз 18?( навскидку говорю )

← →
tesseract © (2006-06-16 21:53) [45]

> ответа можно обойтись без них?

я на вскидку - число получается дробное, и в уже в >1000 степени должно дать на тысячном месте после запятой 0.

← →
default © (2006-06-16 22:19) [46]

6. или даже 19:)
используя контрольные взвешивания стратегией в [4] нужно 10+10 взвешиваний в худшем случае
сокращение маленькое уж больно:)

← →
Alx2 © (2006-06-16 23:02) [47]

> 9. Какая 1000-я цифра справа от запятой в десятичном представлении
> числа (1 + Sqrt(2))^3000 ?

Ответ: 9.

Решение:
(1+sqrt(2))^n = a[n]*sqrt(2)+b[n];
a[1] = 1; b[1]=1

a[n+1]=a[n]+b[n]
b[n+1]=2*a[n]+b[n]

Отсюда
sqrt(2)*a[n] = ((sqrt(2)+1)^n - (1-sqrt(2))^n) / 2
b[n] = (sqrt(2+1)^n+(1-sqrt(2))^n)/2

b[n] - целое число по условию.
разность a[n]-b[n] есть (1+sqrt(2))^(-n)*(-1)^(n+1).
Это значение всегда меньше 1/2 по модулю.
Значит, b[n] является ближайшим целым числом к числу a[n]*sqrt(2)
При n=3000 значение a[n]-b[n] отрицательно и примерно равно -4.7*10^(-1149)

Следовательно, дробная часть числа a[n]*sqrt(2) примерно есть 1-4.7*10^(-1149). В интересующей нас области (тысячный знак справа от десятичной запятой) идет серия девяток. Вообще, имеется цепочка девяток длинны > 1140

Итак, ответ 9.

← →
Alx2 © (2006-06-16 23:03) [48]

> разность a[n]-b[n] есть (1+sqrt(2))^(-n)*(-1)^(n+1).

Описка. Следует читать как разность sqrt(2)a[n]-b[n] есть (1+sqrt(2))^(-n)*(-1)^(n+1).

← →
DesWind © (2006-06-16 23:09) [49]

По второму локазательства уже не приведу, но может прокатит за метод мат индукции))) Я решал перенеся половину левой части в правую, вобщем сумма след. двух членов послед равна произведению данного на 2, а при n=0 a=1, вот и все мое доказательство )

← →
Alx2 © (2006-06-16 23:12) [50]

3. Простая и уже ранее есть решение.
Приведу таки свое. cos(sin(x)) - всегда положителен. sin(cos(x)) - иногда :)

← →
DesWind © (2006-06-16 23:36) [51]

А 4 решил кто-нить? Мнеб интерсно былоб узнать как. Я залез на википедию, прочитал все про треугольники.... Но... Остановился на рассширенной теореме Пифагора, но не хватает косинуса...

← →
tesseract © (2006-06-16 23:41) [52]

> Пифагора, но не хватает косинуса...

доп треугольник пристраивал? не зря там ТРИ стороны даёться.
Теория есть но слишком много синусов и косинусов:-)

← →
DesWind © (2006-06-16 23:43) [53]

> доп треугольник пристраивал

Не успел... Пятница))))

← →
DesWind © (2006-06-16 23:44) [54]

Точнее Тяпница

← →
tesseract © (2006-06-16 23:48) [55]

> DesWind © (16.06.06 23:44) [54]

кстати, там не Пифагор, у него без косинусов. долго вспоминал как синус(90-адьфа) разложить, но рабочий день кончился :-).

Где-то у меня книга валялась "Школьные олимпиады по информатике" 1987 ГВ. Найду что-нибудь выложу :-)

← →
DesWind © (2006-06-17 00:19) [56]

> [55] tesseract © (16.06.06 23:48)

Это тоже было ) К этому пришел через теорему синусов... В итоге, чет мне больше приглянулась теорема Пифагора... Вобщем, что-то упускаю я, что-то незначительное и в тоже время важное...

← →
DesWind © (2006-06-17 00:23) [57]

> кстати, там не Пифагор,

Зайди на википедию, мож я и ошибаюсь, но есть там формУла, кторая называется "расширенной теоремой Пифагора", и там неважно какой это треугольник.

← →
default © (2006-06-17 11:50) [58]

4. sqrt(369)~19.2м ?

← →
Bless © (2006-06-17 12:15) [59]

MBo © (16.06.06 18:10) [34]
А
Bless © (16.06.06 15:04) [18] 1. AB =2

неправильно?

← →
default © (2006-06-17 12:31) [60]

Bless © (17.06.06 12:15) [59]
см. [34], партия говорит, что неправильно

← →
Bless © (2006-06-17 12:43) [61]

Тьфу ты, точно. Не заметил.

← →
default © (2006-06-17 13:09) [62]

к [58]
на всякий случай на бумаге нарисовал пропорциональную картинку
все размеры сошлись

← →
Alexis © (2006-06-17 13:30) [63]

> default © (17.06.06 11:50) [58]
> 4. sqrt(369)~19.2м ?

S=369 кв.единиц
Да, у меня тоже столько же. Я через координатную систему решал, а ты как? Расстояние до точки А 58 единиц получилось?

← →
default © (2006-06-17 13:42) [64]

Alexis © (17.06.06 13:30) [63]
"Я через координатную систему решал, а ты как?"
через синусы, косинусы, теорему Пифагора, основное тригонометрическое тождество, последнее освобождало от синусов и косинусов и дело иметь приходилось с обычными алгебраическими уравнениями, квадратными
"точки А 58 единиц получилось?"
каких единиц? я не считал это расстояние, судя по картинке на бумаге оно где-то 7.8м

← →
Alexis © (2006-06-17 13:49) [65]

> через синусы, косинусы, теорему Пифагора, основное тригонометрическое
> тождество, последнее освобождало от синусов и косинусов
> и дело иметь приходилось с обычными алгебраическими уравнениями,
> квадратными

> "точки А 58 единиц получилось?"
> каких единиц? я не считал это расстояние, судя по картинке
> на бумаге оно где-то 7.8м

Пардон, не 58 конечно, а расстояние до точки А=sqrt(58)=7.61...

(B) x^2 + (y-a)^2 = 13^2,
(C) (x-a)^2 + (y-a)^2 = 20^2,
(D) (x-a)^2 + y^2 = 17^2,

где а=сторона квадрата, х, у - координаты точки, где стоит Вася Пупкин. Три уравнения-три неизвестных :)

← →
Alexis © (2006-06-17 15:43) [66]

8).
В момент времени t=360/11 минуты ~ 32.(72) после полудня. До этого времени скорость удаления стрелок друг от друга растет. Так?

← →
Alexis © (2006-06-17 16:13) [67]

10).
Могу предположить что 50! нечетным количеством послед.чисел можно представить (1*3*5*7*...*49 - 1) / 2 способами и двумя послед.числами 50! представить нельзя.
Осталось подумать, как представить 4, 6, 8 и т.д. числами :)

← →
default © (2006-06-17 16:20) [68]

Alexis © (17.06.06 13:49) [65]
никаких проблем при решении этой системы не возникает?
всё-таки уравнения нелинейные

> default © (17.06.06 16:20) [68]
> Alexis © (17.06.06 13:49) [65]
> никаких проблем при решении этой системы не возникает?
> всё-таки уравнения нелинейные

Нет не возникает, впрочем скобки там и не надо почти раскрывать. Я делал так:
(1) это (С)-(D)
(2) это (С)-(B)
дальше смотрим (B)+(D)-(C)
и формируем (2) - (1) которое возводим в квадрат а дальше все там очевидно :)

> default © (17.06.06 17:30) [70]
> Alexis © (17.06.06 17:19) [69]
> тогда твой способ самый простой:)
> всю задачу опошлил:)свёл до банальности:)

Так и знал - провинция-с, не поймут! :)

Alexis © (17.06.06 17:50) [71]
просто тут люди в такие-ли дебри лезли сэ тими синусами и косинусами, я сам страниц 6 извёл на это, только потом решение получилось - тривиальным его не назвать, хотя и особенно хитрого ничего нет, но у тебя!
как школе! три уравнения по теореме Пифагора с тремя неизвестными и задаче конец:) обидно за задачу:)

← →
SergP. (2006-06-17 21:43) [73]

> [44] default © (16.06.06 21:49)
> 6. раз 18?( навскидку говорю )

12 точно должно хватить... Насчет того хватит ли 11 - не знаю...

Вобщем нужно сделать 12 замеров так, чтобы по любым 10 из них можно было однозначно определить фальшивую монету.
Тогда в минимум в 11 комбинациях (10 из 12) мы должны получить одинаковый результат, который и будет верным.

SergP. (17.06.06 21:43) [73]
ты располагаешь процедурой решающей задачу за 12 взвешиваний?
я пока вижу оптимизацию в поиске некоторой оптимальной схемы деления то на три кучки, то на две(когда делим на две кучки контрольное взвешивание проводится только когда весы соврут)

← →
SergP. (2006-06-17 23:32) [75]

> [74] default © (17.06.06 22:26)

Я пока еще не совсем уверен в том что 12 взвешиваний нужно... Нужно еще подумать над этим. Хотя думаю что должно хватить 12.

Первоначально была мысль что здесь нужно применить коды Хемминга. Потому подумал что нужно 14 взвешиваний. Но что-то не получилось их применить.

Alx2 © (16.06.06 23:02) [47]
> 9. Какая 1000-я цифра справа от запятой в десятичном представлении
> числа (1 + Sqrt(2))^3000 ?
>Ответ: 9.

Верно

>default © (17.06.06 11:50) [58]
>Alexis © (17.06.06 13:30) [63]
>4. sqrt(369)~19.2м ?

Верно

>Alexis © (17.06.06 15:43) [66]
>8).
>В момент времени t=360/11 минуты ~ 32.(72)

Нет

>Alexis © (17.06.06 16:13) [67]
Хинт - нечетные числа действительно могут понадобиться при решении задачи

2.
из условия
"a(n+2) = 2*a(n) - a(n+1), для n = 0, 1, 2, ..." имеем
2*a(n)=a(n+1)+a(n+2), для n = 0, 1, 2, ..., т.е. удвоение любого члена последовательности должно равняться сумме двух последующих членов; очевидно, что недопустимо выполнение a(n+2)=2*a(n)-a(n+1) < 0, ибо по условию числа последовательности - положительные
будем рассматривать даже чуть более общую задачу - и первый член последовательности неопределён
покажем, что только в случае когда первые два члена последовательности равны друг другу, последовательность задачи можно построить
пусть имеется послед-ть
a,b,c,d,e,f,g,h,i,....
c=2a-b (1); e=2c-d (2); d=2b-c (3);
(3) подставляем в (2) и имеем e=2c-(2b-c)=3c-2b (4);
в (4) теперь подставляем (1), имеем
e=3(2a-b)-2b=6a-5b (5);
теперь из (5) вычитаем (1), имеем e-c=(6a-5b)-(2a-b)=4(a-b)
теперь делаем ключевой вывод: если a<b, то e-c=4(a-b)<0
c-d=(2a-b)-(2b-c)=2a-3b+c=2a-3b+(2a-b)=4(a-b), то есть c<d при a<b и значит рассуждения применимы вновь, теперь уже будем иметь g-e=4(c-d)=16(a-b), отсюда понимаем что если некий член послед-ти меньше следующего, то члены последовательности начиная с члена после указанных двух шагая черех один уменьшаются причём уменьшение это увеличивается, что означает что в конце концов мы получим отрицательный член последовательности, что недопустимо
стало быть, в частности, первый член послед-ти не может быть меньше второго
если же первый член послед-ти больше второго, то получаем
a>b, 2a=b+c; a+a=b+c,a-b=c-a, поскольку a-b>0 в силу a>b, то c-a>0,c>a
а поскольку c>a, а a>b в силу закона транзитивности c<b, b<c и получаем что второй член посл-ти меньшет третьего и из предыдущего это значит что послед-ть нереализуема
случай a=b тривиальный, только он и даёт построить последовательность
для указанной же более узкой задачи a=b=1 и a(2005)=1

← →
SergP. (2006-06-19 21:32) [79]

> я пока вижу оптимизацию в поиске некоторой оптимальной схемы
> деления то на три кучки, то на две(когда делим на две кучки
> контрольное взвешивание проводится только когда весы соврут)

Ладно. Есть еще такой метод: Делим все на 3 кучи. 2 из них взвешиваем. Далее снова делим исходную кучу на 3 но уже другим образом (каким - думаю понятно, просто долго объяснять) и т.д. 10 раз.
В результате мы можем выбрать 21 монету среди которых наверняка есть фальшивая, т.е.:

f(59049)=10+f(21)

← →
SergP. (2006-06-19 21:52) [80]

6. Еще такой вариант есть:

После n-взвешиваний мы можем выделить 59049*(2*n+1)/(3^n) монет среди которых наверняка есть фальшивая.

Теперь решая уравнение 59049*(2*n+1)/(3^n)=1 находим что n=13

правда есть небольшие сомнения касающиеся методики взвешивания при количестве взыешиваний более 10

Пятничные задачки для brain разминки ;) Найти похожие ветки