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

← →
MBo © (2006-06-16 13:27) [0]

1. Медианы AA" и BB" треугольника ABC пересекаются под прямым углом.
BC = 3, AC = 4, найти AB.

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

3. Что больше для вещественных x, sin(cos x) или cos(sin x)?

4. Вася Пупкин стоит на квадратном поле ABCD, и знает расстояния от себя
до углов B - 13м, С - 20м, D - 17м. Как ему найти размер поля?

5. Если числа 2^n и 5^n начинаются с одной и той же цифры, то какая это может быть цифра?

6. Есть 59049 монет (3^10). Среди монет имеется одна фальшивая.
Известно, что фальшивая монета немного тяжелее настоящей.
Сколько нужно взвешиваний на чашечных весах без гирь,
чтобы определить фальшивую монету, если известно,
что во время одного из взвешиваний весы могут показать неверный результат?

7. Вася Пупкин был на бегах, и задумался, сколькими способами,
включая одновременный финиш, 8 лошадей могут прийти к финишу?
(Для двух лошадей A и B, есть 3 варианта - победа A, победа B, равенство)

8. Минутная стрелка часов вдвое длиннее часовой.
В какое время от полудня до следующей встречи стрелок (примерно в 1.05)
расстояние между их концами увеличивается с наибольшей скоростью?

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

10. Сколько существует способов представления числа 50! в виде суммы двух
или более последовательных натуральных чисел?

← →
default © (2006-06-16 13:39) [1]

спасибо, Борис
я уже на пробежку собирался, но отложу её ненадолго:)

← →
Александр Иванов © (2006-06-16 13:46) [2]

5. 0 :)

← →
Александр Иванов © (2006-06-16 13:47) [3]

В смысле n=0

← →
Александр Иванов © (2006-06-16 13:50) [4]

6. 10 взвешиваний. Количество монет делим на три и взвешиваем две из трех кучек.

← →
MBo © (2006-06-16 13:57) [5]

>Александр Иванов © (16.06.06 13:50) [4]
А учел, что весы могут один раз соврать?

>Александр Иванов © (16.06.06 13:46) [2]
>5. 0 :)
Ну это несерьезно ;)

← →
Александр Иванов © (2006-06-16 14:03) [6]

7. 41432

Сначала число перестановок 8 = 8!
плюс:
число сочетания 2 из 8, число перестановок 6,
число сочетания 3 из 8, число перестановок 5,
число сочетания 4 из 8, число перестановок 4,
число сочетания 5 из 8, число перестановок 3,
число сочетания 6 из 8, число перестановок 2,
число сочетания 7 из 8, 1
1

← →
tesseract © (2006-06-16 14:08) [7]

> Александр Иванов © (16.06.06 13:46) [2]

вот до 20 степени, дальше какой-то error :-)

2^5=32 5^5=3125
2^14=16384 5^14=1808548329
2^20=1048576 5^20=1977800241

> 8.

Между концами стрелок? и по какому принципу расстояние считать?

← →
MBo © (2006-06-16 14:08) [8]

>Александр Иванов © (16.06.06 14:03) [6]
>7. 41432
неверно
можно сначала для небольшого числа попробовать, например, для 4

← →
Александр Иванов © (2006-06-16 14:11) [9]

по второму - чему равно a(1)?

← →
MBo © (2006-06-16 14:12) [10]

>Между концами стрелок? и по какому принципу расстояние считать?
По прямой

← →
MBo © (2006-06-16 14:13) [11]

>Александр Иванов © (16.06.06 14:11) [9]
>по второму - чему равно a(1)?
Это тоже надо определить ;)

← →
tesseract © (2006-06-16 14:14) [12]

> 7.

ммм.. У нас число значений мест - 8, степеней свободы места - 3.

3^8=6561 вариантов.

← →
tesseract © (2006-06-16 14:23) [13]

Сорри это всего вариантов распределения лошадей включая все третьи все вторые и тд.

← →
Александр Иванов © (2006-06-16 14:26) [14]

7. 69527?

← →
For kaif (2006-06-16 14:34) [15]

10. 24. По 3,5,7,..49 чисел в каждой.

← →
For kaif (2006-06-16 14:37) [16]

Это тоже надо определить ;)
Тогда a(n)=1, n E N :)

← →
SergP. (2006-06-16 14:39) [17]

> [4] Александр Иванов © (16.06.06 13:50)
> 6. 10 взвешиваний. Количество монет делим на три и взвешиваем
> две из трех кучек.

Не проверял или 10 это правильно если бы весы совсем не врали.
Но если правильно, то учитывая то что весы могут один раз соврать навскидку предположу что 10+4, т.е.14

← →
Bless © (2006-06-16 15:04) [18]

1. AB =2

← →
evvcom © (2006-06-16 15:13) [19]

3. sin(x) и cos(x) изменяются от -1 до 1
при x = (0; pi/2; pi; 3pi/2; 2pi)
cos(sin x) = (1; cos(1)=0,54; 1; cos(1); 1; cos(1))
sin(cos x) = (sin(1)=0,84; 0; -sin(1); 0; sin(1))
В итоге cos(sin x) > sin(cos x). Максимум sin(cos x), конечно больше, чем минимум cos(sin x), но по фазе макс. синуса приходится на макс. косинуса, тогда как мин. косинуса приходится на 0 синуса.

← →
default © (2006-06-16 15:21) [20]

7. 545835?
F(N)=C(N,1)F(N-1)+C(N,2)F(N-2)+...+C(N,N)F(0), F(0)=1
C(n,k)-сочетания из n по k

← →
tesseract © (2006-06-16 15:33) [21]

> 7. 545835?

Столько не может количество вариантов меньше.

На самом деле сущевтует два варианта - лошадь пришла первой, или лошадь не пришла первой (если вместе пришла с кем то, вероятность не меняеться) Итого 2^8= 256 - 1 (какая-то лошадь должна придти). Итого 255 вероятностей.

ЗЫ : DMclient test

← →
DesWind © (2006-06-16 15:43) [22]

Для второй ответ a(2005)=1 ?

← →
default © (2006-06-16 15:44) [23]

tesseract © (16.06.06 15:33) [21]
я рассматривал и варианты: 1,3 лошади пришли первыми, 4,5,7 вторыми и тд
все варианты

← →
tesseract © (2006-06-16 15:49) [24]

> я рассматривал и варианты: 1,3 лошади пришли первыми, 4,
> 5,7 вторыми и тдвсе варианты

перебор. Всего распределения лошадей 2^8 - она пришла или не пришла. Это энтропия или число состояний системы. А тут больше вероянтонстей чем позиций лошадей.

← →
default © (2006-06-16 15:52) [25]

tesseract © (16.06.06 15:49) [24]
я понял задачу так как решил:)
дождёмся судьи он рассудит по справедливости:)

← →
DesWind © (2006-06-16 15:54) [26]

Ответ на пятую 2

← →
DesWind © (2006-06-16 16:04) [27]

> [26] DesWind © (16.06.06 15:54)
> Ответ на пятую 2

плохо, полохо считаю.... 3 )))

← →
DesWind © (2006-06-16 16:06) [28]

Я геометрию забыл... что следует из равенства двух сторон треугольника?

← →
Bless © (2006-06-16 16:08) [29]

> DesWind © (16.06.06 16:06) [28]

Что он равнобедренный :)

← →
DesWind © (2006-06-16 16:11) [30]

> [28] DesWind © (16.06.06 16:06)

Ошибся. Что если равны две стороны у двух треугольников... Но чувствую, что это уже не важно...

← →
evvcom © (2006-06-16 16:45) [31]

> Что если равны две стороны у двух треугольников...

Ничего. Вот если бы еще угол между ними... :)

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

на 1 вроде корень из 5.
Хотя уже запутался.

← →
tesseract © (2006-06-16 17:29) [33]

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

должна быть 0.

← →
MBo © (2006-06-16 18:10) [34]

>default © (16.06.06 15:21) [20]
>7. 545835?
Да, верно

>tesseract © (16.06.06 16:55) [32]
>на 1 вроде корень из 5.
Правильно

решающим 2) и 5)
хорошо бы хотя бы минимальное доказательство

← →
Alx2 © (2006-06-16 18:11) [35]

> [32] tesseract © (16.06.06 16:55)
> на 1 вроде корень из 5.
> Хотя уже запутался.

У меня тоже sqrt(5) в 1-й

← →
tesseract © (2006-06-16 18:15) [36]

> MBo © (16.06.06 18:10) [34]
> >default © (16.06.06 15:21) [20] >7. 545835?Да, верно

Для 8-ми лошадей как-то не стыкуется с теорией чисел. больше 255 имхо не получиться.

← →
tesseract © (2006-06-16 18:19) [37]

> tesseract © (16.06.06 18:15) [36]

не впёр сразу в вопрос теперь дошло.

← →
MBo © (2006-06-16 18:22) [38]

>tesseract © (16.06.06 18:15) [36]
>Для 8-ми лошадей как-то не стыкуется с теорией чисел. больше 255 имхо не получиться.

Для 1,2,3,4,5,6,7 вариантов будет:
1, 3, 13, 75, 541, 4683, 47293

← →
Alx2 © (2006-06-16 18:36) [39]

> 5. Если числа 2^n и 5^n начинаются с одной и той же цифры,
> то какая это может быть цифра?

Тройка.

← →
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]

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

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

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

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

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

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

> "точки А 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,

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

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

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

> 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

← →
SergP. (2006-06-19 21:56) [81]

2 default Вобщем насчет 12 взыешиваний я не прав, но почему-то у меня присутствует уверенность что кол-во взвешиваний не может быть 18, а в крайнем случае, если теоретическое решение [79] с ответом 13 не верно, то ИМХО максимум - это 14, но не более...

← →
SergP. (2006-06-19 21:57) [82]

> если теоретическое решение [79]

Имелось ввиду [80]

← →
SergP. (2006-06-19 22:08) [83]

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

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

SergP. (19.06.06 22:08) [83]
будет свободное время тоже буду думать, задача видится очень интересной
надо её доканать
насчёт 18 сильно не обращай внимания
единственное, может хоть на что-то такие соображения натолкнут(на них я раньше основывался):
допустим мы имеем число монет являющееся степенью двойки:
разбиваем число монет на две кучки(знаем что хотя бы в одной из кучек - фальшивка), действуем по существу всё по той же схеме из [4], но
если в случае деления на три кучки нужно каждый раз делать контрольное взвешивание(если идти по старой схеме взвешивания) до того как весы соврут(чтобы не уйти по ложному пути), то в случае двух кучек контрольное взвешивание делать после каждого взвешивания не нужно

допустим на каком-то из взешиваний весы обманули и мы перешли к работе с кучкой без фальшивых монет - тогда следующее взвешивание даст равенство весов
могла быть и другая ситуация: предыдущее взвешивание было верным, а текущее сорвало ввиде равенства весов
то есть при обнаружении равенства весов весы точно обманули-или на предыдущем взвешивании или на текущем, для определения этого нужно взвешивание ещё раз(и если весы обманули на предыдущем шаге придётся вдобавок делать ещё взвешивание для отброшенной кучки(деля её как обычно пополам)
если обмана не было до конца процесса взвешивания, нужно окончательный результат проверить на истинность(опять используя дополнительные взвешивания)
то есть накладные расходы возникают только в случае обмана или достижения конца процесса без обмана

но у нас число монет это степень тройки, но можно переходить и к двум кучкам
только вот нужно эти переходы выполнять оправдано
а то перейдёшь бывает к двум кучам, а они раза 2-3 поделятся на 2, а потом всё...тут надо соизмерять затраты с результатом

← →
SergP. (2006-06-19 23:53) [85]

> [84] default © (19.06.06 23:04)

6.
Все. Наконец-то понял!!!!
пОСЛЕ 10 ВЗВЕШИВАНИЙ мы можем выделить 21 монету среди которых наверняка есть фальшивая, причем одна из них может быть фальшивой только в том случае когда весы ни разу не соврали (надеюсь это не нужно доказывать). выкидываем нафиг эту монету. у нас остается 20. Берем 7 дополнительных (заведомо нефальшивых монет), либо просто 7 воображаемых монет (пофиг), лепим из них куб, так чтобы воображаемые монеты составляли ребра имеющие общую монету. Далее делаем 3 взвешивания, при каждом взвешивании взвешиваем паралельные слои монет, в которые не входят ни одно из ребер целиком. Получается что в каждом взвешивании участвуют по 8 монет на каждой чашке, (либо по 9 если берем не воображаемые монеты, а реальные). Получается что каждая из наших 20 монет участвует во взвешивании минимум 2 раза. И если мы получаем неравновесие в 2 или 3 взвешиваниях - то мы можем однозначно выявить эту монету, так как неправильное взвешивание было в первых 10 взвешиваниях. Если получаем только один факт неравновесия, значит он неверный, и в первых 10 взвешиваниях небыло неправильных взвешиваний. В таком случае фальшивая монета та, которую мы отбросили нафиг после 10 взвешиваний.

Вобщем все-таки 13 взвешиваний... Как и получилось ранее теоретически...

← →
SergP. (2006-06-20 00:23) [86]

ЕПРСТ... По сути это и есть применение кодов Хемминга (избыточные данные добавляемые к основным с целью выявления и исправления одиночных ошибок), только в данном случае мы имеем дело не с двоичными, а с "троичными битами"

В 6 задаче 13 - правильный ответ

SergP. (20.06.06 00:23) [86]
поздравляю! правда пока время на разбор твоего решения нет, с дипломом вожусь, позже, главно ветке не дать уйти в аут

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