Интересные задачи на собеседованиях

dens

На многих собеседованиях предлагают решить различные задачи. Поделитесь задачами с собеседований или нестандартными вопросами.
p.s. меня как-то спросили при устройстве в "Агаву": "Назовите 3 причины, почему канализационной люк круглый."

pashushkan

На многих собеседованиях предлагают решить различные задачи. Поделитесь задачами с собеседований или нестандартными вопросами.
p.s. меня как-то спросили при устройстве в "Агаву": "Назовите 3 причины, почему канализационной люк круглый."
про люк давно слышал, что в МБА такое спрашивали.
это оптимальная форма чтоп не проваливался.

stm7929259

это оптимальная форма чтоп не проваливался.
Да ладно, неужели?
Ты уравнение Лагранжа в колодце небось решал?
Коли ты слышал это на МБА - аргументируй. Мой довод: люк в виде равностороннего треугольника - лучший вариант для люка. Опровергни

philnau

[math]$c_0$ - последовательности, сходящиеся к $0$,  $c$ - просто сходящиеся последовательности  Норма на обоих пространствах равномерная $= sup |x_i|$.  Существует ли линейная непрерывная биекция между этими пространствами $с <-> c_0$?   [/math]

dunaeva81

Вот что пишет википедия:
Крышки канализационных люков обычно делают круглой формы, так как круглая крышка не может повернувшись провалиться в канализационный люк. Крышки круглой формы также легче всего изготавливать.

verse3e3

классически эта задача про люк ориентирована не на поиск правильного ответа, а на оценку креативных способностей, типа "круглую крышку легче катить рабочим"
задача посложнее - как м&мs покрывают глазурью так, что не остается никаких следов

ETrohkina

нигде не накосячил?

verse3e3

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

dunaeva81

В треугольную дырку хуёвей залезать
приблизительно одинаковой площади

geva

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

beer-for-bear

задача посложнее - как м&мs покрывают глазурью так, что не остается никаких следов
В барабане специальном, они там крутятся и равномерно покрываются глазурью

geva

маккинзи любит давать задачи, которые имеют два решения: простое, но до него нужно догадаться, и технически сложное
например: дан куб с ребром 10, составленный из кубиков с ребром 1 как кубик-рубика. этот куб целиком окунают в краску...сколько маленьких кубиков не покрасилось (хотя бы одной гранью)
Куб 9*9*9 не покрасился, то есть ээ.. ща калькулятор достану... 729 кубичков
Пысы: 8*8*8, конечно

beer-for-bear

дан куб с ребром 10, составленный из кубиков с ребром 1 как кубик-рубика. этот куб целиком окунают в краску...сколько маленьких кубиков не покрасилось (хотя бы одной гранью)
если как кубик рубика, то все

dunaeva81

Пысы: 8*8*8, конечно
скорее имелось ввиду, как ты считать будешь: посчитаешь, количество покрашенных (сложный) или отсечешь по грани и посчитаешь непокрашенные (простой)

verse3e3

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

verse3e3

нет, простой, это отсечь все покрашенные и понять, что получил куб 8*8*8, наверно это и имел
Upd ты наверно тоже это имел в виду?

geva

После учебы на мехмате вообразить куб из тысячи частей, окунуть его, и рассечь, все в 3Д - на это требуется не больше секунды :)

timohatimoha

выстреливают, естественно, правильный вариант

beer-for-bear

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

geva

ну я просто видела как все эти глазированные конфеты делаются, поэтому ответ знаю
А букву как на них рисуют?

verse3e3

ок, тогда задача еще сложнее, для математиков:
есть пруд и утка в центре, вокруг пруда бегает дракон и его скорость в 4 раза больше скорости утки. он бежит на утку и не умеет плавать...сможет ли утка выбраться из воды и не быть съеденной драконом

dunaeva81

нные и понять, что получил куб 8*8*8, наверно это и имел
Upd ты наверно тоже это имел в виду?
отсечь покрашенные можно по разному: посчитать сколько было покрашенных (типа 10*10*2+8*10*2+8*8*2=488 а можно понять, что не окрасился "внутренний" куб (типа понять сразу, что грань внутреннего куба равна 8)

beer-for-bear

А букву как на них рисуют?
штампом

1853515

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

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

geva

таких фигур (которые в любом направлении имеют одинаковую "ширину") вообще-то дохуя бесконечно много, так что это не аргумент
ты не прав

geva

ок, тогда задача еще сложнее, для математиков:
есть пруд и утка в центре, вокруг пруда бегает дракон и его скорость в 4 раза больше скорости утки. он всегда бежит по направлению на нее но не умеет плавать...сможет ли утка выбраться из воды и не быть съеденной драконом
Давайте не будем задачки, требующие знания констант (пи и подобного) :grin:

verse3e3

задачка с реального собеседования в маккинзи :D
давай лучше простое и сложное решение сюда :)

Nusha10

Если центр кривизны границы пруда в месте нахождения дракона находится ровно на прямой между драконом и уткой, то утка может плыть по этой прямой, а дракон не сдвинется с места. Утка выиграет.

verse3e3

п...ц не работать тебе в маккинзи :)

verse3e3

ладно, давайте я сложно решение расскажу?

geva

Простое - если урка (утка) проплывает радиус за время А, то дракон за время 3.142А оказывается в любой точке на берегу пруда.

Nusha10

Просто условие голимое. Пруд круглый хоть?

geva

Пруд круглый хоть?
Впишем пруд в окружность, какие проблемы. Количество лошадиных сил у драконьего движка позволяет это сделать

geva

Почему на четыре делим? полупериметр пруда равен pi*R

verse3e3

ну а скорость у него в 4 раза больше

geva

Ага
Для желающих могу картинку нарисовать.
А вы решите для меня задачку с ЕГЭ, пожалуйста. Я сегодня в лужу сел.
(2 / pi) * sin x + cos (19*pi) = cos x

1853515

ты не прав
в чем?

geva

В том, что есть много симметричных фигур, но если ты любую, не круглую, повернешь на угол (pi / число углов) в горизональной плоскости, а потом поставишь на ребро, то такой люк с удовольствием упадет в дыру

verse3e3

короче, утка спасется или нет?

geva

Утка умрет (с) "Очень страшное кино"

Nusha10

Впишем пруд в окружность, какие проблемы. Количество лошадиных сил у драконьего движка позволяет это сделать
Если пруд в виде звезды, то дракон не успеет :)

verse3e3

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

dens

сводится к уравненю [math] $2 \sin y + \pi \cos y = \pi, y =-x $[/math], которое стандартными школьными методами сводится к [math]$  \frac{2}{\sqrt{\pi^2 + 2}}\sin y + \frac{\pi}{\sqrt{\pi^2 + 2}} \cos y = \frac{\pi}{\sqrt{\pi^2 + 2}}$[/math]
в итоге получаем [math] $y  = (-1)^k \arcsin(\frac{\pi}{\sqrt{\pi^2 + 2}}) + \pi k - \arctan(\pi/2)$ [/math]

1853515

В том, что есть много симметричных фигур, но если ты любую, не круглую, повернешь на угол (pi / число углов) в горизональной плоскости, а потом поставишь на ребро, то такой люк с удовольствием упадет в дыру

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

kvnkvn

Вообще все задачи тут есть в книге "Как сдвинуть гору Фудзи?".

verse3e3

ну да это правильно, задача про мэндмс оттуда же, предлагаю запостить сюда книгу

Suveren

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

geva

Ответ всем :)
Если пруд в виде звезды, то дракон не успеет

никто не говорил, что он обязан бегать строго по периметру пруда. Если мне скажут, что должен строго по периметру пруда, то я потребую +10% к зарплате за постоянно изменяющиеся условия труда
сводится к уравненю

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

нарисуй парочку, а я их уроню

1853515

нарисуй парочку, а я их уроню


:D

1853515

на ногу не урони - она тяжелая :D

geva

сейчас я поеду домой, а там попробую уронить, хорошо? :)

stm7929259

В треугольную дырку хуёвей залезать
Во, правильно, аргумент принят!

kaygorod

дан куб с ребром 10, составленный из кубиков с ребром 1 как кубик-рубика. этот куб целиком окунают в краску...сколько маленьких кубиков не покрасилось (хотя бы одной гранью)

Почему 8*8*8? Если хотя бы одной гранью, то все 1000. При условии, что краска не затекает внутрь, максимум по 3 грани будут окрашены на углах.
Задача 1. Есть здание 100 этажей и 2 стеклянных шарика. За наименьшее кол-во сбрасываний определить начиная с какого этажа шарик будет разбиваться.
Задача 2. Сварганить взрывчатку из подручных компонентов на необитаемом острове.

1853515

ну давай :)
можешь даже не только на (pi / число углов) вращать :)
ЗЫ у этой фигуры хоть углы есть... не нашел по-быстрому гладкую фигуру, а рисовать влом :)

stm7929259

+ задача про мух, вылетевших с автомобилей, движущихся навстречу
+ задача про парашютистов, которые друг про друга не знают, но им нужно после приземления на одну линию обязательно встретиться
+ задача для "математиков"
1^2 = 1
2^2 = 2 + 2
3^2 = 3 + 3 + 3
...
X^2 = X + X + ... + X - всего X раз
дифференцируем и получем 2 = 1. Если взять неопр.интеграл - тоже херня получится. Это задача для особо сильных аналитиков на собеседовании :)
Это типа Дойче Банк

Damrad

я не понял от чего производную берем? и откуда 2=1 получилилось

avg1035210

это задача для тупых менеджеров которые математику не учили никогда :)

1853515

я не понял от чего производную берем? и откуда 2=1 получилилось

типа X^2 = x+x+x+..+x
(X^2)' = 2x
(x+x+x+...x)' = (1 + 1 + 1...) = x
лол короче :)

avg1035210

интересно знает как решать эту задачу :grin:

1853515

(X^2)' = 2x
(x+x+x+...x)' = (1 + 1 + 1...) = x

на самом деле нагнал то ли манагер толи перцы в дойче
из 2x = x не следует 2 = 1.. просто все x равны нулю :grin:
ЗЫ хорош флудить - интересная тема же :)
дабы искупить вину за флуд запощу последнее что помню:
есть список с "петлей" (a la лассо) - найти его длину (т.е. длину хвоста и самого цикла)
что-нить еще вспомню - запощу

Damrad

а голова где?
список можно затирать?

1853515

затирать, писать ничего нельзя
есть указатель на начало (или конец - это как посмотреть :) ) хвоста

selena12

вообще-то он прав. уточни, что значит "дракон бежит на утку"

stm7929259

на самом деле нагнал то ли манагер толи перцы в дойче
Ну разумеется нагнали - тебе пишут как есть, сокращают с обеих сторон x, а потом говорят "Ой, а почему 2 = 1?". Сокращать можно (из примера видно, что не равно 0 производную-интеграл нельзя так брать

stm7929259

Не переживай за меня! Остынь, выпусти пар, пивка попей..

avg1035210

браво! решил :)

Max778

Утка в начале должна двигаться по окружности, радиус которой равен 1/5 расстояния в каждый момент времени до дракона (странно, что не волка). Когда расстояние до ближайшего края пруда станет равным 3/4 радиуса этого пруда, то надо плыть по прямой к краю и улетать.
Но если у нее начинает кружиться голова от таких спиралей, то можно плыть к краю пруда чуть пораньше - с pi/4 радиуса.

Damrad

а чем вообще можно пользоваться?
список одно или двусвязный? т.е. назад можем перемещаться?
можно создать копию этого списка, а потом ее уже затирать? или памяти нужно иcпользовать O(1)?

Suveren

я конечно тупой, но утки прекрасно взлетают с воды. и кстати не разу не видел чтоб они взлетали с берега.

lebuhoff

Когда пытался устроиться в частную IT-контору в Осло на месте задали следующие блиц-задачи:
1) Какой угол между минутной и часовой стрелкой в 3 часа 15 мин.?
2) Определит силу, с которой оказывает давление жидкость высотой h на вертикальную прямоугольную боковую стенку сосуда.
3) Какая площадь треугольника со сторонами: a=1 м., b=3 м. и c=5 м?

asgrig

чорт, надо переезжать в Норвегию и гнобить местных жителей

arturkaas

а какие ответы?

Badyss

ключевое слово "пытался" ?)

m_dron

Какая площадь треугольника со сторонами: a=1 м., b=3 м. и c=5 м?
Какой милый развод : )

katrinmania

сть пруд и утка в центре, вокруг пруда бегает дракон и его скорость в 4 раза больше скорости утки. он бежит на утку и не умеет плавать...сможет ли утка выбраться из воды и не быть съеденной драконом
это настолько боянная задача, что уже и симуляторы давно есть )
http://artcraft.cz/fun/duck.html

lebuhoff

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

Max778

Прошел! ТОчнее, улетела!

Damrad

я бы еще понял,если бы ты в формулу герона числа сразу бросился подставлять, но ты говоришь, начал РЕШАТЬ и искать АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ... сразу в шею гнать
да и остальные приведенные тобою задачки ужасно простые

lebuhoff

чорт, надо переезжать в Норвегию и гнобить местных жителей
Приезжай!
Тут, кстати, довольно много российско-белорусских ИТ-шников работают.
А вообще целью данных задач ставилась проверка базовых знаний для человека с PhD (про "ведущий вуз страны" МГУ тут не все слышали и предпочитают не верить на слово).
Причём, как оказалось, уже встречались китайские товарищи со "степенью PhD" такой, что не могли найти даже объём куба!

stm7929259

получил мнимую площадь
Я сразу заметил подвох т.к. числа очень показательные и видно, что треугольник какой-то ненормальный, "на слуху" красивый треугольник 3-4-5, а вот 1-3-5 сразу попахивает кидаловым из-за "1" - маловато!

lebuhoff

я бы еще понял,если бы ты в формулу герона числа сразу бросился подставлять, но ты говоришь, начал РЕШАТЬ и искать АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ... сразу в шею гнать
Упс-с. Уже перешли на критику меня?
В таком случае я бы порекомендовал бы учесть ряд факторов:
1) Собеседование на английском (с частичным переходом на норвежский, т.к. рабочий язык компании норвежский).
2) Уже к 5-ому курсу (а уж после аспирантуры и подавно) большинство забывает основные формулы (я уж не говорю про формулу Герона с которыми редко работает и которые можно посмотреть в справочнике под рукой.
3) Задачу я всё же РЕШИЛ и ПОЛУЧИЛ решение в общем виде.

sobol_polo

Тема с люками тут уже поднималась год назад.
А дабы развеять посиневшие от натуги математические умы, ловите этическую задачку. Тоже с собеседования.
Вы едете домой в своей машине, погода отвратительная - льет ливень и дует пронизывающий ветер. И вы видете, что на автобусной остановке стоят три человека. Один - пожилая женщина, которая едет в больницу. Второй - ваш лучший друг. Третий - ваша любимая женщина. В ващей машине всего одно место. Как вы поступите?

Damrad

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

12457806

Проеду мимо, постараясь облить их грязной водой из ближайшей лужи. Чтобы никому не обидно было.

beer-for-bear

Тетке вызвать скорую, другу дать денег на такси, а девушку с собой

Damrad

и как часто ты так поступаешь?
давайте реально отвечать

beer-for-bear

у меня в машине больше мест :)
а вообще в плохую погоду стараюсь не шляться по улицам, даже на машине

Bryn

Отвезу, конечно, пожилую женщину :)
Но сначала предложу любимой женщине,
а она откажется и уговорит меня отвезти бабулю в больницу.
А друг есть друг. Он все поймет и останется на остановке.
P.S.
А потом он женится на твоей любимой женщине,
и они будут часто вспоминать о тебе как о прекрасном человеке
Вот такая история в духе Ремарка

vovkak

меня на собеседовании как-то попросили прикинуть, сколько в Москве мужских парикмахерских.

Damrad

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

selena12

друга за руль, самому на пассажирское, девку себе на колени, бабку в багажник.

geva

на мужское достоинство друга надеваем Вовочку, а на Вовочку - три арбуза.

12457806

Во над какой задачей сейчас тружусь)
"Сделать описание стандартной виндоуской игры САПЕР. Документ должен быть оформлен по ГОСТ в виде руководства оператора"

geva

На собеседовании такие вопросы задавать как-то не с руки.

12457806

У меня послезавтра собеседование. Вот, сутки дали.
PS^ Мучительно больно подгонять сапера под ГОСТ. Наверное, в этом вся фишка.
PSS^ В яндексе в свое время просили всего лишь пункт менюшки "Закладки" IE описать.

dens

вспомнил еще задачу с собеседования "про слона":
на прямой в т. x0 находятся слон и тонна (=1000 кг) бананов. грузоподъемность слона 100кг. чтобы пройти 1 метр он должен съесть 1кг. также, он может перетаскивать бананы с одного места на другое (но все равно по дороге ест). на какое максимальное расстояние может отойти слон от т. x0?
p.s. двигается только вдоль прямой.

12457806

Я бы на месте слона сидел бы в хО, пока не сожрал бы все бананы. А потом бы прошел максимальное расстояние, равное кратчайшему пути до следующей тонны бананов.

1853515

как там люк ? уронился ? :D

svetik70

Думаю, , не будь дурак, уже открыл для себя кривые постоянной ширины.

Trewester

имеем переменные
i - элемент от начала (изначально 0)
n - интервал (изначально 0)
x - последний элемент
идём по элементам. если 2^n == i. запоминаем элемент в x.
если встретили элемент х_i_0 == x, тогда цикл равен i_0 - 2^n, а хвост i%(i_0-2^n)

1853515

ну так надо чтоб он признался что был неправ :grin:
ЗЫ нечего было подсказывать :)
ЗЗЫ меня в свое время порадовало, что можно просверлить почти квадратное отверстие :shocked:

1853515

чо-то я не вкуриваю..
какой "последний" элемент?
какой интервал?
мб я просто туплю :)
напиши плиз поразвернутее

Trewester



#define MAX_LOG10_OF_ELEMENTS 10000000

int func(int *a)
{
int *x;
int i = 0;
int n2 = 1;
int j;
int b = 1;
int LOOP,TAIL=-1;

for(k=0;b && k<MAX_LOG10_OF_ELEMENTS;k++)
{
x = a;
for(j=0;j<n2;j++)
{
if(x == a)
{
LOOP = i - n2;
TAIL = i%(i-n2)


return TAIL;
}
a = *a;
i++;

}
n2 = n2*2;
}

return -1;
}


сорри, если там +-1 промахнулся.
upd: поменял пару строчек местами.

Damrad

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

Trewester

полный перебор чего?
по кругу мы прокатимся не более, чем log_2(длина круга) +1
можно 2 на 10000 заменить.
асcимптотика [особо] не поменяется.

Damrad

ща...
не могу сообразить, почему это работает

katrinmania

ассимптотика
тест закончен, спасибо

Trewester

я чувствовал, что что-то не так в этом слове, но лень было гуглить :grin:
подстава. там оно выше было. все против меня.

Max778

Для слона у меня такой ответ получается:
[math] $ S = \sum\limits_{n=1}^{10} \frac{100}{2n-1} $ [/math]

Badyss

я когда на JAVA-прогера устраивался дали 4 задачки. 2 боянных + 2 новых для меня.
Бояны:
1) Из шахматной клетки вырезали 2 угловых противоположных клетки. Можно ли покрыть её кусочками 1*2 не накладывая куски друг на друга.
2) В коридоре 3 выключателя, в комнате 3 лампочки. Каждой лампочке соответствует один выключатель. Как определить что чему соответствует, если в комнату можно заходить только один раз.
И новые для меня:
3) В коробке есть m белых и n черных шариков. За раз ты вытаскиваешь два шарика, если они одного цвета докладываешь в коробку черный, если разного - белый. Повторяешь пока не останется один шарик. Можно ли сказать какого он цвета.
4) На каком-то туземном языке были написаны числительные надо было понять по какому принципу.
По времени особо не ограничивали, я минут за 30 написал решения всех 4-х задач.

olegikristina

Мне такие задачи/тизеры давали:
ТНК-ВР
-У тебя есть два фитиля, каждый полностью выгорает за минуту, но горят они с неравномерной скоростью. Как замерить полторы минуты?
- Есть роща. Как оценишь количество деревьев, растущих в ней?
- Оцени выручку московского метро за год.
- Что блольше: корень кубический из двух или корень квадратный из трех. (Неточно, но типа того)
Credit Suisse
Лондон:
- Сколько ежегодно продается футбольных мячей в России?
- Антон, у меня есть компания, Rolls-Roys. Она производит реактивные двигатели для самолетов. Какие факторы будут в ближайшее время влиять на ее прибыльность? Приведи аргументы, которые помогли бы мне убедить клиента купить акции компании.
Москва:
- На часах 3.15 - сколько градусов между часовой и минутной стрелкой? (боян)
- О скольких датах в году невозможно точно сказать в каком формате они записаны - идет ли первым число или месяц?
Еще вспомню - напишу.

ETrohkina

- Что блольше: корень кубический из двух или корень квадратный из трех. (Неточно, но типа того)
только наверно наоборот 2^1/2 vs 3^1/3
в 6 степень получаем 8<9

ETrohkina

Девочка Маша каждое утро по дороге в школу заходит к речке умыться. Её дом и школа находятся на одном берегу реки на разном удалении от реки. Найти кратчайший путь дом-речка-школа (река прямая).

katrinmania

угол падения = углу отражения )

soba

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

Badyss

а после того как убил одного впередистоящего убиваешь следующего?
или стоишь ждёшь мотыгу в спину

beer-for-bear

Это при устройстве в дурдом такие задачи дают решать?

freya83

 
Все люди планеты встают в круг по экватору паравозиком.

даже если выберут самых тощих, то вместится на экватор 100 млн чел. И если они все убьют друг друга, то по грубым подсчетам выживут все жители Земли.

ETrohkina

Если их отсортировать по скорости реакции по возрастанию, то подохнут все кроме последнего!

Badyss

выживет от одного до половины.
взависимости от реакции

LiliyaA

И что там в первой задаче получается?
(про стеклянные шарики)

Damrad

там вроде около 12ответ. (точно не помню. заново считать - лень)
идея такая:
бросаешь первый с 12 этажа. если не разбился, то дальше его просаешь с 12+11 этажа. если опят цел, то еще +10 этажей и так далее.
когда первый наконец разбивается, дальше вторым нужно идя по каждому этажу. в первом случае это будет 1,2,3...10 этаж.
во втором уже 13,14,...
если бы делать наивно-интуитивно - и скажем первым шариком скачать через +10 этажей, то когда она разобьется, вторым в худшем случае придется сделать еще 9 бросков. А первым мы могли уже и до 100-го этажа добраться, то есть сделать 10 бросков. и будет всего 10+9.
а в правильном решении будет не более 12 бросков.

1853515

 
#define MAX_LOG10_OF_ELEMENTS 10000000

int func(int *a)
{
int *x;
int i = 0;
int n2 = 1;
int j;
int b = 1;
int LOOP,TAIL=-1;

for(k=0;b && k<MAX_LOG10_OF_ELEMENTS;k++)
{
x = a;
for(j=0;j<n2;j++)
{
if(x == a)
{
LOOP = i - n2;
TAIL = i%(i-n2)


return TAIL;
}
a = *a;
i++;

}
n2 = n2*2;
}

return -1

 :shocked:
то ли я торможу, то ли хз, но что означает запись "a = *a;"
зачем там переменная b
зачем там итерация до MAX_LOG10_OF_ELEMENTS = 100000 если n2 "кончится" (станет больше 2^32) гораздо раньше?
PS на всякий случай - в элементах списка ничего не записано (никаких чисел)

Damrad

блин. ну это он имеет ввиду переход по указателю на следующий элемент
a = a^.next в паскалевской нотации
переменная b нужно чтобы брейкнуться из первого цикла находять внутри вложенного.
это просто булевский флаг. нужно брейкаться и выводить ответ - он = 0. пока еще не нужно = 1

1853515

видимо мой моск неспособен воспринимать алгоритмы в С :grin:
b там юзается только в одном месте вроде - в условии.. соотв. ее оттуда можно просто убрать вроде?
ЗЫ на длину списка нет никаких ограничений :)

1853515

там же return есть. мб b осталось от старой версии кода?

1853515


...
x = a;
for(j=0;j<n2;j++)
{
if(x == a)
....

разве тут не всегда будет true в if-е?

Damrad

там b юзается и в условии цикла:
b && k<MAX_LOG10_OF_ELEMENTS;
брейкнуться через ретурн конечно можно. подготовить прям там на месте и вернуть tail
но это сумборно будет.
лучше мы сначала в циклах покрутимся. потом выйдем нах из всех циклов и будем спокойно уже вне цикла расчеты делать сколько там длина, сколько там цикл и т.д.
>разве тут не всегда будет true в if-е?
кстати да...

1853515

b вроде только в условии юзается...
и оно равно 1...

Damrad

upd: поменял пару строчек местами.
Редактировал (05.03.2009 01:58)
раньше менялось )

Trewester

a = next(a)
переменная b - была флагом выхода из внешного цикла. Сейчас она не нужна.
я сначала написал очень коротко - потом подумал, что задолбают упрёками, решил дописать до рабочего(более-менее но всё равно какашками закидали
А что значит, что нет никаких чисел? указатель на объект есть? Запомнить его можно или нет? Если нет, то как отличить 2 объекта друг от друга?

Trewester

вот это баг, да. нужно проверку делать после перехода к следующему.

#define MAX_LOG10_OF_ELEMENTS 10000000
int func(int *a)
{
int *x;
int i = 0;
int n2 = 1;
int j;
int LOOP,TAIL=-1;
for(k=0;k<MAX_LOG10_OF_ELEMENTS;k++)
{
x = a;
for(j=0;j<n2;j++)
{
a = *a;
i++;

if(x == a)
{
LOOP = i - n2;
TAIL = i%(i-n2)
return TAIL;
}
}
n2 = n2*2;
}
return -1;
}
надо было писать на втором языке, который я чуть-чуть знаю. Там нет косяков с ограничением чисел и более читаемо.

Damrad

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

Damrad

во.теперь корректно. неплохо было бы если бы еще объяснил, почему это работает

1853515

а что на счет переполнения n2*2 (тут ведь по сути 2^n вроде) ?

Trewester

в цикле длины n2 мы ищем элемент, совпадащий с первым.
посколько n2 - неограничено, то когда-нибудь TAIL+LOOP < n2, поэтому такой элемент найдём.
А когда знаем длину цикла, находим по номеру элемента хвост.

antcatt77

а что на счет переполнения n2*2 (тут ведь по сути 2^n вроде) ?
если это реальная программа, то поставить тип __int64, или на крайняк добавить класс длинное целое.

1853515

+ я правильно понимаю, что во внутреннем цикле (в случае не совпадения с x) a "увеличивается" на n2 = 2^n?
т.е. a = 1, 2, 4, 8, 16, ...
и в начале каждого внешнего цикла выставляется x = a...
т.е. мы сравниваем только с 1,2,4,8,16 и т.д. элементом?
или я чего-то не понимаю?

katrinmania

идея такая:
бросаешь первый с 12 этажа. если не разбился, то дальше его просаешь с 12+11 этажа. если опят цел, то еще +10 этажей и так далее.
когда первый наконец разбивается, дальше вторым нужно идя по каждому этажу. в первом случае это будет 1,2,3...10 этаж.
во втором уже 13,14,...
Николас Кейдж сомневается в твоем ответе

1853515

__int64

ну хватит этого на 64 итерации - толку-то, если там длинна цикла может быть сильно больше 64 элементов...
хотя мб я просто не вкуриваю алгоритм...

Damrad

да срал я на кейджа. идея 100% правильная. и ответ тоже около 12

Trewester

ааа,
длина цикла
2^n , где n увеличивается на единичку с каждым циклом.

Trewester

т.е. n>sizeof(int) *8 ?
ну можно чуть подправить с
n2 = n2*2
на
if (n2 == 1<<(sizeof(int)*8-1
 n2 = n2 -1 + n2;
else
 n2 = n2*2
указателей же не может быть больше, чем размерность int.
и это уже не алгоритм, как мне кажется.

Trewester

можно просто на 1 длину цикла увеличивать,
n2 = n2++;
вместо
n2 = n2 *2;
тогда по кругу прокатимся чуть больше раз.

antcatt77

ну хватит этого на 64 итерации - толку-то, если там длинна цикла может быть сильно больше 64 элементов...
хотя мб я просто не вкуриваю алгоритм...
это смотря каких итераций
итераций изменения n:да, 64
но элементов пробежится: 2^64 - а столько памяти еще нет.

Trewester

в цикле сравниваем первый элемент группы со всеми элементами этой группы.
группы 1, 2, 4, .... элементов. (можно 1,2,3,... - любая неограниченная последовательность)
блин. надо мне учиться выражать мысли :crazy:

1853515

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

Trewester

да, но переменные не те.
а - это текущий элемент (a_i)
x - первый элемент в группе.

1853515

все, вроде во все воткнул..
в правильность подсчета хвоста и цикла лень втыкать :)
все вопросы сняты :)

Damrad

нет не сняты. идею я тоже вкурил. а вот подсчет нет.
пусть у нас список из 20 элементов
и цикл начинает с 11-го: next(20) = 11
допустим мы выбрали стратегию не когда *2, а когда размер группы на каждом шаге ++.
вот где-то в середине этого цикла закончится предыдущая неудавшаяся группа. И мы начали новую и она нам совпадение. т.е. замкнулась. длину цикла мы понятно дело сразу скажем.
А как длину хвоста считать? У нас по идее нету никакой информации о том, как далеко начало этой успешной группы от 11 элемента

1853515

мне отсюда задачки нравятся (не все правда)
вот вроде ничего = хотя хз пока что

antcatt77

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

Damrad

вот. теперь отличное объяснение. а как узнать точную длину хвоста, если метка попала на середину цикла и потом мы сообразили, что это цикл?

1853515

я же написал, что понял уже алгоритм :)
мне больше нравится мой :)
1-й итератор всегда увеличивается на 1, второй на 2.
ждем пока пересекутся 2 раза - разница между временами и будет длина цикла
далее от точки пересечения и от начала списка пускаем 2 единичных итератора
они пересекутся как раз в начале цикла через время равное длине хвоста
вроде так :D

antcatt77

да, подсчет в коде не правильный, т.к. там написано
TAIL = i%LOOP
т.е. считается, что TAIL всегда меньше цикла, а это может быть и не так

Damrad

они пересекутся как раз в начале цикла через время равное длине хвоста
сомнительно. почему они не могут пересечься на середине цикла?
или это не совсем единичные итераторы?

Den_P

задача посложнее - как м&мs покрывают глазурью так, что не остается никаких следов
Это где такую задачу давали?

1853515

пересекутся, пересекутся...
или это не совсем единичные итераторы?

это как? чисто мнимые ?:)

Damrad

ну типа может они у тебя не синхронно на 1 увеличиваются. а как-то хитрее.
вот пример:
проверил твой алгоритм на листочке для такого списка:
1... 11 и next(11) = 5
первый раз они пересекаются в точке 7. и равны при этом 7 и 14. 14-7 = 7 - это длина цикла. все правильно.
потом пускаем единичные от 1 и от 7.
1 2 3 4 5 6
7 8 9 10 11 7 опа. один уже бежит впереди другого и они никогда не пересекутся

Trewester

ага. ошибся.
хвост можно сделать так:
перебираем все элементы цикла. Получаем на каждом шаге длину пути от первого элемента(хвоста) до каждого элемента цикла. Берём минимум иэ этих чисел.

Damrad

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

Damrad

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

verse3e3

мне нигде - это задача из упомянутой тут книги

1853515

ну там +-1 :)
начинай с элемента след. за пересечением

antcatt77

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

Badyss

такую хорошую тему засрали...

verse3e3

надо сделать тему обсуждаемой
а вообще согласен, все эти разговоры и желание быть умнее кого-то - полный бред

1853515

опередил :)
я просто на бумажке рисовал что там куда попадает - так что +- 1 :)

Damrad

все эти разговоры и желание быть умнее кого-то
поржал. где ты это увидел?

Damrad

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

1853515

была уже похожая тема ( и не одна) - там уже предлагали ее сделать обсуждаемой и прикрепить, но это не встретило понимания

1853515

быть умнее кого-то
мелочь, а приятно (с) :grin: :grin: :grin:

ETrohkina

желание быть умнее кого-то - полный бред
нормальное желание :)

antcatt77

апд: проверил на других примерах... забавно они всегда ровно на 1 расходятся. в общем первый нужно пускать с начала списка. а второй - не с точки пересечения, а от следующего за ней элемента
что-то мне, кажется, что ты какие-то красивые примеры подбирал, чтобы такое получилось.
что будет, если хвост - 0, а кольцо - 3, 4, 5, 6 и т.д.?

verse3e3

разных ответа: "где ты это увидел", "мелочь, а приятно", "это нормально"
предлагаю создать отдельную ветку "кто тут самый умный"

antcatt77

ага и получаем асимптотику н квадрат... в случае если длина цикла равна половине длине списка
да, будет tail*loop
для варианта наоборот, когда для каждого элемента цикла перебираем хвост - будет (tail+loop/2)*loop

Damrad

что-то мне, кажется, что ты какие-то красивые примеры подбирал, чтобы такое получилось.
зря тебе так кажется. Я не на столько туп, чтобы не суметь это правильно протестить. странно, но работает. нулевые и единичные случаи я не тестил. вот разные независимые комбинации длины списка, хвоста и цикла - да

Damrad

tail*loop
тебе не кажется, что задача должна иметь какое-то более интересное решение?
ибо tail * loop как-то не сильно отличается от обычного решения в лоб за (tail + loop) * (tail + loop)

Damrad

вот вам еще задачка со вступительного собеседования в мфти:
заходит абитуриент. ему профессор говорит:
-Вон видите на окне ваза стеклянная стоит?
-Ага.
-Так у нее та сторона, которая стоит на солнце - холоднее, чем та, которая обращена к нам! Почему так?
-Че реально?
подходит, убеждается, охуевает. собеседование не проходит.
а вы бы прошли? ;)
да, задачка известная и многие ее знают. не обламывайте тех, кто не слышал

Trewester


// b - элемент в цикле
//first - данный по задаче

unsigned int m;

m = -1
for(b1=b;;b1 = next(b1)
{

a = first_el;
for (i=0;a!=b;i++)
a = next(a)

m = min(m,i)
}

return m;

antcatt77

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

Den_P

Поделитесь задачами с собеседований или нестандартными вопросами
Один знакомый любит на собеседованиях давать задачу про огурец:
В огурце массой 100г было 90% воды, после усыхания стало 80% воды. Какова масса огурца после усыхания?

geva

граммов

Damrad

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

antcatt77

тебе не кажется, что задача должна иметь какое-то более интересное решение?
конечно, не кажется.
т.к. красивые решения имеют только задачки из учебника.
реальные задачки (в том числе как раз те, которые дают на собеседование) - часто не имеют красивого решения.

antcatt77

а вот почему на втором этапе тоже они встречаются - не понимаю
медленный итератор пробегает = tail + z
быстрый итератор пробегает = tail + z + k*loop
быстрый итератор пробежал путь в два раза больше
2*(tail+z) = tail+z+k*loop
tail+z = k*loop
далее пускаем два единичных: один от старта другой от точки tail+z
точка пересечения у них должна быть конец хвоста
первый итератор - прошел tail
второй итератор - прошел tail+z+tail, что равно tail+(z+tail) = tail + k*loop - а это и есть точка стыка между кольцом и хвостом.
да, согласен - алгоритм работает - они встретятся

Damrad

ага. согласен. только что на листочке те же вычисления провел
автор сам решение придумал?

ETrohkina

А что весёлый профессор спрашивает в пасмурную погоду?

Suveren

-Так у нее та сторона, которая стоит на солнце - холоднее, чем та, которая обращена к нам! Почему так?
"Да её какой-то козёл повернул." - ответ правильный, собеседование не пройдено.

vantony

Понравились задачи про фитили (о том, что есть 2 фитиля, горящих неравномерно, но оба с временем горения в 1 минуту. Где нужно придумать, как отсчитать 1.5 минуты) и про 3 лампочки (к каждой из которых по выключателю проведено и нужно определить - какой куда, лишь 1 раз зайдя в комнату).
И легкие вроде, а с ходу и не ответишь - самое то для проверки мозга Хотя не все знакомые нашли решения)

galka1

про 3 лампочки (к каждой из которых по выключателю проведено и нужно определить - какой куда, лишь 1 раз зайдя в комнату
Задача содержит неявное условие, это плохо ). Это только с лампочками накаливания выйдет, и то не всегда. Вот если лампочки на шпиле ГЗ, а выключатели - в подвале, а?
Есть другая задача - 8 лампочек и 8 выключателей. В комнату можно заглядывать 3 раза. как тут быть ?

geva

как задачу с фитилями решать?

Damrad

с двух концов поджигать

Damrad

АПД: условие кривое. забейте пока-что
вот тебе задачка на логику про кроликов:
есть 2000 кроликов.
и есть 10 пробирок. в одной из них - яд.
если кролику дать яд, он умрет через 10 дней.
как за 11 дней узнать в какой пробирке яд?
на rsdn была кажись

Badyss

условие задачи неполное.
не сказано сколькими кроликами можно пожертвовать

stm767951122

Дать 10 пробирок 10 кроликам и сидеть наблюдать.
Наверное, кролики неотличимые или что-то еще? Уточни задачу.

Damrad

да хоть всеми. не важно. на то они и кролики, чтобы ими жертвовать.

Damrad

можешь считать, что кролики имеют номера на спинке.
апд: кроликов 2000, а не 1 тысяча. ну или 1000 кроликов и 9 пробирок. хе х
бля. я запутался. щас найду условие

stm767951122

Дать пробирку 1 кролику 1.
Пробирку 2 кролику 2.
...
Из кролика 11 сделать жаркое.
Через 10 дней посмотреть, что вышло.
В чем подвох?

Badyss

я знаю эту задачу с 64 пробирками и 6 кроликами которыми можно жертвовать
PS. Насчёт 64 не уверен, 63 точно можно. Правда это задача не с собеседований.

Damrad

сорри. я забыл условие. ща придумаю

stm767951122

Все веселее чем алгоритмы.

Damrad

Все веселее чем алгоритмы.
я тебя наверное разочарую

stm767951122

^10 > 1000, чо тут думать!

abramenkomv

Пиши в офтопе — кому надо подумает, кто захочет прочтет!

stm767951122

Я даже решать не буду, все же понятно сразу.

abramenkomv

Я тебе мягко намекаю, что ты здесь не один. Сам лично не хочешь не решай, а даже идеи решения надо писать в оффтопе, чтобы каждый желающий мог самостоятельно подумать над решением от начала и до конца.

stm767951122

Я тебе мягко намекаю, что ты здесь не один. Сам лично не хочешь не решай, а даже идеи решения надо писать в оффтопе, чтобы каждый желающий мог самостоятельно подумать над решением от начала и до конца.
NOTED!

stm767951122

Поставил тебе плюс!

Badyss

вот кстати сайт подборка задач такого типа на русском.
Ответов нет, все желающие могут зарегистрироваться и проверить своё решение.

Badyss

расскажите ещё плз про слона и бананы плз. :)
Ну я перетащил на
100/19+100/17+...+100/3+100/1 км
На мой взгляд - это максимум.
Идея в том, чтобы 900 кг бананов было в некоторой точке А_1 до неё 19 ходок(10 туда и 9 обратно 800 кг в точке А_2 до неё от точки А1 17 ходок и т.д.

dens

я кстати не знаю точного решения в задаче с бананами.

lordkay

вот кстати сайт подборка задач такого типа на русском.

мне эта нравится -
У Мегамозга нашли страшную болезнь. Доктор выписал ему всего 4 таблетки двух видов (по 2 каждого вида совершенно не отличимых друг от друга, и предупредил, что если выпить более одной таблетки одного вида - смерть, не выпить таблеток - смерть, выпить за раз меньше нормы - смерть. Таблетки надо принять за 2 приема по одной каждого вида через день ровно в 10:00. К несчастью, Мегамозг смешал таблетки. Как ему гарантированно выжить?

lordkay

еще мне нравится, когда программисты начинают писать прогу, чтобы решить эту задачу
 
Есть резинка длины 1 метр. По ней ползет улитка. Скорость улитки 1см в минуту. Ползет она от левого конца резинки к правому. В конце каждой минуты резинка растягивается и ее длина увеличивается на 1 метр. "Растягивание" происходит мгновенно и равномерно по всей длине.
Вопрос: доползет ли улитка до правого конца резинки?
Понятно, что улитка живет вечно и не устает.

Trewester

живучая улитка :grin:
вселенная, кстати, тоже вечная?
 
доползёт.
если принять, что не резинка растягивается, а улитка сжимается, то она ползёт
1, 1/2, 1/3...
этот ряд не ограничен, но, когда он 100 достигнет вселенной скорей всего уже не будет.
 
наверно западло тем, у кого скрин стоит, где текст белый на чёрном фоне

Trewester

 
У Мегамозга нашли страшную болезнь. Доктор выписал ему всего 4 таблетки двух видов (по 2 каждого вида совершенно не отличимых друг от друга, и предупредил, что если выпить более одной таблетки одного вида - смерть, не выпить таблеток - смерть, выпить за раз меньше нормы - смерть. Таблетки надо принять за 2 приема по одной каждого вида через день ровно в 10:00. К несчастью, Мегамозг смешал таблетки. Как ему гарантированно выжить?

клёвая задачка.
я так понимаю всякие подручные средства(доктора там) использовать нельзя?
upd:...

lordkay

 
этот ряд не ограничен, но, когда он 100 достигнет вселенной скорей всего уже не будет.

да, ей ползти 52*10^36 лет
 

lordkay

я так понимаю всякие подручные средства(доктора там) использовать нельзя?
а что ты хочешь сделать с доктором, скормить ему все таблетки и посмотреть что будет? :)

Trewester

да я неправильно условие понял. Я думал нужно съесть всего 2 таблетки. одну сегодня. одну завтра. И чтобы они разные были.

elenakuzina

В ABBYY что ли устраивался ?

Badyss

не. Superscape

elenakuzina

В ABBYY точно такие же задачки давали 3 года назад

Badyss

я догадываюсь кто у кого спёр :)

ETrohkina

С таблетками прикольная задачка, решал года 4 назад :)
А что делать если ему дали таблеток 3-х видов на 3-месячный курс (я 1 апреля по 30 июня и он их смешал? пить каждый день надо 3 разные таблетки.

Damrad

крошишь в кофемолке все в порошок. тщательно перемешиваешь. делишь на три кучки

ETrohkina

стопудова. только делишь 91 кучку.

buls

либо все перемолоть, смешать, растворить в воде для лучшего перемешивания, делишь объем на 91 и пьешь равное количество раз в день.

Damrad

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

ETrohkina

Я пират, Джек Воробей. Делю кучу золота на три равные кучки. Пусть каждый из пиратов выберет себе по кучке, оставшаяся отойдёт ко мне. А дальше пусть те две заново делят по тому же принципу.

verse3e3

не подойдет так как они могут захотеть одну у ту же "бОльшую" кучу

Damrad

типа ответ тут
http://kakoblog.ru/2007-12-15/kak-podelit-porovnu/
добавлю еще пояснение:
когда каждый выбрал себе по куче - он выбрал кучку не меньше 1/н-ной на его взгляд. значит любую оставшуюся он согласен отдать пирату, который не выбирал кучки, а делил

buls

для трех.
первый делит на 3 части, потом каждый свою еще делит на 3. потом каждый берет по одной трети от первых третей. т.е. по 3/9. все счастливы.

Damrad

неправильно
потом каждый берет по одной трети
в каком порядке они будут брать? может я заберу себе самые большие трети от третей

buls

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

frbvtyrj

не учёл откаты!
Первый делит примерно пополам и одну маленькую кучку оставляет, заранее сговорившись с 3, чтобы тот её выбрал.
В итоге у второго останется примерно четверть вместо трети :)

Damrad

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

ETrohkina

не подойдет так как они могут захотеть одну у ту же "бОльшую" кучу
Я же капитан Джек Воробей!
Делю кучу на 5 равных частей. 2 части сливаю в одну кучку, а 3 остальные сливаю и делю их пополам, т.е. по 3/10.
В итоге получилось три кучки: 4/10, 3/10 и 3/10.
Двое естественно выбирают бОльшую первую и дерутся за неё. А я забираю 2 остальные.

Trewester

на дискре мехмата эта задачка звучала так
"как разлить бутылку водки на N человек, чтобы все были удовлетворены"

buls

только зачем-то еще на до девятых частей опустился
мне кажется что чем меньше деление тем оно точнее.

ETrohkina

ааа! бля. вот как было:
есть 1000 пробирок
и всего-лишь 10 кроликов!
нужно узнать в какой пробирке яд.
кролики пронумерованные. и сидят каждый в своей клетке и ждут своей смерти
Рюхнул сотрудник на работе (или его яндекс)::
Для 2 кроликов можно 4 пробирки зафигачить (2^2):
первую никому не даём,
2-ю пробирку кролику-1,
3-ю - кролику-2
4-ю - кролику-1 и кролику-2.
Тогда если никто не погиб, то в 1-й яд, если оба, то в 4-й, и т.д.
3-м кроликам можно 8 пробирок залить (2^3):
1-ю никому не даём,
2-ю пробирку кролику-1,
3-ю - кролику-2
4-ю кролику-3
5-ю - кролику-1 и кролику-2.
6-ю - к-1, к-3
7-ю - к-2, к-3
8-ю - к-1, к-2, к-3
ну и т.д.

Trewester

первый разделил в пропорции 50000:10:1
второй выбрал 50000, третий 10, первому 1
они делят в тех же пропорциях.
получается, кто второй выбирать будет из первой кучи - останется недоволен.

Trewester

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

Trewester

в задачке с водкой было понятно, что есть только 3 стакана на троих, кстати

Trewester

почему они не могут выбрать одну кучку?
кучки как-то разделены.
первый(делящий думает, что
1: 1: 1
второй
4:3:1
третий
4,1:1:3

Kizel

Что-то не понравилось мне ни одно решение про трёх пиратов, поэтому пишу своё.
Есть первый, второй и третий пират.
Ну первый пират (самый лох) делит все сокровища на 3 равные с его точки зрения кучки. Двое остальных выбирают себе по кучке, а первый забирает себе оставшуюся. Если двое пиратов выберут одну и ту же кучку, то им надо выбрать ещё и вторую по размеру кучку и молиться, чтобы и в этом случае их мнения совпали; после этого смешать эти 2 кучки и поделить между собой, как в ситуации с двумя пиратами. Если же второй и третий пират лучшую кучку выберут одну и ту же, а вот насчёт второй по размеру не сойдутся, то им надо будет самую большую кучку поделить между собой отдельно, а вторую по размеру (каждый свою) поделить с первым пиратом.
В итоге первый пират получит по половине от друх равных (с его точки зрения) кучек. Второй и третий пират получат по половине от самой большой и второй большой кучек. Нормально, по-моему.
В варианте не понятно, что делать, если второй и третий пират укажут на одну и ту же кучку как на самую большую, а второй большой будут считать разные кучки.

Damrad

ага. и тут двоичная система )

ETrohkina

имхо ты тоже самое написал, можно было и не белым

verse3e3

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

antcatt77

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

oleg1966

1) Из шахматной клетки вырезали 2 угловых противоположных клетки. Можно ли покрыть её кусочками 1*2 не накладывая куски друг на друга.
2) В коридоре 3 выключателя, в комнате 3 лампочки. Каждой лампочке соответствует один выключатель. Как определить что чему соответствует, если в комнату можно заходить только один раз.
И новые для меня:
3) В коробке есть m белых и n черных шариков. За раз ты вытаскиваешь два шарика, если они одного цвета докладываешь в коробку черный, если разного - белый. Повторяешь пока не останется один шарик. Можно ли сказать какого он цвета.
4) На каком-то туземном языке были написаны числительные надо было понять по какому принципу.
По времени особо не ограничивали, я минут за 30 написал решения всех 4-х задач.
мне давали именно те же самые 4 задачи, я их тоже решил за 30 минут :) АББИ, видимо? :) :) :)

oleg1966

Если их отсортировать по скорости реакции по возрастанию, то подохнут все кроме последнего!
и пусть это будет Дункан Маклауд!

verse3e3

ок, отдали наименьшую тому кто делил, а дальше? все складывают кучу и см при n=2?

AIR1kk

ДА!

stm767951122

чуваки я знаю решение про кучки скажите если уже можно написать

verse3e3

hurrah

Trewester

это не решение.
выше есть пример, на котором оно не работает.
решение написал.

Trewester

а как они определят, какая самая маленькая?

antcatt77

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

Trewester

задача в том. чтобы каждый считал, что его часть > 1/3. вне зависимости от очерёдности.
1) первый разделил. он считает себя крутым дельцом оценивает кучки как 1:1:1
второй оценивает кучки как 4:1:3
третий как 4,1:3:1
если отдать 3 кучку первому, то по мнению второго этого отойдёт 3/8 > 1/3, а значит на первых двух останется <2/3. И независимо от того, кто будет делить - он будет недоволен.
если отдать 2 кучку - тоже самое с третьим.

soba

Авторы, которые не пишут решение, просьба не ставить перевод строки лишний раз.
А то водишь зажатым курсором по экрану лишний раз :mad:

stm767951122

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

klenal

а если сразу двое крикнут?

Damrad

точняк... что-то такое там было...

antcatt77

с точки зрения психологии способ не очень.
нервные будут кричать раньше всех, а потом буду ныть, что им недодали и надо начать дележки с начала.
т.е. имхо, это способ для людей с крепкими нервами и хорошей реакцией.
ps
кстати еще все эти способы интересно оценивать с той точки зрения, а что будет если поровну даже теоретически не делится.

stm767951122

Начать отсыпать обратно в большую кучу пока один из них не откажется.

stm767951122

нервные будут кричать раньше всех, а потом буду ныть, что им недодали и надо начать дележки с начала.
Не понимаю, какое это имеет отношение к решению задачи.

blackout

А если они оба откажутся?
В стади постили решение этой задачи для общего случая, по-моему меньше года назад.

blackout

Если правильно помню, там было такое решение:
 Первый выделяет свою долю. Потом начинают опрашивать остальных, согласны ли они ему ее отдать.
Если все согласны, то отдаем и решаем для меньшего числа человек.
Если кто-то не согласен, то он считает эту долю больше средней. Дадим ему эту долю уменьшить и дальше опрашиваем, согласны ли отдать эту долю уже ему.

stm767951122

А если двое не согласны?

stm767951122

То есть, мне довольно понятно, что твое решение точно такое же.
Если тебе не понятно, то не надо, пожалуйста, меня поправлять.

blackout

Какие двое?
Твое решение неправильное, а то, которое привел я - правильное. Поэтому оно и не точно такое же.

stm767951122

Что, если двое не согласятся первому отдать ему долю?

Не рой себе яму, пожалуйста.

blackout

Что, если двое не согласятся первому отдать ему долю?
Я так понимаю, что ты говоришь о случае трех человек.
Первый выделяет свою долю.
1) Если второй и третий согласны, то они делят между собой остальное.
2) Если второй не согласен, то второй уменьшает долю, выделенную первым и соглашается ее взять. Теперь первый согласен, так как он по его мнению поделил поровну, а второй эту долю даже уменьшил. Так что остается только мнение третьего.
2.1) Если третий согласен, то второй берет долю и третий и первый делят остальное.
2.2) Если третий не согласен, то он берет долю, выделенную первым и уменьшенную вторым и сам в свою очередь ее уменьшает*. Теперь первый и второй согласны отдать ему эту долю по вышеназванным причинам и могут спокойно делить остаток между собой.
* Это в общем случае, в случае n = 3, он ее уменьшит на 0 конечно, так как она ему и достанется.

blackout

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

Ну хорошо, а что если эти двое опять одновременно откажуться? Начать насыпать опять из большей кучи в меньшую? Но вот беда, эти двое опять могут одновременно сказать, что хотят меньшую кучу и т.д.

stm767951122

Первый выделяет себе 99%.
Второй не соглашается и уменьшает выделяет себе 98%.
Третий выделяет себе 97% и забирает.
Не ништяк.

antcatt77

А если двое не согласны?
если одновременно двое не согласны, то выбираем кого-то одному предлагаем уменьшить и взять себе, а потом и второму тоже самое.

blackout

Первый выделяет себе 99%.
Задача первого - выделить себе среднюю долю. Значит он думает, что 99% это средняя доля.
Второй не соглашается и уменьшает выделяет себе 98%.
Задача второго - выделить себе среднюю долю. Значит он думает, что 98% это средняя доля.
Третий выделяет себе 97% и забирает.
Итак, третий доволен, второй доволен (ведь третий взял меньше 98%, которые сам второй считает за среднюю часть первый доволен (как и второй).
Мне кажется, ты не понимаешь это решение :)

antcatt77

Не ништяк.
так все, которые еще без доли могут участвовать.

Trewester

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

почему дождёмся момента, когда кто-нибудь закричит?

Trewester

Если правильно помню, там было такое решение: 
вот это прикольное решение.

stm767951122

если одновременно двое не согласны, то выбираем кого-то одному предлагаем уменьшить и взять себе, а потом и второму тоже самое.
Ну так это и с моим решением работает.

blackout

Не работает. В твоем решении на одном шаге индукции долю меняет только один человек.

alrtyntu

Итак, третий доволен, второй доволен (ведь третий взял меньше 98%, которые сам второй считает за среднюю часть первый доволен (как и второй).Мне кажется, ты не понимаешь это решени
это не решение, так как оно предполагает что мне "побоку" я беру или не я. Себе-то я считаю долю средней, а вот другому... не факт.
К тому же, тут важна очередность.
Вообще задача из серии: "представьте, что перед вами - n абсолютно логичных существ, знающих, что перед ними n-1 абсолютно логичное существо и вы".
При подобном раскладе -да, решение.

yuli9

вот задачка(не бейте ногами, если слышали):
сын отца профессора бьет отца сына профессора.
кто кого бьет, если профессор участия в драке не принимает?

blackout

это не решение, так как оно предполагает что мне "побоку" я беру или не я.
То же самое можно сказать и про решение для двух пиратов. Ведь тому, кто делит, "побоку" он берет, или не он.
А вообще, это решение в том смысле, что в независимости от сговора любого количества пиратов, каждый пират может получить не менее 1/n, если у него хороший глазомер.

alrtyntu

я указал на область применимости решения, только и всего :)
Для "абсолютно логических существ" все верно, для существ "психологических" - как карта ляжет.

geva

боян
брат профессора бьет ее мужа

maxbut

А что за задачка про пиратов в ссылке?
Я вот такую задачку про пиратов знаю:
есть 5 пиратов, им нужно разделить между собой 100 монет.
Им нужно как-то разделить между собой эти монеты. Они договорились делить так:
они по очереди будут предлагать способ деления, и каждый голосует за или против,
причем если хотя бы половина голосующих за, то этот способ деления принимается,
в противном случае, того, кто предложил этот способ, казнят, и уже следующий предлагает способ деления.
Каждый пират имеет цель выжить и получить как можно больше денег, и каждый пират это знает про других.
Какой способ нужно предложить первому пирату, чтобы получить максимально возможную сумму?

stm8647541

Про монеты задачка ещё есть - есть 13 монет, одна из них фальшивая, но тяжелее или легче она - неизвестно. Есть весы без гирек. Надо за три взвешивания найти фальшивую монету.

nasheforum

есть 5 пиратов, им нужно разделить между собой 100 монет.
Им нужно как-то разделить между собой эти монеты. Они договорились делить так:
они по очереди будут предлагать способ деления, и каждый голосует за или против,
причем если хотя бы половина голосующих за, то этот способ деления принимается,
в противном случае, того, кто предложил этот способ, казнят, и уже следующий предлагает способ деления.
Каждый пират имеет цель выжить и получить как можно больше денег, и каждый пират это знает про других.
Какой способ нужно предложить первому пирату, чтобы получить максимально возможную сумму?

Он (первый) возьмёт 98 монет себе и по одной отдаст среднему и последнему
Решение:
Пусть для определенности пираты занумерованы по старшинству (5й самый старший, 1й - младший и решает всегда самый старший пират. Рассмотрим по индукции, сначала для двух пиратов:
[2]: Очевидно, 2й возьмет все 100 монет себе, и шиш 1му, и сам же за это проголосует, его голоса достаточно
[3]: 3й возьмет 99 монет себе, и одну даст 1му. В этом случае 1й поддержит его на голосовании, т.к. он знает, что если сольет 3го, то решать будет 2й, а второй ничего ему не даст. Одна монета лучше, чем ноль
[4]: 4й возьмет 99 монет себе, и одну даст 2му. В этом случае 2й поддержит его на голосовании (2 голоса из 4х достаточно т.к. он знает, что если сольет 4го, то решать будет 3й, а уж он хуй ему че даст (см. схему выше)
И наконец, [5]: 5 возьмет 98 себе, и под 1й отдаст 3му и 1му. Они поддержат его, т.к. знают, что если сольют его, то 4й пират предложит схему [4] (а 2й согласится при которой им не достается вообще ничего.
Вроде так...

Dasha1992

Кто-нибудь решал задачу с Yandex-a?
:
Составить набор тестов для тестирования лексического анализатора, разбирающего декларации следующего вида (здесь приведён синтаксис декларации в нотации Бэкуса-Наура):
procedure <return type> <name> ([<param type> <param name>[, ...]]); <return type>= void | int <param type>= int | long <name>, <param name> - идентификаторы, соотвествующие требованиям java.
Результат работы лексического анализатора - заключение о том, является ли введенная строка корректной декларацией.
Для каждой строки должен быть указан ожидаемый результат работы программы.

Kizel

Кстати очень интересная задачка про 13 монет. Кто ещё не решал, советую решить самим, а не смотреть в ответ. Я раньше решал только для 12 шаров, оказывается для 13 тоже можно :). А для 14 пока могу решить, только если есть ещё и 15-я, эталонная монетка.

mamishka


ааа! бля. вот как было:
есть 1000 пробирок
и всего-лишь 10 кроликов!
нужно узнать в какой пробирке яд.
кролики пронумерованные. и сидят каждый в своей клетке и ждут своей смерти
Нужно точно знать в какой пробирке яд, значит:
  1. Каждому кролику даём пробирку уникальную пробирку. (число сочетаний из 10 по 1 = 10)
2. Каждой паре кроликов даём из уникальной пробирки (число сочетаний из 10 по 2 = 45)
3. Каждой тройке кроликов даём из уникальной пробирки (число сочетаний из 10 по 3 = 120)
и т.д.
9. Каждой девятке кроликов даём из уникальной пробирки (число сочетаний из 10 по 9 = 10)
Таким образом можно залить в кроликов 1024 разных пробирок (одну не заливать ни в кого).
Получили ответ равный 2^10 = количество возможных вариантов, которые можно закодировать этими кроликами, как битами (умер / не умер). :)

Badyss

Кстати очень интересная задачка про 13 монет. Кто ещё не решал, советую решить самим, а не смотреть в ответ. Я раньше решал только для 12 шаров, оказывается для 13 тоже можно . А для 14 пока могу решить, только если есть ещё и 15-я, эталонная монетка.
Для 14 - решить задачу за 3 взвешивания невозможно. Даже в случае любого дополнительного числа эталонных монеток. Так что наверное стоит поискать ошибку в рассуждениях:)
Если сильно хочется что-то повзвешивать можно поискать за 4 взвешивания одну фальшивку из 40 монет.

Kizel

Для 14 - решить задачу за 3 взвешивания невозможно. Даже в случае любого дополнительного числа эталонных монеток. Так что наверное стоит поискать ошибку в рассуждениях:)
Если сильно хочется что-то повзвешивать можно поискать за 4 взвешивания одну фальшивку из 40 монет.
Ладно, ищи сам ошибку в рассуждениях.
 Откладываем 5 монет. 9 монет + 1 эталонная для равновесия кладём по 5 на чашки весов. Рассмотрим сначала случай, когда весы не уравновесились. Запоминаем, какая чашка тяжелее, а какая легче; убираем с одной чашки эталонную монетку, с другой убираем 3 монетки. Имеем 4:2. Далее одну монетку перекладываем, чтобы получить 3:3 и ещё 2 монетки меняем местами на чашках. Таким образом 3 монетки остались на своих местах, а 3 поменяли чашку. Проводим второе взвешивание. 3 варианта - чашки остались как были, чашки уравновесились, чашки поменяли положение (то есть чашка, которая была внизу, подняла, а котороя была вверху, опустилась). В первом случае фальшивая монетка находится среди тех 3-х, которые остались на тех же чашках, что и во время первого взвешивания. Берём 2, которые лежали на одной и той же чашке, кладём на весы и если чашки уравновесились, то фальшивая третья, если неуравновесились, то фальшивая лежит на чашке, которая находится в том же положении, в котором находилась чашка с этими двумя монетками после второго взвешивания. Во втором случае делаем вывод, что фальшивая монетка среди 3-х, которые мы отложили после первого взвешивания, берём 2 из них, кладём на весы и если весы уравновесились, то фальшивая третья монетка, если неуравновесились, то фальшивая на чашке, которая находится в том же положении, в котором находилась чашка с этими тремя монетками после первого взвешивания. Третий случай аналогичен первому, только фальшивую монетку ищем среди 3-х монеток, которые мы перемещали с чашки на чашку.
Ну если после первого взвешивания чашки уравновесились, то ты наверно знаешь, как среди пяти монеток отыскать фальшивую за 2 взвешивания.

Badyss

особо вникать не стал.
возможно суть в том, что мы имеем в виду разные задачи.
Я лично имел в виду(вполне возможно, что зря) задачу "определить какая монета фальшивая и легче она или тяжелее". При такой постановке задачи решить её при 5 монетах за 2 взвешивания нельзя. В то время как ты в последнем сообщении утверждаешь другое. Если у тебя другая постановка задачи - вполне логично что и ответ другой:)

stm767951122

Идите в программинг со своими алгоритмами, ебана.
Сколько можно повторять?

plush_s

Интересная тема :D
У меня есть любимая задачка (вернее две) - даю всем аналитикам в наш банк (в основном мехмат, многие сыпятся).
1)Есть 3 наперстка, под одним из которых деньги. Ты выбираешь любой. Из оставшихся 2х я переворачиваю пустой. Имеет ли смысл менять решение на второй не открытый? Ответ обосновать.
Если человек правильно решает, но строго не доказывает, то задаю другую задачу:
2)У меня есть х и 2х денег в конвертах. Ты об этом знаешь, но номинал х не знаешь. Я даю тебе конверт - в нем 100 рублей. Имеет ли смысл менять решение, ведь "средний" выигрыш при смене (50+200)/2=125 ? Ответ строго обосновать.
Каждая задачка по одной довольно просто строго решается, но решая одну за другой люди начинают бредить :)

tatjana82

Решение для 12 и 13 шаров практически одно и то же. Если решить для 12 монет, то через 2-3 минуты решается и для 13 (у меня так было если, конечно, там только одно решение для 12 (другие решения не искал). А для 14 задача решается только при условии, что одна из настоящих монет помечена.

toni_ga

Что за банк? 

katrinmania

Судя по наперсткам — Национальный Акционерный Европейский БАНК.

tatjana82

В предыдущем сообщении я неправильно выразился. Как и писал , для 15 с одной помеченной настоящей есть решение.

ukird


советую сменить задачи, это ж баян.
в первой нужно сменить выбор. Тогда твои шансы на деньги будут 2/3, если не менять, то 1/3.
во второй нужно рискнуть и взять другой конверт, тогда мат. ожидание выше.

stm767951122

Средний выигрыш при смене - 125?
Вычитать первый конверт Пушкин будет?

plush_s

Нет, другой. Если кому очень интересно - в приват.
Задачи, конечно боян, и они не единственные на собеседовании - они любимые.
по второй задачи
то анонимус - а если бы я дал конверт закрытым? тоже бы поменял решение?

blackout

Во втором случае оба конверта изначально одинаковы и то, что в одном из них лежит 100р ничего про этот конверт не говорит, так как неизвестно распределение величины x.
Значит пофиг какой конверт брать.

geva

Парадокс Монти Холла
Опа. а ты почему не в мусорном слое? :)

AIR1kk

решение не помню )
а его тут и помнить, какбе, не надо, логика то должна быть в голове ;)

stm8647541

+1. Я задачу запостил потому что такую (именно которую я давал, с 13 монетками) давали моему знакомому на собеседовании в мелкософт (может и ошибаюсь, хз). Нафиг обсуждать задачки с 40 монетами, их точно никто на собесе не получит :) Или же в такую контору точно не надо идти :)

ukird

если бы дал конверт закрытым, то по-моему тоже нужно поменять конверт.
типа если не менять конверт, то твой выигрыш - это х с вероятностью 1. Средний выигрыш: х.
Если поменять, то с вероятностью 0.5 ты выиграешь x/2 и с вероятностью 0.5 ты выиграешь 2х. То есть средний выигрыш тогда x/4+x. А это больше чем х. так что надо менять конверт. кажется так.

Max778

Все равно менять конверт.
При смене выигрыш возможный 5/4x

ETrohkina

Получается конверт в любом случае надо менять, можно даже не смотреть :)
Это парадокс, оторвись от тервера и взгляни со стороны на это подход, абсурд :)
п.с. если конверты абсолютно одинаковы по толщине, то брать сотку и радоваться что не полтинник достался, т.к. 200-рублёвую бумажку пока не выпустили

ukird

не вижу парадокса в том, что нужно менять конверт не глядя.
Если тебе чисто по интуиции кажется, что это абсурд, то смотри: типа четсная игра - это когда у тебя есть шанс 0.5 удвоить свои деньги и шанс 0.5 проиграть в ноль. Согласен? А в задаче условия лучше - в худшем случае ты не в ноль проиграешь, а всего лишь потеряешь половину

Damrad

кароче так: брать можно любой из конвертов (то есть менять нету смысла)
парадокс разрешается тем, что после того, как ведущий озвучил сумму в конверте, он этим установил некоторую минимальную планку выиграша (то есть 50)
Поэтому мы либо выигрываем этот минимум, либо +150
125 -50 = 75
150 / 2 = 75 все ништяк
то есть обман кроется тут: (50+200)/2=125?
нужно считать как (0+150) / 2. потому что минимальная планка 50 уже
возьмите меня аналитиком :D

ETrohkina

Ок, давай так. Есть два конверта, их дают нам с тобой, по одному. В любом случае нам меняться выгодно, т.к. мат.ожидание положительно для обоих, так? Парадокс :)

geva

- Ты получишь от меня все, что хочешь, но учти, твой сосед получит вдвое больше!
- Господи! Выколи мне глаз!

AIR1kk

Ну давай посчитаем матожидание :)
Тебе дают сотню, так? Значит с вероятностью 50% во втором либо 50, либо 200.
Далее, тебе предлагают поменять. Считаем матожидание:
а) если там сотня (вероятность 0,5 то (50-100)*0,5 + (200-100)*0,5 = 25.
в) если там полтишок (вероятность те же 0,5 то (50-100)*0,5 + (100-100)*0,5 = -25
Итого: 25*0,5 + (-25)*0,5 = 0
Соответственно - меняй, не меняй, хрен чё выгадаешь :)

ETrohkina

в) если там полтишок (вероятность те же 0,5 то (50-100)*0,5 + (100-100)*0,5 = -25
вот это невкурено (или мало выкурено :))
Расскажи лучше как выбрать шкатулку с деньгами у Якубовича? :cool:

AIR1kk

Расскажи лучше как выбрать шкатулку с деньгами у Якубовича?
как как, три буквы подряд угадать надо :grin:

ETrohkina

Задачка. Якубович предлагает тебе выбрать одну из двух шкатулок: в одной деньги, в другой пусто. Ты выбираешь, но Якубович открывает вторую, а она пустая, и предлагает тебе поменять свой выбор. Стоит ли менять выбор?

Max778

а) если там две сотни (вероятность 0,5 то (100-100)*0,5 + (200-100)*0,5 = 50.

Nefertyty

2)У меня есть х и 2х денег в конвертах. Ты об этом знаешь, но номинал х не знаешь. Я даю тебе конверт - в нем 100 рублей. Имеет ли смысл менять решение, ведь "средний" выигрыш при смене (50+200)/2=125 ? Ответ строго обосновать.
Понял, кажется.
То, что будет в первом увиденном конверте, случайная величина, а тут "среднее" считается исходя из того, что это - константа (100). Если строго ввести случайную величину x и разрешить две стратегии: брать первый увиденный конверт, или брать остальной - то легко видеть, что мат. ожидание выигрыша для них одинаково: 3/2*E(x)

AIR1kk

ну вот видишь, не прокатило :)
Чисто по логике, меняя ты либо получишь в два раза больше, либо в два раза меньше. Матожидание "прибыли" при смене всегда будет равно четвёртой части от предложенной суммы, чо, конечно надо менять :)

blackout

Пусть x - случайная величина и p - ее плотность.
Рассуждения про то, что во втором конверте равновероятно лежат суммы x и 2*x верно только в том случае, когда p(x) = p(2*x) <=> p(x) = const для любого положительного x. Но проблема в том, что такого распределения не существует.
А вообще, если рублей всегда целое число, то если сумма нечетная, то нужно полюбому брать второй конверт :)

katrinmania

хватит уже бояны обсуждать, все уже решено до нас
http://en.wikipedia.org/wiki/Two-envelope_paradox
вкратце: неизвестно распределение х, они могут всегда (50, 100) класть, например.

ukird

Pelot, что-то ты меня запутал. Что там в википедии написано скажите плз, инета нет :)

ETrohkina

Там полотно на английском. Пусть умный Шаллер в двух словах перескажет :)

ukird

вот я также как рассудил.
А всё, я понял. Когда конверты у нас обоих по одному и мы поменяемся - это не то же самое. В этом случае если один выигрывает, то другой однозначно проигрывает. И здесь нет смысла меняться, т.к. в сумме для нас не будет разницы. Это не то же самое, как если бы каждый из нас имел дело с отдельной парой конвертов.

AIR1kk

Сергей, Вы, главное, сообщите, когда передачу "Поле Чудес" с Вашим участием по телевизору показывать будут! :D

Sergey79

А в задаче условия лучше - в худшем случае ты не в ноль проиграешь, а всего лишь потеряешь половину
играем в игру: бросаем монетку. Если решка (0) - то теряешь половину денег. Если орел (1) - удваиваешься. Бросить монетку - всегда выгодно, потому что выигрыш после бросания x/2-x/2/2=x/4. Осуществим второе бросание - опять выиграем "в среднем" и т.д.
Пусть прошло миллион бросаний. Оператор A удваивает x, оператор B - уполовинивает. Операторы коммутируют, поскольку ABx=2*1/2*x=1/2*2*x=BAx.После миллиона бросаний y=ABBABABABAABBBBAAAABA....BABABABABBAx=x "в среднем", поскольку A и B "в среднем" поровну. Но где же выигрыш?
===========
В конвертах при смене конверта выигрыш в среднем 5/4x, а при не смене выигрыш в среднем x, где x - это произвольное положительное число, а вовсе не 100 рублей.
Типа
- тебе сколько денег дать: x или 5/4x рублей?
- а чему равно x?
- не скажу
В результате, из конверта получишь некую сумму, а уж равна она x или x/2 или 2x или 5/4x совершенно без разницы. КОлбласу на x не купишь.

Nefertyty

После миллиона бросаний y=ABBABABABAABBBBAAAABA....BABABABABBAx=x "в среднем"
Если "в среднем" понимать как мат. ожидание, то нет.
E(y) будет больше E(x лень считать, насколько.

ETrohkina

Надо короче Якубовичу спор предложить: спорим на x/2 рублей, что я выберу пустую шкатулку? Выбираю пустую, ты мне x/2 рублей, выбираю с бабками, то я проспорил и отдаю тебе x/2 рублей.
(где х - кол-во бабла в шкатулке).

ukird

задача(простите, если было):
есть 50 человек. Завтра их посадят в тюрьму, каждого в отдельную камеру. Они не смогут никак общаться. В тюрьме есть абсолютно пустая комната с одной лишь лампочкой. Охранник тюрьмы будет рандомно выбирать человека и приводить его в эту комнату. Человек может оставить лампочку включенной или выключенной. При этом охранник лампочку не трогает, то есть следующий кого приведут найдет лампочку в таком же состоянии в каком её оставил предыдущий. Условие: если однажды кто-нибудь из заключенных заявит, что уже все побывали в этой комнате, их отпустят. есть всего одна попытка. Но это произойдёт завтра, а сейчас они могут обсудить стратегию. Как им действовать, чтобы точно спастись? Предполагается, что время неограничено и заключенные не умирают

ukird

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

nasheforum

Ну тут вроде просто
Они выбирают одного чела, который будет "счетчиком"
Потом их начинают запускать. Обычный закл (не счетчик) действует так: если лампочка включена, не трогает её. Если выключена, то: если он еще не "отмечался", включает её, если же он один раз уже включал, то тоже не трогает. Когда "Счетчик" заходит и видит зажженую лампочку, он в уме добавляет +1 и гасит, а иначе не трогает. Когда он досчитает до 49, он говорит, что все уже побывали.
Устремляя число заходов к бесконечности и считая, что заклов запускают рандомно, получим, что рано или поздно такой момент наступит

Kizel

Значит по поводу парадокса двух конвертов. В двух словах, что я понял из Википедии :)
После вскрытия первого конверта мы почему-то предполагаем, что вероятность того, что наши деньги удвоятся или уполовинятся, 50 на 50. Это правда только в том случае, если в конвертах может быть любая бесконечно большая сумма. Но это невозможно. А если всё-таки принять это условие, то получится, что мы будем иметь либо бесконечность, либо бесконечность умножить на 5/4, что тоже бесконечность :). Поэтому конверты менять нет смысла.
В реальности же максимально возможная сумма конечна. И следовательно существует некая (конечная) вероятность того, что в выбранном конверте лежит именно она (будь то 100 рублей или какая-то другая сумма). Существует конечно ещё и равная (в случае слепого выбора из всех возможных x) вероятность, что в руках у нас конверт с минимально возможной суммой.
Таким образом, пусть у нас некий ряд иксов (по условию задачи в конвертах x и 2x рублей) от 1 до n. И на самом деле, если у нас вариант от 2 до n-1, то мы получаем 1.25x, если решим поменять конверты, то есть будем в плюсе. В случае k=1, выигрыш от смены конвертов будет очень незначительным. А вот в случае k=n (максимально возможная сумма в случае смены конвертов мы теряем дофига - половину от максимальной суммы!, и это перекроет все 25%-ные выигрыши в случае неграничных вариантов. Поскольку мы не знаем, какая сумма является максимальной, то и менять конверты нет смысла. Они для нас равнозначны.
Строго доказать могу для ряда 1, 2, 4, 8 ну и прочие степени двойки до 2^n

Sergey79

Если "в среднем" понимать как мат. ожидание, то нет.
E(y) будет больше E(x лень считать, насколько.
ну да, будет больше, поскольку отклонение от среднего не симметрично с точки зрения выигрыша.
Однако смысл в том, что выигрыш с равной вероятностью может быть "больше" или "меньше", хотя отклонение в "больше" - больше. Поэтому возникает вопрос о правомочности аппелирования средним при расчете выигрышной стратегии. Т.е. какой реальный смысл стоит за этой математической величиной.

ukird

да, правильно )
А вот такая: 100 человек стоят в линию. Все смотрят в одну сторону вдоль линии. Всем одевают на головы шапки 7 различных цветов. Каждый человек видит все головы впереди стоящих, но не видит свой цвет и цвет шапок всех, кто сзади. Далее, если человек называет цвет, и этот цвет совпадает с цветом его шапки, то он выживает, если нет, его убивают. Есть всего одна попытка. При этом когда кто-то называет цвет, все остальные слышат его. Сколько человек можно спасти? Как для этого нужно действовать?

Kizel

Пусть прошло миллион бросаний. Оператор A удваивает x, оператор B - уполовинивает. Операторы коммутируют, поскольку ABx=2*1/2*x=1/2*2*x=BAx.После миллиона бросаний y=ABBABABABAABBBBAAAABA....BABABABABBAx=x "в среднем", поскольку A и B "в среднем" поровну. Но где же выигрыш?
Говоришь, в среднем выигрыша нет ;). Ну-ну. Я согласен сыграть с тобой в это бросание монеток. Поставлю вначале рубль. В результате, если будет даже незначительное отклонение от среднего, скажем, орлов выпадет на 64 больше, чем решек (легенду про изобретателя шахмат все помнят? то это будет тебе ОЧЕНЬ дорого стоить. Если же случится равновероятное зеркально противоположное событие, то я потеряю свой рубль... :( :) ;) :grin:

galka1

Надо уточнить условия: Первым начинает тот, кто стоит самым последним.
И подсказка - все кроме этого последнего могут спастись

stm767951122

мат. ожидание выигрыша для них одинаково: 3/2*E(x)
Но ведь в этом случае не учитывается, что вероятность условная?

elenakuzina

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

Nefertyty

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

ukird

ну, теперь обобщи на случай n цветов.

elenakuzina

Невозможно, потому как условие задачи:
"Каждый человек видит все головы впереди стоящих"

ukird

хм, не понял почему невозможно. ну видит он все головы впереди стоящих и каждая голова какого-то из этих n цветов. Пусть n меньше кол-ва людей

stm767951122

Если игрок посмотрел внутрь первого конверта, то задача сразу поменялась, и рассматривать вероятности просто так, в отрыве от его знания содержимого первого конверта, нельзя.

Trewester

я понял, почему апполону эта задачка нравится.

starshine

Невозможно, потому как условие задачи:
"Каждый человек видит все головы впереди стоящих"
возможно, просто умрут первые n-1 (при n = 7 => 6) человек.
первые шесть человек говорят цвета, количество которых четно, при этом не повторяясь(если четных цветов нет,то только тогда повторяют уже названный цвет причем начинают считать с 7ого человека. А седьмой уже считает и делает выводы, как и все последующии, которые знают все цвета с седьмого человека, кроме своего.
то бишь умерают первые шесть, а выживут 94

ETrohkina

А вот такая: 100 человек стоят в линию. Все смотрят в одну сторону вдоль линии. Всем одевают на головы шапки 7 различных цветов. Каждый человек видит все головы впереди стоящих, но не видит свой цвет и цвет шапок всех, кто сзади. Далее, если человек называет цвет, и этот цвет совпадает с цветом его шапки, то он выживает, если нет, его убивают. Есть всего одна попытка. При этом когда кто-то называет цвет, все остальные слышат его. Сколько человек можно спасти? Как для этого нужно действовать?
В среднем n-1/2.
Опять боян с какой-то олимпиады по программированию.
Последний говорит чёт/нечёт кол-во белых к примеру всех впереди стоящих. предпоследний уже знает свой цвет и говорит его. третий с конца знает кол-во всех белых кроме последнего и цвет предпоследнего и однозначно определяет свой. и т.д. Все кроме последнего выживут, Последний с вер-ю 1/2 погибнет.

ETrohkina

Задачка для прогеров, Риалто. Для двух цветов - двоичная система, ты по идее говоришь последнюю цифру (0 или 1) в 2-ной системе исчисления.
Для n цветов получаешь число закодированное n цветами.
  ответ будет что-то типа: N-(n-1) плюс ещё в среднем (n-1)/n

galka1

проще говоря, последний назвает mod n от того числа, которое видит перед собой в виде разноцветных "цифр"

dhara360

Я не знаю в точности решения парадокса про выбор конвертов с деньгами, но у меня есть идея, которую я бы хотел обсудить.
Я считаю, что в данном парадоксе, как и в Санкт-Петербургском, решение задачи лежит в рассмотрении функции полезности. То есть, неверно что человек, УЗНАВ сумму в конверте, исходя из соображений мат. ожидания, поменяет конверт. В этом и состоит разница: в данной ситуации небезразлично, была ли показана сумма или нет, потому что не зная предложенной суммы, человеку безразлично, какой выбрать, а зная, он оценивает, насколько для него важна возможность потери половины этой суммы.

ukird

смотрите: пусть цвета пронумерованы от 0 до р-1. Последний складывает все номера и делит их по модулю р, получается какое-то х100, и называет соответствующий цвет. далее, предпоследний складывает все номера перед собой и делит по модулю р (х99).
х100 = (цвет 1-го + цвет 2-го + ... + цвет 99-го)modр
х99 = (цвет 1-го + цвет 2-го + ... цвет 98-го)modp
тогда
|х100-х99|modp - это и есть цвет 99-го.
Далее 98-й знает х99 и свой х98, его цвет: |х99-х98|modp.
Так спасутся 99 людей. вроде нет ошибки )

ukird

на одном сайте тоже было написано, что умрут первые р-1 человек. если в посте выше нет ошибки, то хрен там)

ukird

зачем писать такие общие посты: "если проделать вычисления по такой-то формуле, то полцчим ответ". Если уж ты пишешь как решить задачу напиши норм решение.

ukird

это было написано к посту, который удалили =(

katrinmania

Я считаю, что в данном парадоксе, как и в Санкт-Петербургском, решение задачи лежит в рассмотрении функции полезности.
Обычно так гуманитарии делают — начинают придумывать фигню, потому что знаний, чтобы рассмотреть задачу формально, у них нет.

Oleg4534

В догонку: как делают дробь, как делают мягкую начинку в конфетах, и посложнее: как чистят креветок?

geva

первые два вопроса имеют несколько ответов, а последний только два: либо таджиками, либо китайцами.

geva

Во, если я на первый вопрос отвечу: "мелкую дробь изготавливают литьем свинца с башни в тазик с водой, а крупную, картечь - обкатыванием кусочков проволоки", то меня не возьмут с формулировкой "больно умный, бл", да?

Oleg4534

либо таджиками, либо китайцами.
А вот и нет, в свч хвостики очень быстро нагревают так, что лопается хитин, потом отшелушевают ошмётки. :)

Runa

Наверняка для кого-то баян.
Однажды утром в воскресенье судья, который никогда не лгал, сообщил приговорённому к казни: "Вы будете повешены в один из дней между 8 часами утра и 8 часами вечера на следующей неделе. Когда именно вас повесят, вы узнаете только в день вашей казни".
Осужденный стал рассуждать таким образом:
Казнь не может состояться в следующее воскресенье, в последний день указанного судьёй срока: если она не состоялась до этого дня, то о том, что она произойдет в воскресенье, я буду знать уже в субботу в 9 вечера. Значит, меня не могут повесить в воскресенье, поскольку казнь, как сказал судья, будет неожиданной, и я узнаю о ней в день казни.
Но в субботу меня тоже не могут повесить: поскольку я знаю, что в воскресенье меня не повесят, то если в пятницу ко мне не придут с объявлением о казни, уже в 9 вечера в пятницу я буду твердо знать, что меня повесят в субботу. Казнь опять-таки не окажется неожиданной.
Рассуждая таким образом, осуждённый исключил последовательно пятницу, четверг, среду, затем вторник и, наконец, понедельник. В итоге он пришел к выводу, что его вообще не могут повесить, поскольку ни один день недели не удовлетворяет условию неожиданности, указанному судьёй. Но в среду за ним пришли и привели приговор в исполнение.
Где ошибка в рассуждениях? :)

katrinmania

вот здесь
никогда не лгал,

Runa

Т.е. во вторник в 9 вечера приговоренному было уже понятно, что его убьёт в среду? :) Почему? Получается и в понедельник в 9 вечера было понятно, что убьют во вторник. Однако во вторник не убили.

katrinmania

Утверждение судьи о том, что мол, чувак, какой бы ты алгоритм ни использовал, он все равно не даст тебе день казни — заведомо ложно, потому что заключенный вполне может выбрать себе следующий алгоритм — выбрать случайное число и бояться только его. То есть, утверждение судьи не может быть справедливо для всех возможных алгоритмов поведения.

Oleg4534

Взботни про полураспад и про кошку шрёдингера.
Теорвер не шлюха подзаборная чтобы ей вот так вертеть как захочется.

Runa

Но ведь заключенный ещё рано утром в среду не мог знать на 100% что его в этот день повесят. Он действительно узнал лишь когда ему объявили. Получается судья не соврал.
То что он мог тупо в начале недели решить, что его повесят в среду и точно знал заранее - разные вещи Имхо. :)

katrinmania

Судья не мог быть на 100% уверенным, что заключенный не выберет среду. Утверждение его ложно. Что тут еще обсуждать?

Runa

В моём понимании знал заранее - это либо логически к этому пришёл, есть чёткое объяснение. Либо кто-то слил инфу.
Подкинул монетку и решил что в среду - вряд ли можно назвать "знал".

nasheforum

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

katrinmania

Подкинул монетку и решил что в среду - вряд ли можно назвать "знал".
Нужно рассуждать формально, а не на уровне житейской логики.

katrinmania

Просвещайтесь
http://en.wikipedia.org/wiki/Unexpected_hanging_paradox

stm767951122

В history посмотрите на википедии - Шаллер эти статьи сам пишет.

stm767951122

И главное ставит
This article is in need of attention from an expert on the subject. WikiProject Mathematics or the Mathematics Portal may be able to help recruit one. (November 2008)
Казалось, нет бы с мехмата кого-нибудь рекрутировать.

zajxam

Есть n -натуральных чисел, есть еще n-натуральных чисел абсолютно таких же, и есть еще одно натуральное число. Все эти 2n+1 число как-то случайным образом расположены в массиве. Требуется за один проход массива найти то единственное число без пары. Памяти под другие массивы у нас нет.
P.S. Вроде бы поэтому же принципу последний из 100 чудаков в колпаках в цветах "радуги" должен спасать, оставшихся 99, и себя если сильно повезет :)
P.S.S Есть n коробков спичек, в каждом nk спичек, двое играют в игру за ход можно взять ровно из одного по выбору коробка любое количество спичек, тот кто возьмет последнюю победил. Придумать выиграшную стратегию.

stm767951122

Чуваки, n - это алгоритмы.
Мы все тут умники, разумеется.
Но давайте как-то сместимся обратно в сторону задач на логику, а не на алгоритмы.

Damrad

замени н на 10 и будет тебе логика вместо алгоритмов

Suebaby

Есть n -натуральных чисел, есть еще n-натуральных чисел абсолютно таких же, и есть еще одно натуральное число. Все эти 2n+1 число как-то случайным образом расположены в массиве. Требуется за один проход массива найти то единственное число без пары. Памяти под другие массивы у нас нет.
при фиксированном sizeof(int) и больших n задача не имеет смысла. Поэтому скажи пожалуйста, какая требуется асимптотика затрачиваемой памяти по n И по sizeof(int)
это тупняк был. Хотя всё же небессмысленный: памяти нам потребуется порядка log(n). Чтобы хотя бы одно число хранить. Впрочем, это и так всем кроме меня очевидно было.

incwizitor

Есть n -натуральных чисел, есть еще n-натуральных чисел абсолютно таких же, и есть еще одно натуральное число. Все эти 2n+1 число как-то случайным образом расположены в массиве. Требуется за один проход массива найти то единственное число без пары. Памяти под другие массивы у нас нет.
по XOR-ить их все нафиг

saper

P.S.S Есть n коробков спичек, в каждом nk спичек, двое играют в игру за ход можно взять ровно из одного по выбору коробка любое количество спичек, тот кто возьмет последнюю победил. Придумать выиграшную стратегию.
Если игроков двое, то необходимо после некоторого своего хода оставить в чётном количестве коробков по одной спичке (в остальных - по 0) и не допустить того, чтобы это провернул противник

stm7542793

P.S.S Есть n коробков спичек, в каждом nk спичек, двое играют в игру за ход можно взять ровно из одного по выбору коробка любое количество спичек, тот кто возьмет последнюю победил. Придумать выиграшную стратегию.

Если коробков нечетное число, выигрывает первый тянущий, если четное, то второй.
Для четного числа. Второй игрок мысленно разбивает коробки по парам и каждый раз, когда первый тянет сколько-то спичек из одного коробка, он тянет столько же из парного.
Для нечетного. Первый игрок берет все спички из одного коробка и сводит задачу к уже описанной выше.

stm5994768

А если в "парном" спичек меньше?

Damrad

что значит меньше? в каждом одинаковое число - по н*к спичек

stm5994768

хм я думал, что это k индекс типа

zajxam

что значит меньше? в каждом одинаковое число - по н*к спичек
нет, в каждом разное число спичек, k -пробегает от 1 до n (вообще отдельно эту задачу сложно рассматривать, так что вспоминаем задачку про 2n+1 число :) )

sergeychik_a

считаем сумму 10^n для всех чисел из массива
делим ее на 10 до тех пор пока не получим в остатке или в частном единицу
считаем количесво необходимых делений
...
профит!
Мир Вам!
 

Suebaby

считаем сумму 10^n для всех чисел из массива
шютник? это то, о чём я писал как раз

ETrohkina

Вы едете домой в своей машине, погода отвратительная - льет ливень и дует пронизывающий ветер. И вы видете, что на автобусной остановке стоят три человека. Один - пожилая женщина, которая едет в больницу. Второй - ваш лучший друг. Третий - ваша любимая женщина. В ващей машине всего одно место. Как вы поступите?
Высажу всех пид..ров из машины и посажу этих троих.

sergeychik_a

нет, не то
Мир Вам!

maxbut

я еще задачку с собеседований помню, решение недлинное, как раз для собеседований
Вопрос: может ли иррациональное число в иррациональной степени дать рациональное число

blackout

e в степени ln(2) даст 2. так как e трансцендентное, то e в рациональной степени не может равняться целому числу, значит ln(2) тоже иррационально.

maxbut

доказательство иррациональности ln(2 озвученное здесь одной строчкой, совсем не тривиальное, за которым стоит немало теорем высшей математики,
если прям щас докажешь их всех, то засчитаю.
Считай, что у тебя на вступительном экзамене эта задачка. Свойства степеней, типа при умножении степени складываются и т. д, использовать можно

blackout

Это сразу же следует из трансцендентности e, которая, правда, не столь очевидна :) но общеизвестна.

blackout

Вот другое решение:
sqrt(2)^sqrt(2) либо рационально, тогда sqrt(2) - искомое число. либо иррационально, тогда sqrt(2)^sqrt(2) - искомое число.

maxbut

не в точку

maxbut

при беглом просмотре показалось, что верно, но пока неверно.

ETrohkina

В деревне, где живет пятьдесят семейных пар, каждый из мужей изменял своей жене. Каждая из женщин в этой деревне, как только кто то из мужчин изменил своей жене, немедленно узнает об этом (все знают, как быстро распространяются сплетни в маленьких городках если только это не ее собственный муж (о своих бедах каждый узнает последним). Законы этого городка требуют, чтобы женщина, получившая доказательства неверности своего мужа, убила его в тот же день. Ни одна из женщин не может ослушаться. Однажды королева, славящаяся своей непогрешимостью, приезжает в городок. Она объявляет жителям, что по крайней мере один из мужчин городка совершил супружескую измену. Что произойдет и почему?

Damrad

в первый день не убьют никого, в на второй - всех?

katrinmania

Это что-то из вариаций на эту тему
http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29

Suveren

деревне, где живет пятьдесят семейных пар, каждый из мужей изменял своей жене. Каждая из женщин в этой деревне, как только кто то из мужчин изменил своей жене, немедленно узнает об этом (все знают, как быстро распространяются сплетни в маленьких городках если только это не ее собственный муж (о своих бедах каждый узнает последним). Законы этого городка требуют, чтобы женщина, получившая доказательства неверности своего мужа, убила его в тот же день. Ни одна из женщин не может ослушаться. Однажды королева, славящаяся своей непогрешимостью, приезжает в
через 50 дней замочат все мужики в порядке самообороны замочат своих жён

paoook

изменяют все? значит, королева ничего нового не сказала. Итак каждая жена знает, что 49 остальных изменяют.

zajxam

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

maxbut

Вот более корректная формулировка. Ща проверил, вроде этого достаточно.
  
Известно, что в королевстве из всех жителей есть 40 супружеских пар.
Известно, что:
1) каждая женщина знает все обо всех действиях мужчин, кроме своего мужа (если она замужем конечно.)
2)Женщинам запрещено обсуждать своего мужа с другими
3)Запрещено при женщине обсуждать ее мужа.
4) если жена узнает, что муж изменил ей, то она обязана в полночь этого же дня при всех расстрелять своего мужа на площади.
Однажды королева собрала всех на площади и известила, что среди мужчин есть по крайней мере один изменник.
что произойдет впоследствии и когда.

zajxam

Всех изменников убьют в день номер которого совпадает с их количеством.
Ибо если он один, то та женщина которая не знает ни об одном изменнике поймет, что изменял ей именно ее муж и убьет его в первый же день.
Если их два, то в первый день ни кого не убьют, а на след день, те две женщины чьими мужьями они являются поймут, что их мужья изменяют...
И далее по индукции

maxbut

yes

dilk20089

Есть книга "Aha! Insight" by Martin Gardner. Русский перевод тоже есть, можно найти в электронном виде.
Там много клевых задач, проще чем в других книгах Гарднера и больше подходит для собеседований. В детстве одна из любимых книг была.
Еще есть гугловские тесты GLAT, но там много хардкорных задач, типа найти сопротивление бесконечной решетки, не используя двухмерное дискретное преобразовыние Фурье

ETrohkina

а вот старая, но прикольная:
Встречаются в парке два старых друга, они не виделись много лет.
Первый говорит: Сколько лет твоим детям?
Второй отвечает: Произведение возрастов моих двух детей дошкольного возраста (от 1 до 6) равняется числу ворон, которые находятся напротив нас.
Первый: А можно еще какое-нибудь уточнение?
Второй: Младший похож на свою маму.
После чего первый дал ответ на вопрос: Сколько лет детям?
Подсказка: Оба товарища привыкли формулировать свои мысли точно и не задавать лишних вопросов.

msv27

  Четыре года и один год. :cool:

paoook

А если "младший" на пару часов младше? ;) Так бывает. На самом деле есть задачка про троих детей, она чутка посложнее. Что-то про номер трамвая там было.

ETrohkina

А если не загоняться, то детей с разницей в несколько часов обычно называют близнецами-двойняшками ;)

ILYABUZADZHI

А точно никаких цифр в условии быть не должно? ИМХО, условий что произведение возрастов равно натуральному числу и то, что дети разного возраста - как-то маловато. Или я чего-то не понимаю?

ETrohkina

Оба товарища привыкли формулировать свои мысли точно и не задавать лишних вопросов.

kastodr33

Есть книга "Aha! Insight" by Martin Gardner. Русский перевод тоже есть, можно найти в электронном виде.
Как русская версия называется?

msv27

условий что произведение возрастов равно натуральному числу и то, что дети разного возраста - как-то маловато
Ещё добавь, что дети дошкольного возраста.

ILYABUZADZHI

ну и чем не подходят варианты 1,2 или 2, 4 или еще какой-нить?

dilk20089

Есть книга "Aha! Insight" by Martin Gardner. Русский перевод тоже есть, можно найти в электронном виде.
Как русская версия называется?
Называется "Есть идея"
Скачать

ETrohkina

ну и чем не подходят варианты 1,2 или 2, 4 или еще какой-нить?
Для обоих вариантов не нужна доп инфа. Если он видит 2 или 8 ворон, то разложение одно с ограничениями на возраст.
А в задаче сказано ,что инвестбанкиры лишних вопросов не задают.

Max778

Мне больше интересно, как вообще можно было ее придумать? Очень нестандартно. Поэтому она такая известная.

ETrohkina

Мне кажется два чувака в парке встретились, посчитали ворон и придумали задачу
Задача да, прикольная, жалко что боян.

dilk20089

Это называется метазадачи. Мартин Гарднер, который вел рубрику в Scientific American на протяжении многих лет, посвятил метазадачам один из номеров.

ETrohkina

или вот ещё вариант:
Встречаются в парке два старых друга банкира, они не виделись много лет.
Первый говорит: Ну как дела, как работа?
Второй отвечает: Отлично! На работе две такие тёлки работают, Катя и Лиза!
Первый спрашивает: А какой у них размер?
Второй отвечает: Произведение размеров их грудей равняется числу ворон, которые находятся напротив нас.
Первый: А можно еще какое-нибудь уточнение?
Второй: Катя - блондинка.
После чего первый дал ответ на вопрос: Какой размер у каждой?
Подсказка: Оба товарища привыкли формулировать свои мысли точно и не задавать лишних вопросов.
Подсказка 2: Размеры от 1 до 5
Подсказка 3: У Блондинки по умолчанию больше.

Flat

объясните пожалуйста про задачу с воронами и детьми. как он пришёл к выводу о возрастах?

stel_s

Смотри, там есть n ворон, причем для n есть два разложения на множители n=ab=cd, так что a, b, c, d лежат от 1 до 6 (все числа в задаче натуральные). Если бы разложение n было только одно, то уточнения были бы не нужны. Простым перебором чисел от 1 до 30 (там их меньше на самом деле) получаем, что единственным таким числом является 4=2*2=1*4. А так как есть младший, то вариант 2*2 не подходит, значит, 1 и 4 года

Flat

круто, спасибо :)

sttt

уточнение что маленький размер у блондинки Кати заставляет друга-банкира похотливо перебирать в голове разные варианты, да?)

leonmykopad

с детьми как-то проще... тут сразу представляешь блонидку с грудьми... :o

s4d3v2g

Катя и Лиза
все совпадения имён случайны? :grin:

ETrohkina

Поправил с учётом статистических данных о блондинках. Убрал из условия лишние данные, вынес их в подсказки.
зы. Изначально просто версия строилась по реальным событиям, имена из жизни :)

plush_s

На подобии задачи про детей, только интересней и сложней. Можно решить так, можно с использованием теории чисел. Тоже боянчик кончено, но прикольный, все собираюсь дать кому-нибудь наглому...
Один маленький мальчик загадал два различных числа. Оба строго больше 1 и строго меньше 100, натуральные. Одному мегамозгу он сказал сумму этих чисел, другому - их произведение. Прошла неделя, и два мегамозга встретились.
Тот, кто знал произведение, говорит:
- Ты знаешь, мне не хватает данных, чтобы определить, что за числа загадал маленький мальчик.
- А я знал что тебе не хватит данных! - ответил тот, кто знал сумму.
- Тогда я понял, что за числа он загадал... - сказал тот, кто знал произведение.
- Тогда и я понял... - сказал тот, кто знал сумму.
Что за числа загадал маленький мальчик?

plush_s

Кстати задачу про детей решают все, а вот, если добавить лишнее условие, что сумма месяцев их возрастов равна количеству воробьев на ветке... Условие ничего не значит и ничего не дает, а вот решить задачу не дает :grin: :grin: :grin:

Lokomotiv59

Один маленький мальчик загадал два различных числа. Оба строго больше 1 и строго меньше 100, натуральные. Одному мегамозгу он сказал сумму этих чисел, другому - их произведение. Прошла неделя, и два мегамозга встретились.
Тот, кто знал произведение, говорит:
- Ты знаешь, мне не хватает данных, чтобы определить, что за числа загадал маленький мальчик.
- А я знал что тебе не хватит данных! - ответил тот, кто знал сумму.
- Тогда я понял, что за числа он загадал... - сказал тот, кто знал произведение.
- Тогда и я понял... - сказал тот, кто знал сумму.
Что за числа загадал маленький мальчик?

4 и 13 подходят вроде.

Max778

1 и 6 ? :o

verse3e3

мне казалось, что это тред не занимательных задач, а задач, которые дают на реальных собеседованиях

saper

не подходят по ограничениям, налагаемым условиями на числа

Lokomotiv59

Да, все верно — 4, 13. Программа показывает, что других вариантов нет.

geva

Тут уже пошли задачи для выявления задротов.

ETrohkina

ты её решил чтоль? :grin:

ETrohkina

вот такая ещё на тер.вер:
Есть 3 карты в мешке:
одна с обеих сторон черная,
вторая с обеих сторон белая,
третья с одной стороны черная, с другой белая.
Вы вытягиваете одну карту и видите только одну сторону карты - черную.
Какова вероятность того, что другая сторона будет белой?

katrinmania

Странно, ответ, вроде, должен быть в правом нижнем углу квадрата.

ETrohkina

ещё из фудзи:
На столе лежат четыре карточки. У каждой из них на одной стороне — буква, а на другой — цифра. Естественно, вы видите только одну из сторон:
A, F, 2, 7.
Определите, какую карточку(и) вам нужно перевернуть, чтобы проверить, выполняется ли правило „Если на одной стороне карточки гласная буква, то на другой стороне этой карточки — четное число“.

algraf

во я помню меня как-то спросили эту задачу на собеседовании :grin: компания в последствии разорилась

ETrohkina

хочешь сказать, что компании куда ты ходишь на собеседование потом разоряются?
тогда список давай.

algraf

нет просто ах..эл от пафоса итд. вот там спросили эту задачку ;)

Lokomotiv59

Имеется ввиду, числа близки к 100? Тогда бы тот, кто знает произведение, мог бы узнать и сами числа сразу, так как ему известно, что числа не превосходят 100.
(например, 99*97 нельзя представить в виде 33*291, так как 291 > 100).

incwizitor

Есть 3 карты в мешке:
одна с обоих сторон черная,
вторая с обоих сторон белая,
третья с одной стороны черная, с другой белая.
Вы вытягиваете одну карту и видите только одну сторону карты - черную.
Какова вероятность того, что другая сторона будет белой?
50 % ?

Lokomotiv59

/3. Надо учесть, что черную с обеих сторон карту можно вытянуть любой из 2х сторон наверх.

incwizitor

странно, но я пока не понял почему 1\3 =\
1\3 было бы если бы задача была такая: с какой вероятностью вытащите карту на одной стороне черное, а на второй - белое =)

fifitY

Мне больше нравится 50%, учитывать сторону карты, естественно, не надо (измерения 2, первое уже как бы сделано)
1/3(1/2+1+0)

Lokomotiv59

Вот объясните тогда, где ошибка в рассуждении.
Предположим, что на одной из стороне каждой карты стоит 1, а на другой — 2.
Тогда рассмотрим элементарные события: Ч1Ч2, Ч2Ч1, Ч1Б2, Б2Ч1, Б1Б2, Б2Б1. Вероятность каждого — 1/6.
Искомая вероятность: P(X) = P(Ч1Б2) / (P(Ч1Ч2) + P(Ч2Ч1) + P(Ч1Б2.

katrinmania

Да, я неправильно сказал, я имел в виду просто правее и ниже.
У меня получается, что после первых двух фраз, сумма может быть одной из:
11 17 23 27 29 35 37 41 47 53
Тогда, если загадано (14, 3 то первый, имея только произведение (42 не сможет определить, что загадано, (14, 3) или (21, 2).

Lokomotiv59

Тогда, если загадано (14, 3 то первый, имея только произведение (42 не сможет определить, что загадано, (14, 3) или (21, 2).
ну так есть ведь разница, (14, 3) или (13, 4) :grin:

katrinmania

Ой, пардон
А почему не подходит, скажем, (26, 27)?

Lokomotiv59

Для суммы 53 прога нашла контрпример: (10, 43 (16, 37).
То есть второй (кто знает сумму s=53) не сможет определить (10, 43) или (16, 37). Обе пары обладают тем свойством, что первый бы их отгадал на своем ходу :)

katrinmania

Все, я понял уже.
Тупил, пока картинку не нарисовал

zajxam

ага, только эти контр примеры в ручную как-то сложно очень перебирать, я вот долго пытался понять чем плохо 19 и 4, пока догнал что тот кто знает сумму не смог точно знать они это или же 16 и 7, которое также удовлетворяет первым двум условиям...
Вообще пока не представляю как решить эту задачу, еслиб ответ был немного подальше, и что-то типа тех же 16 и 37..

zajxam

Тупил, пока картинку не нарисовал
Красивое творчество!
А как получил и что оно означает?

Lokomotiv59

Надо спросить у 'а. В любом случае, задача не для собеседования явно.
Хотя 13 и 4 нашел руками, а с помощью компа потом лишь проверил единственность.

zajxam

а с помощью компа потом лишь проверил единственность.
А можешь проверить единственно ли оно если числа скажем брать до 1000, или 10000, а то если нет, то дать какой нибудь начальный интервальчик поубойнее типа числа от 100 и до 1000 :smirk:

antcatt77

> то дать какой нибудь начальный интервальчик поубойнее типа числа от 100 и до 1000
числа от 2 до 1000
и мальчик никогда не загадывал несчастливых чисел
----
числа от 2 до 1000
и мальчик нам по секрету сказал, что никогда не загадывает несчастливых чисел

antcatt77

если нет, то дать какой нибудь начальный интервальчик поубойнее типа числа от 100 и до 1000
или числа от 2 до 3000
но нам мальчик по секрету сказал, что числа меньше 30 он не загадывал

incwizitor

Вот объясните тогда, где ошибка в рассуждении.
Предположим, что на одной из стороне каждой карты стоит 1, а на другой — 2.
Тогда рассмотрим элементарные события: Ч1Ч2, Ч2Ч1, Ч1Б2, Б2Ч1, Б1Б2, Б2Б1. Вероятность каждого — 1/6.
Искомая вероятность: P(X) = P(Ч1Б2) / (P(Ч1Ч2) + P(Ч2Ч1) + P(Ч1Б2.
P(X) = P(Ч1Б2) / (P(Ч1Ч2) + P(Ч1Б2 = 1/6 : (1/6 + 1/6) = 50% ?

Runa

Вероятность того, что карта полностью чёрная 1/3, а не 1/6.
P(ЧЧ) = 1/3, P(ББ) = 1/3, P(ЧБ) = 1/6, P(БЧ) = 1/6

Runa

С планеты Глюк галактики Кин-дза-дза прибыли 3 представителя. Визатор для одного из них покажет синий цвет, для другого – красный, для третьего – розовый. При этом синие всегда врут, красные всегда говорят правду, а розовые отвечают случайно. Проблема в том, что визатор они с собой не привезли, хотя кто есть кто они сами, естественно, знают. Им нужно задать 3 вопроса, чтобы установить кто какому цвету соответствует. Каждый вопрос задаётся только одному из них, любому, т.е. можно одного можно спросить 2 раза, другого вообще не спрашивать. (Задав 1 вопрос троим - считается что задали 3 вопроса). Отвечают они Да и Нет, но на своём языке: У и Ы, что из этого соответствует нашим Да и Нет тоже неизвестно.

incwizitor

Вероятность того, что карта полностью чёрная 1/3
я с этим согласен, но это не используется в формуле
Тогда рассмотрим элементарные события: Ч1Ч2, Ч2Ч1, Ч1Б2, Б2Ч1, Б1Б2, Б2Б1. Вероятность каждого — 1/6.
обозначим события буквами a, b, c, d, e, f соответственно, тогда
P(X) = P(c+e+f | a+b+c) = P(c | a+b+c) + P(e | a+b+c) + P(f | a+b+c) = 1/6 + 1/6 + 1/6 = 1/2
P(c | a+b+c) = P(c*(a+b+c : P(a+b+c) = (1/36 + 1/36 + 1/36) : 1/2 = 1/6
у меня снова получилось 50 % =\
ps: привет ;)

Runa

P(c+e+f | a+b+c)
Это вероятность чего? :)
P(ЧБ) = 1/6
P(ЧЧ) = 1/3
P(ЧБ | первая сторона Ч) = P(ЧБ) / (P(ЧБ)+ P(ЧЧ = 1/6 / (1/6 + 1/3) = 1/3
ps Привет :)

incwizitor

Это вероятность чего?
ты выбиваешься из нашего разделения вероятностного пространства. ты чувствуешь разницу между Ч1Ч2 и Ч2Ч1 ? разница в том, что написано на _верхней_ стороне карты. первые два символа я отношу к верхней стороне.
вероятность чего я считаю:
P(нижняя сторона белая+написано 1 либо белая и написано 2 | верхняя сторона черная+написано 1 либо черная+написано 2)

ETrohkina

Надо посчитать вероятность вытягивания чёрно-белой, при условии что вытянул карту чёрной стороной. Вот и считай по формуле условной вероятности.
Откуда 50%?

incwizitor

Надо посчитать вероятность вытягивания чёрно-белой, при условии что вытянул карту чёрной стороной. Вот и считай по формуле условной вероятности.
согласен, давай я попробую:
P (на карте есть белая сторона | на карте есть черная сторона) = P(на карте есть и белая и черная сторона) : P(на карте есть черная сторона) = 1/3 : 2/3 = 1/2 :grin:
мне кажется очевидным, что искомая величина строго больше 1\3 = вероятность вытащить в точности карту с белой+черной стороной, т.к. нам помогли уже с одной стороной (нам нахаляву сделали черную сторону, осталось разобраться со второй стороной). эту помощь я оцениваю в 2\3 (вероятность вытащить карту с черной стороной) и получаю снова 1\3 : 2\3 = 1\2
что же неправильно в моих рассуждениях? =\

antcatt77

P (на карте есть белая сторона | на карте есть черная сторона) = P(на карте есть и белая и черная сторона) : P(на карте есть черная сторона) = 1/3 : 2/3 = 1/2
ты здесь еще зачем-то учел, тот случай - когда мы вытянули чернобелую карту - белой стороной вверх

blackout

P (на карте есть белая сторона | на карте есть черная сторона)
Это было-бы искомой вероятностью при условии:
Есть 3 карты в мешке: ...
Одна из сторон случайно вынутой карты - черная.
Какова вероятность того, что другая сторона будет белой?
В то время как рельное условие:

Есть 3 карты в мешке: ...
Вы вытягиваете одну карту и видите только одну сторону карты - черную.
Какова вероятность того, что другая сторона будет белой?

incwizitor

хм, я действительно понял задачу не так, как все =\
то есть следует читать так: какова вероятность того, что вытащив карту и увидев на ней черную верхнюю сторону, вы увидите белую нижнюю?
тут тогда я вообще не вижу условной вероятности - это вероятность вытащить карту черое+белое = 1\3

incwizitor

не выдержал и полез в инет=)
http://en.wikipedia.org/wiki/Bertrand's_box_paradox
спасибо за интересную задачку
парадоксы всегда вызывают много вопросов)

blackout

тут тогда я вообще не вижу условной вероятности - это вероятность вытащить карту черое+белое = 1\3
Нет, не так.
Пусть было 4 карты - ЧЧ ЧЧ ЧБ и ББ, а все остальное так же. Тогда по твоей логике ответ 1/4 - вероятность вытащить ЧБ. Хотя на самом деле ответ 1/5.

saper

На столе лежат четыре карточки. У каждой из них на одной стороне — буква, а на другой — цифра. Естественно, вы видите только одну из сторон:
A, F, 2, 7.
Определите, какую карточку(и) вам нужно перевернуть, чтобы проверить, выполняется ли правило „Если на одной стороне карточки гласная буква, то на другой стороне этой карточки — четное число“.

vitamin8808

розовые отвечают случайно.
Если такого два раза подряд один и тот же вопрос спросить он ответ поменяет, или может оба раза тоже самое ответить?

Runa

Как хочет, так и отвечает. Рандомно.

Nefertyty

Всех изменников убьют в день номер которого совпадает с их количеством.
Ибо если он один, то та женщина которая не знает ни об одном изменнике поймет, что изменял ей именно ее муж и убьет его в первый же день.
Если их два, то в первый день ни кого не убьют, а на след день, те две женщины чьими мужьями они являются поймут, что их мужья изменяют...
И далее по индукции
если юрист так ответит, его ж нельзя брать

Logon

Немного не в кассу, но вопрос тоже с собеседования (на рабфак географического факультета с него сыпалась половина поступающих:
Может ли на экваторе быть снег? Если да/нет, то почему?

lordkay

Может ли на экваторе быть снег? Если да/нет, то почему?
наверное может, какие-нить горы в кении, например

stm767951122

то есть следует читать так: какова вероятность того, что вытащив карту и увидев на ней черную верхнюю сторону, вы увидите белую нижнюю?
Ха!
А я только хотел объяснить парням, что они не понимают, что такое условная вероятность :)

lordkay

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

blackout

Или холодильник.

lordkay

ну холодильник это чит, я думаю, что имеется ввиду естественный способ

FieryRush

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

Runa

Два человека договариваются о встрече. Каждый может прибыть на место встречи в произвольное время между 15ч. и 16ч. и ждать 10мин. Какова вероятность того, что они встретятся?

stm7542793

Два человека договариваются о встрече. Каждый может прибыть на место встречи в произвольное время между 15ч. и 16ч. и ждать 10мин. Какова вероятность того, что они встретятся?
11/36. Решпется графически.

Runa

правильно

paoook

Решпется графически
интеграл предлагаю взять

antcatt77

Каждый может прибыть на место встречи в произвольное время между 15ч. и 16ч. и ждать 10мин. Какова вероятность того, что они встретятся?

5/18
(Z)для начала зафиксируем, что если один пришел, то чтобы второй с ним встретился, он должен придти в момент, когда первый уже есть, или в один из моментов, на 10 минут раньше
время можно разбить на три интервала: первые десять минут, середина, и последние десять минут
если первый пришел в первые 10 минут, обозначим как k, то по Z, второй должен придти в интервал 10мин+k
если первый пришел в последние 10 минут (до конца 16ч, осталось k то по Z, второй должен придти в интервал k + 10мин
если первый пришел в остальное время, то по Z, у второго на это есть интервал 20 минут
весь интервал: 1ч, отсюда - 10мин=1/6
итого: 1/6 *интеграл по k от 0 до 1/6 (1/6+k) + 4/6*2/6+1/6 *интеграл по k от 0 до 1/6 (1/6+k)=1/36+8/36+1/36=10/36=5/18

antcatt77

откуда берется несимметрия?
почему 11/36, а не 10/36?
на обоих же краях - симметричные проблемы.

incwizitor

откуда берется несимметрия?

если первый пришел в последние 10 минут (до конца 16ч, осталось k то по Z, второй должен придти в интервал k + 10мин , но не позже 16
?

katrinmania

произвольное время между 15ч. и 16ч.
это равномерное распределение, что ли?

antcatt77

если первый пришел в последние 10 минут (до конца 16ч, осталось k то по Z, второй должен придти в интервал k + 10мин
> но не позже 16
это как раз уже учтено в k, т.к. k - это сколько времени осталось до 16 часов (смотри определение а "+ 10" - это в интервал на 10 минут раньше
такое же симметричное есть и с начала периода
второй может придти раньше, но не раньше 15 часов
поэтому я и говорю, что задача симметричная, а правильный ответ по agassi получается несимметричный.

Suebaby

что значит "несимметричный"? 11 делится на 2. Получается 5 с половиной.

incwizitor

я вижу несимметричность именнов длинах интервала для второго чувака
если k+ 10 означает 10 минут назад, то "но" я не там поставил:
а) если первый пришел в первые 10 минут, обозначим как k, то по Z, второй должен придти в интервал 10мин+k, но не раньше 15
б) если первый пришел в последние 10 минут (до конца 16ч, осталось k то по Z, второй должен придти в интервал k + 10мин
заметь, "но" здесь только одно и в этом я вижу несимметричность.
для а) размер интервала переменный, для б) интервал когда может прийти второй - строго равен 10 минут
для первого чувака "но" не существует - он приходить в отрезке [15, 16часов]

antcatt77

если k+ 10 означает 10 минут назад, то "но" я не там поставил:
расписываю подробно
второй человек может придти во время, когда первый пришел (обозначим это время как k1 или придти раньше менее чем на 10 минут (обозначим это время как k2)
для середины (с 10 по 50 минуты) - k1=k2=10, итого: k1+k2=10+10=20
для начала - k1=10, k2=k, т.к. если второй придет ранее, чем за k минут, то он не впишится в 15 часов
итого: k1+k2=10+k
для конца - k1=k, k2=10, т.к. если второй придет позже, чем на k минут от прихода первого, то он не впишется в 16 часов.
итого: k1+k2=k+10
т.е. начало и конец симметричны: k+10
вопрос все тот же самый:
откуда берется несимметрия?

antcatt77

что значит "несимметричный"? 11 делится на 2. Получается 5 с половиной.
если была бы симметрия, то получилось бы 10/36 = средний интервал - 8/36 + два боковых по 1/36

FieryRush

поэтому я и говорю, что задача симметричная, а правильный ответ по agassi получается несимметричный.
Норесуй квадрат и посчитай площадь точек с разницей координат не более 10 мин. Все у него правильно.

Suebaby

фигура задаётся такими неравенствами:
|x-y|<1/6
15<x<16
15<y<16
(x, y — моменты прибытия людей, всё в часах)
согласен?
площадь фигуры равна 11/36
согласен?

katrinmania

Забавно наблюдать, когда чуваки пытаются решить задачку, сформулированную в терминах житейской логики. Каждый при этом решает задачу строго, с помощью математики, но понятия о житейской логике у каждого свои.
Самый яркий пример был с транспортером и самолетом. Вот тут тоже весело, учитывая, что никто не сказал, какое распределение у времени прихода каждого из чуваков

incwizitor

графический комент

симметрия, конечно, есть и осевая и центральная, но хз как можно было ее увидеть в результате=) симметрии по оси времени нет

antcatt77

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

Runa

это равномерное распределение, что ли?

Да.

antcatt77

площадь фигуры равна 11/36
согласен?
согласен. будет 11/36,
рассуждения у меня были правильные, но я сделал арифметическую ошибку: неправильно посчитал интеграл.
интеграл по k от 0 до 1/6 (1/6+k) = 1.5/36, а у меня получилось 1/36

zajxam

И на 1/6 ты этот интеграл тоже зря домножал :)

antcatt77

И на 1/6 ты этот интеграл тоже зря домножал
согласен зря написал "1/6 * интеграл..", но при вычислении я схитрил, и в итоге на эти 1/6 не домножал :)

paoook

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

katrinmania

и получай какой угодно ответ

paoook

ну да. Типо решил задачу в общем виде :grin:

zajxam

поэтому надо брать интеграл по часть плоскости уже нарисованной тут кем-то. Бери хоть какое распределение и считай.
мог у ошибаться, но для произвольного распредения, то-что нарисовано будет как-бы видом сверху на некую двумерную поверхность, и для ответа придется считать не площадь, а объем. А то что нарисовано как раз учитывает, что распределение равномерное и та двумерная поверхность на которую мы смотрим сверху есть просто плоскость.

Runa

Никому неинтересно, как решается задача про 3-х представителей с планеты Глюк? :)
Могу дать подсказки.

lordkay

С планеты Глюк галактики Кин-дза-дза прибыли 3 представителя. Визатор для одного из них покажет синий цвет, для другого – красный, для третьего – розовый. При этом синие всегда врут, красные всегда говорят правду, а розовые отвечают случайно. Проблема в том, что визатор они с собой не привезли, хотя кто есть кто они сами, естественно, знают. Им нужно задать 3 вопроса, чтобы установить кто какому цвету соответствует. Каждый вопрос задаётся только одному из них, любому, т.е. можно одного можно спросить 2 раза, другого вообще не спрашивать. (Задав 1 вопрос троим - считается что задали 3 вопроса). Отвечают они Да и Нет, но на своём языке: У и Ы, что из этого соответствует нашим Да и Нет тоже неизвестно.
сложно условие, тяжело все разложить, прикольнее когда условие простое, а решение сложное, а тут скорее всего все станет понятно, когда до конца разберешься в условии
а что такое визатор и как его можно использовать?

Runa

Просто в таком описании её узнал.
прикольнее когда условие простое, а решение сложное
По-моему, как раз тот случай.
По сути есть Правдивец, Лжец и Чудак, отвечающий совершенно случайно. Нужно за 3 вопроса с ответами Да/Нет узнать кто есть кто. Сами они знают кто есть кто. Вопрос каждый задаётся только одному. Можно и один вопрос всем задать, но будет считаться что задали 3 вопроса. И ещё, вместо Да/Нет они отвечают У/Ы. Что именно из У/Ы Да, что Нет - неизвестно.

blackout

Если задать вопрос "У значит да?" и первые двое дадут одинаковый ответ, то задав другой вопрос третьему можно все узнать. А вот если разный, то нет :(

vitamin8808

Решается так: нужно свести задачу к уже известной(я такое уже решал когда язык их знаешь, это совсем просто, в кванте для младших школьников было). Просто нужно сконструировать такой способ задавать вопросы, чтобы он от языка не зависел.
То есть нужно решить такую задачу:
Вы очутились на дороге между двумя городами, городом Лжецов и городом Правдецов,
но не знаете в какой стороне какой город. Вам повстречался местный житель. Он либо лжец, либо всегда говорит правду. Как с помощью одного вопроса выяснить, в какой стороне какой город Правдецов, при условии что вы не знаете что означает да, а что нет?
ответ говорить не буду :)
ЗЫ на эту задачу есть такой шуточный ответ — спросить "знаете ли вы, что в городе Правдецов сегодня бесплатно наливают пиво?". Ну а потом просто проследовать за чуваком вне зависимости от ответа.

blackout

Пусть мы хотели спросить, верно ли высказывание А. Вместо этого спросим: "Верно ли, что из А и "У значит нет" верно только одно?".
Если А верно, то честный ответит У, если неверно - то Ы. Лжец - наоборот.
Таким образом можно спрашивать такие удлинненные вопросы, считая что У значит да.

stm5994768

вопрос: в какой стороне твой город? куда ответит там и Правдецы )

vitamin8808

вопрос: в какой стороне твой город? куда ответит там и Правдецы )
Неверно, так как они отвечают да или нет, да ещё и на своём языке.

blackout

Вот решение про Кин-Дза-Дзу:

Про то, что можно считать, что они отвечают да и нет вместо У и Ы уже написано выше.
Аналогично, вместо верности утверждения А можно спрашивать: "Верно ли только одно из А и "Ты лжец"?".
И честный и лжец ответят да, если А верно и нет, если не верно.
Теперь можно считать, что у нас два честных и один идиот. Первыми двумя вопросами определим идиота, а третьим - лжеца.
Спросим у первого "второй идиот?" и у второго "третий идиот?". Для любого из четырех вариантов ответа идиот определяется однозначно.
Теперь у одного из двух оставшихся спросим "2*2 = 4?", если ответил да - то но честный.

Runa

Пусть на первые два вопроса ответы ДА, НЕТ. Кто идиот?

uvilir

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

sergeychik_a

замутить из нее компас!
Мир Вам!

Suveren

типа на всякие вышки лазить. монтажницей.

stel_s

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

h_alishov

в метро нашли девочку-магнит
как её можно использовать в народном хозяйстве?
если отключат свет, ее можно заставить бегать вокруг трансформатора.

sttt

в метро нашли девочку-магнит
как её можно использовать в народном хозяйстве?
в случае поломки магнитов адронного коллайдера затыкать ей дыры :)

Cvikli

Вот более корректная формулировка. Ща проверил, вроде этого достаточно.

Известно, что в королевстве из всех жителей есть 40 супружеских пар.
Известно, что:
1) каждая женщина знает все обо всех действиях мужчин, кроме своего мужа (если она замужем конечно.)
2)Женщинам запрещено обсуждать своего мужа с другими
3)Запрещено при женщине обсуждать ее мужа.
4) если жена узнает, что муж изменил ей, то она обязана в полночь этого же дня при всех расстрелять своего мужа на площади.
Однажды королева собрала всех на площади и известила, что среди мужчин есть по крайней мере один изменник.
что произойдет впоследствии и когда.
Клёвая задачка. Особенно понравился эффект, если королева соврала

ETrohkina

ETrohkina

Слепой дровосек случайным образом рубит палку на три части.
Какова вероятность того, что из ее обломков можно составить треугольник?

lordkay

1/4?

ETrohkina

Si.
Тогда и решение туда же )

Runa

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

Suebaby

Если сначала равновероятно на 2 части разрубается, затем вторую часть снова случайным образом равновероятно на 2 части - ответ другой
если при этом произвольным образом выбирается, какая из частей первая, а какая — вторая, то всё ОК, ответ такой же, как и в случае двух зарубок. А слепой дровосек, конечно, не будет париться, какая из частей — "вторая".

Kizel

 Мне кажется, что треугольник из трёх частей можно составить тогда и только тогда, когда самая большая часть не длиннее двух других в сумме. То есть в нашей ситуации ни одна из частей не должна оказаться длиннее, чем половина от изначальной палки.
Исходя из этого положения ответ 50%.
Считаем так. Случайным образом производим первый разруб. Считаем ту половину палки, на которой произошёл разруб первой (вариант, когда слепой лесоруб разрубил палку ровно пополам не учитываем, так как вероятность такого события примерно равна нулю). Теперь собираемся сделать второй разруб случайным образом по всей длине. И видим, что если разруб придётся на первую половину, то у нас останется кусок палки больший, чем половина всей палки. А если разруб придётся на вторую половину, то таких кусков не будет, и треугольник можно будет составить. Так что 50%
Нда, решение неправильное :)

dunaeva81

большая часть не длиннее двух других
строго короче
и как ты учитывать будешь вероятность разрубания пополам?

stm5994768

Пусть а - точка первого удара, b - точка второго удара
тогда вероятность того, что один кусок не больше суммы других следующая:
P = p(a<0,5|b>0,5)*p(b-a>0,5) + p(a>0,5|b<0,5)*p(a-b>0,5) = 1/4*1/2 + 1/4* 1/2 = 1/4

stm5994768

Неверно, так как они отвечают да или нет, да ещё и на своём языке.
Т.е. вопрос я задать смогу на их языке, а ответ понять не смогу?
В условии не говорилось про только да/нет

s4d3v2g

stm8886619

x+y<z еще надо, тогда у тебя остается половина квадрата и как раз 1/4

s4d3v2g

да командир, все верно

ETrohkina

По теории упругости вообще квадрат получается с вер-ю 100%
Решение писать не буду, а то Мурзик прибежит, абасрёт всё

katrinmania

ETrohkina

В некоторых компаниях можно такую задачку дать:
Человек, делающий это, в нем не нуждается; человек, покупающий это сам им не пользуется, а человек пользующийся этим об этом не знает.

katrinmania

Аппарат для жизнеобеспечения

ETrohkina

Как вариант. Самый прикольный имхо гроб :)

ETrohkina

А вот из жизни:
Почему в Москве пик пробок и преступлений попадает на четверг?
Про пробки из личных наблюдений пики по вторникам и четвергам.

lordkay

гроб?

ETrohkina

йад

dunaeva81

Почему в Москве пик пробок и преступлений попадает на четверг?
последний полноценный рабочий день на неделе?

katrinmania

последний рабочий день — пятница

Damrad

не занудствуй. все прекрасно понимают, что четверг

katrinmania

тогда и среду можно такой считать
и вторник
и понедельник

lordkay

>>последний полноценный рабочий день на неделе?
вообще, последний и единственный полноценный рабочий день тогда среда, а все остальное или подготовка к работе или подготовка к выходным:)

Damrad

ага. в понедельник еще все спят. во вторник только начинают раскачиваться

soba

студент

Runa

Сюда же попадает и то, что для маленьких детей. Памперсы, детское питание и т.д. :)

saper

Вариант задачи про волка, козу и капусту...
На одном берегу реки стоят 8 человек:
 - милиционер,
 - преступник,
 - мать и две её дочери,
 - отец и два его сына.
Так же, на берегу есть плот на двух человек. Требуется перевезти всех на другой берег, не оставляя на одном берегу:
 - девочек с отцом без матери;
 - мальчиков с матерью без отца;
 - преступника с кем-либо ещё без милиционера.
Так же, правилами запрещено садить на плот детей без взрослых, а также пытаться переправить на другой берег плот без людей. Естественно, с начала до окончания переправы все её участники не отходят от берегов.
p.s.: где-то читал, что в Японии такую задачку иногда дают при приёме на работу по некоторым специальностям.

geva

эта задачка и во флеше есть, например http://freeweb.siol.net/danej/riverIQGame.swf

paoook

преступника с кем-либо ещё без милиционера.
там решение очень "логичное". Первым действием оставить одного преступника на противоположном берегу.

oleg1966

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

geva

а ответы, комментарии к ним снести во внутрь каждого сообщения... вотс.

Надо бы, только движок форума это пока не поддерживает. Надо будет сносить все обсуждения в мусорку и дублировать в обсуждение из-под модераторского ника. Пусть будет как есть.

Damrad

там решение очень "логичное". Первым действием оставить одного преступника на противоположном берегу.
ну типа считается что преступник в кандалах и далеко не убежит, а если оставить с кем-нибудь, кроме мента, то и придушить может. Так что с логикой там нормально

AIR1kk

не оставляя на одном берегу:
- девочек с отцом без матери;
- мальчиков с матерью без отца;
а почему нельзя вот так оставлять? :shocked:

saper

а почему нельзя вот так оставлять? :shocked:
произойдёт изнасилование :grin:

antcatt77

произойдёт изнасилование
кого кем? :)

AIR1kk

пиздец задача тогда :shocked: :grin:

mamishka

решение:
М – мент
П – преступник
О – отец
о – сыновья
Х – мать
х – дочери
Л – лодка
|| - речка
1. МП Ооо Ххх Л ||
2. Ооо Ххх || Л МП
3. М Ооо Ххх Л || П (тупо, конечно, но приходится преступника оставлять одного)
4. Оо Ххх || Л МП о
5. МП Оо Ххх Л || о
6. МП Ххх || Л Ооо
7. МП О Ххх Л || оо
8. МП хх || Л Ооо Х
9. МП Ххх Л || Ооо (следующим действием получим ситуацию симметричную этой)
10. Ххх || Л МП Ооо (ну а теперь делаем зеркальные действия, перетаскивая остатки народу)
11. МП Ооо Ххх Л || МП оо
12. хх || Л МП Ооо Х
13. Ххх Л || МП Ооо
14. х || Л МП Ооо Хх
15. МП х Л || Ооо Хх
16. П || Л М Ооо Ххх (в очередной раз оставляем преступника в одиночестве. Вот она - плата за педофилию)
17. МП Л || Ооо Ххх
18. || Л МП Ооо Ххх
Оставить комментарий
Имя или ник:
Комментарий: