Пятничные задачки. Вася Пупкин returns...

← →
MBo © (2007-04-13 07:52) [0]

1. Пусть S = 1/2 + 1/4 + 2/8 + 3/16 + 5/32 + ... + Fk/2k + ...,
гдк Fk - k-й член ряда Фибоначчи 1, 1, 2, 3, 5, 8, 13, ... .
Найти значение S.

2. Вася Пупкин в полдень посадил на секундную стрелку часов муху и стал за ней
наблюдать, причем он заметил, что поведение мухи таково:
Если муха обгоняет какую-то стрелку, или ее обгоняет какая-то стрелка
(кроме секундной, у часов есть часовая и минутная стрелки),
то муха переползает на эту стрелку.
Чтобы это занятие не было пустым времяпрепровождением,
он почти по совету Козьмы Пруткова стал считать, сколько она проедет кругов.
Так сколько кругов проедет муха в течение часа?

3. Яхта длиной 6м стоит на двух кильблоках (т.е. точечных опорах), расстояние между которыми 3м.
Вася Пупкин массой 100кг встаёт на нос яхты - яхта уравновешивается на одном кильблоке.
Если же Вася встаёт на корму яхты - яхта уравновешивается на втором кильблоке.
Найти массу яхты.

4. На сабантуйчике Васе Пупкину доверили работать разливающим.
Ему дано 8 стаканов, все наполнены водкой, однако уровень жидкости во всех стаканах разный.
Спрашивается, как уравнять живительную влагу в стаканах, если можно брать любые два стакана
и переливать водку из одного в другой?

5. Имеется расклад в преферансе при игре в мизер:
Первая рука: пика - В, Д трефа - 7, 9 бубна - 10, В, Д, К черва - 7, В.
Вторая рука: пика - 7, 8, 9, 10 трефа - 8 бубна - 7, 8, 9 черва - 8, 9.
Третья рука: пика - К, Т трефа - 10, В, Д бубна - Т черва - 10, Д, К, Т.
Играет, как нетрудно догадаться, вторая рука.
Можно ли вставить второй руке?
(с этим мизером связана история с участием известной личности.
З.Ы. Как ни странно, но не Васи Пупкина :-))

6. Пользуясь элементарной геометрией, найти угол альфа на рисунке
http://mbo88.narod.ru/Image1.gif
http://slil.ru/24223104
(по обеим ссылкам одно и то же, размер 7 кб)

7. Равнобедренный треугольник ABC, основание AC = 12.
Вписанная окружность касается AB в точке M, AC в точке N.
CM и BN пересекаются в точке K, отношение отрезков BK:KN = 4:3.
Найти радиус описанной окружности

8. Как известно, бинарный поиск для поиска в отсортированном массиве A[l..r] работает так:
Находится середина массива m=(l+r) div 2
Если m-й элемент равен ключу поиска, то возвращается индекс m
Если ключ меньше, проводится поиск в левой части, т.е в A[l..m-1], а если больше, то в правой
A[m+1..r]. Если левый индекс становится больше правого - элемент не найден,
возвращается обычно -1.
Васе Пупкину нужно создать таблицу (делается однократно на "большом" компе и заносится в ПЗУ)
из 65535 значений и написать микропрограмму
двоичного поиска в ней для нового нанопроцессора Imbecilon.
Однако обнаружилось, что АЛУ этого процессора, спроектированное небезызвестным
Зильберштуцером, не умеет выполнять операцию деления, да и сдвига тоже.
Можно ли как-то специальным образом организовать данные в таблице, и все-таки выполнять
двоичный поиск (именно его, не хэширование или другие методы) в ней без использования деления?

9. Васе Пупкину нужно взвешивать на рычажных весах предметы дискретного веса,
который может принимать только целые значения до 60 г.
Для этого имеется 6 гирек 1, 2, 4, 8, 16, 32 г.
Вася придумал, как уменьшить количество разновесов до пяти. Какие это могут быть гири?
А Петя Раскладушкин сказал, что можно обойтись и четырьми гирями. Правда ли это?

10. Шёл Зенон по дороге и встретил сначала черепаху, а затем бежавшего
за ней Ахилла. Скорости всех персонажей постоянны. В момент встречи Зенона
с черепахой расстояние от них до Ахилла было 20 метров, а когда Ахилл догнал
черепаху, Зенон удалился от них на 5 метров. Насколько отставал Ахилл
от черепахи в момент его встречи с Зеноном?

11. Вася Пупкин лег спать между 23 и 24 часами, а встал между 8 и 9 часами.
Сколько времени (точно) он проспал, если минутная и часовая стрелки в
момент начала и конца сна поменялись местами?

← →
Alx2 © (2007-04-13 08:02) [1]

1. 2

← →
MBo © (2007-04-13 08:05) [2]

>Alx2 © (13.04.07 08:02) [1]
>1. 2
А школьными методами + использование элементарных свойств ряда Фиб. можно обойтись при решении?

← →
Alx2 © (2007-04-13 08:12) [3]

>MBo © (13.04.07 08:05) [2]
Да, конечно.

(*) F(k)/2^k = (F(k+1)-F(k-1))/2^k = 2*F(k+1)/2^(k+1) -1/2F(k-1)/2^(k-1)

Пусть искомая сумма есть S
Тогда из (*)

S = 2*(S-1/2)-1/2*S

Откуда S=2

← →
MBo © (2007-04-13 08:17) [4]

>Alx2 © (13.04.07 08:12) [3]
ОК.

← →
Alx2 © (2007-04-13 08:24) [5]

8.
Черновая версия:
Можно. Заводим 16-разрядный "путеводитель".
Идем в левую часть - соответствующий бит путеводителя сбрасываем. В правую - устанавливаем его.
Тогда значение путеводителя будет номером элемента.

← →
Alx2 © (2007-04-13 08:28) [6]

К Alx2 © (13.04.07 08:24)
Сорри. Деление я так и не описал.

← →
Alx2 © (2007-04-13 08:31) [7]

8. Как было описано в Alx2 © (13.04.07 08:24)
Делим массив так:
В путеводитель пишем 1 в старший бит. Получаем номер медианного. Если надо идти в левую часть, то старший бит сбрасываем. В правую - оставляем как есть. Потом переходим к следующему биту и работаем аналогично

← →
vasIZmax © (2007-04-13 08:35) [8]

Ради интереса попробую:)
9. 8 ч 20 м.

← →
vasIZmax © (2007-04-13 08:36) [9]

> vasIZmax © (13.04.07 08:35) [8]

зачитался 9 и опечатался.
к 11 думаю ответ: 8 ч 20 м.

ЗЫ. мож повезет)))

← →
MBo © (2007-04-13 08:40) [10]

>Alx2 © (13.04.07 08:24) [5]

Наверно, проще надо, процессор-то - Imbecilon :)
Сравнения, сложения, умножения, присвоения - вот, может, и все, на что он способен

← →
Alx2 © (2007-04-13 08:44) [11]

>MBo © (13.04.07 08:40) [10]
8. То есть вот такой код содержит запретные операции?
const MaskArray: array[0..15] of word = (32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1); function Search(Item: Word; const Data: TArray): Word; var k: Integer; begin Result := 0; for k := 0 to 15 do begin Result := Result or MaskArray[k]; if Item<Data[Result] then Result := Result and (not MaskArray[k]) else if Item=Data[Result] then exit; end; // Не найдено. Тогда вернется номер ближайшего к искомому end;

← →
Alx2 © (2007-04-13 08:47) [12]

>MBo © (13.04.07 08:40) [10]
8. Теперь только сложения и вычитания :))
type TArray = array[0..65535] of integer; const MaskArray: array[0..15] of word = (32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1); function Search(Item: Word; const Data: TArray): Word; var k: Integer; begin Result := 0; for k := 0 to 15 do begin Result := Result + MaskArray[k]; if Item<Data[Result] then Result := Result - MaskArray[k] else if Item=Data[Result] then exit; end; // Не найдено. Тогда вернется номер ближайшего к искомому end;

← →
MBo © (2007-04-13 09:08) [13]

>Alx2 © (13.04.07 08:47) [12]

Верно. Получился оптимизированный бинарный поиск. При отсутствии элемента, правда, лучше -1 возвращать, но модифицировать нетрудно.

Однако есть еще способ с переупорядочением исходного массива, и поиском без вычитаний. Это не будет эффективнее, но в каких-то задачах, вероятно, прием может оказаться полезным.

← →
MBo © (2007-04-13 09:09) [14]

>vasIZmax © (13.04.07 08:36) [9]
>к 11 думаю ответ: 8 ч 20 м.

нет, где-то просчитался

← →
Alx2 © (2007-04-13 09:18) [15]

4. Методом усреднения S[k]=(S[k]+S[k+1])/2 при бесконечном количестве переливаний можно прийти к равенству. :)

← →
boriskb © (2007-04-13 09:21) [16]

MBo ©

5)
Ход чей?
Или независимо от очереди хода?

← →
MBo © (2007-04-13 09:28) [17]

>boriskb
Начало игры, первая рука ходит

>Alx2 © (13.04.07 09:18) [15]
>4. при бесконечном количестве переливаний можно прийти к равенству. :)

;) есть способ за конечное число переливаний.

← →
Bel © (2007-04-13 09:30) [18]

5. Мне кажется, не вставить. На первой руке одной карты не хватает для отжора одной трефы или червы с третьей руки. Хотя, что-то мне подсказывает, что, раз этот вопрос возник, то сунуть можно. Будет интересно узнать ответ...

← →
Elen © (2007-04-13 09:34) [19]

> к 11 думаю ответ: 8 ч 20 м.

А мне кажется 9 часов ровно.

← →
Кабан © (2007-04-13 09:42) [20]

AK____________QJ
QJ10__________97
A_____________KQJ10
AKQ10_________J7
______10987
______8
______987
______98
Если я правильно понял расклад, то не получиться. Разыгрывающий может получить взятку только в черве или трефе, для этого нужно вынести три трефы или три червы по бубне, но разыгрывающий будет видеть какая масть сносится и вынесет соответствующую фоску на 4-ый бубновый ход.

← →
Elen © (2007-04-13 09:43) [21]

> Можно ли вставить второй руке?

Мне чтото подсказывает что этот расклад уже давался когда-то в журнале Наука и жизнь и назывался Мизер Наполеона. Там давалось описание как подсадить мизерующего. Поправьте если ошибаюсь.

← →
MBo © (2007-04-13 09:59) [22]

>Elen © (13.04.07 09:34) [19]
>А мне кажется 9 часов ровно.
нет

>Elen © (13.04.07 09:43) [21]
.. и назывался Мизер Наполеона

Тогда это уже третий вариант авторства :))

← →
Кабан © (2007-04-13 10:22) [23]

более тщательный анализ показал, что я был неправ
отобрав 3 бубны восток может снести 2п,
теперь на ход 4-ой бубной, у разыгрывающего уже нет позиционного преимущества, и он вынужден избавиться от трефы или червы раньше Запада, Восток соответственно избавляется от трех треф или трех червей на 4-ую бубну и две пики

← →
Кабан © (2007-04-13 10:33) [24]

Кстати, при такой игре, разыгрывающий будет вынужден снести пику на 4-ую бубну, чтобы избежать паровоза

← →
Elen © (2007-04-13 10:44) [25]

> MBo © (13.04.07 09:59) [22]
>
> >Elen © (13.04.07 09:34) [19]
> >А мне кажется 9 часов ровно.
> нет

Э-э-э-э я правильно думаю что угол между стрелками в начале сна и в конце сна равен и острый (поскольку в начале сна минутная была между 8 и 9 часами, а в конце сна 23-24 часами)? Так?

← →
MBo © (2007-04-13 10:46) [26]

>Кабан
Отлично.
Итак, получается такая схема
1: *Б, 2: *Б 3: TБ
далее передачка назад
3: 10Ч 1: ВЧ 2: *Ч
далее 2 захода в бубны, пронос пик у третьего,
четвертый заход в бубны - третий сносит не ту масть, что 2, и проносит эту же масть полностью на две пики.

Одна из историй:
"Дело в том, что предложенный выше расклад случился еще в прошлом веке в санкт-петербургском кафе «Доминик». Как вспоминает очевидец, кавалерийский полковник С. Боровой — вся компания, игравшая в преферансовой комнате, считала этот мизер «небитым». Однако, заглянувшая на преферанс строго одетая дама показала (с разрешения игроков) интересный и четкий план... С тех пор любители пульки зовут указанный метод розыгрыша именем этой дамы — знаменитого русского математика Софьи Ковалевской."

второй вариант -
"называется мизером де Голля. История по памяти такова: генерал де Голль (французский президент) играл в преферанс с тремя русскими гастролёрами. Он заказал этот мизер и снёс прикуп "в рожу". Де Голля отпустили с миром, сказав, что мизер не ловится. Де Голль записал себе 10 в пулю и тут же показал, как всё-таки он ловится."

← →
MBo © (2007-04-13 10:49) [27]

>Э-э-э-э я правильно думаю что угол между стрелками в начале сна и в конце сна равен и острый

Если отсчитывать от часовой вправо до минутной, то вначале он будет Fi (>Pi), а в конце 2Pi-Fi

← →
TUser © (2007-04-13 11:01) [28]

9. Пупкину - выкинуть гирю 1г. НАприме 37г. - это 32+4 (мало), но меньше, чем 32+4+2, значит, ровно 32+4+1.

> MBo © (13.04.07 10:49) [27]

Я имею ввиду что острый угол между ними будет одинаковым. Так? Если да то положение минутной можно не учитывать и просто просчитать часы предполагая что он лег в 23 и проспал : 00,01,02,03,04,05,06,07,08 = 9 часов. Или я вру?

5. Дадут за милу душу.
передача по бубне обратная передача по черве 2 хода в бубну с третьей руки несем трефу и в семерочку

А если между обратной передачей по черве добрать пику и еще одну черву то взятки три как с куста

блин трефу с пикой перепутал позорище....
да и все раньше изложили красиво...

>Или я вру?
ага. в 23 и в 8 часов ровно минутная стрелка будет вверху. Как же ее можно не учитывать?

> 9. Пупкину - выкинуть гирю 1г. НАприме 37г. - это 32+4 (мало),
> но меньше, чем 32+4+2, значит, ровно 32+4+1.

Прикольно :) А ещё по-моему можно обойтись пятью гирями, если их вес будет представлять собой степени тройки: 1 г, 3 г, 9 г, 27 г, 81 г. Даже с хорошим запасом можно вешать, до 121 г :) А вот чтобы ещё одну гирю выкинуть - сдаётся мне, что тут уже никакие ухищрения не помогут...

Хотя если использовать метод TUser © (13.04.07 11:01) [28] с двумя не совсем точными взвешиваниями, то наверно можно всё-таки обойтись и 4 гирями: 2 г, 6 г, 18 г, 54 г.

итак,если объединить идеи TUser и Agent13, все-таки можно обойтись 4 весами, используя гири на обеих чашках и отношения <, =, >
Набор 2, 6, 18, 54

4. По поводу переливания водки: можно переливать как угодно, по сколько угодно, или есть какие-то ограничения?

>4. По поводу переливания водки: можно переливать как угодно, по сколько угодно, или есть какие-то ограничения?

можно взять пару стаканов и перелить сколько хочешь из одного в другой, в частности - можно уравнять эту пару

>а случайно не 9 часов 55 мин он спал?
насколько я помню, нецелое число минут получиться должно

Пятничные задачки. Вася Пупкин returns... Найти похожие ветки