Перейти к содержимому

Фотография

Прелестная задачка

- - - - -

  • Авторизуйтесь для ответа в теме
Сообщений в теме: 20

#1
Vadziku

Vadziku

    Один, просто Один

  • В доску свой
  • 17 674 сообщений
Вот, на экслеровском форуме изящная задачка промелькнула, есть над чем поломать голову  :smoke:

Задача про 12 шаров и 3 взвешивания
Программист из Львова сказал, что те, кто решает эту задачу за 2 часа принимаются на Лондонскую биржу.
Мы с ним поспорили (в поезде на Москву), что решим эту задачу за час :fie:

Решение пришло на 45-й минуте, но так как все к этому времени приняли изрядную дозу пива, доказывали мы друг другу истину до самого утра. Таможенники нас не трогали и относились с пониманием.

Условия:
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно)
Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну"
Есть 3 взвешивания, которые можно сделать

Необходимо определить какой из шаров - имеет аномальную массу
  • 0

#2
udaFF

udaFF

    Читатель

  • В доску свой
  • 1 587 сообщений
Очень просто:
1 взвешивание - на каждой из чашек по 6 шаров,
выкидываем 6 шаров, которые больше (меньше)
2 взвешивание - взвешиваем на каждой из чашек по 3 шара, выкидываем 3 шара, которые больше (меньше)
3 взвешивание - взвешиваем любые два шара, если равно, то третий шар искомый и так далее.
  • 0

#3
Da_ReBeL

Da_ReBeL

    цыник и падонак

  • В доску свой
  • 2 022 сообщений
2Udaff
ни пайдет... ты ж не знаиш, больше он или меньши... тебе уже панадабицца 4 взвешивания минимум.
  • 0

#4
udaFF

udaFF

    Читатель

  • В доску свой
  • 1 587 сообщений
ну тады ой, буду думать :0)
  • 0

#5
шрайбикус

шрайбикус

    вечный глюк

  • В доску свой
  • 4 891 сообщений

Очень просто:
1 взвешивание - на каждой из чашек по 6 шаров,
выкидываем 6 шаров, которые больше (меньше)
2 взвешивание - взвешиваем на каждой из чашек по 3 шара, выкидываем 3 шара, которые больше (меньше)
3 взвешивание - взвешиваем любые два шара, если равно, то третий шар искомый и так далее.


так ведь загвоздка в том, что

12-й либо тяжелее, либо легче (это неизвестно)

так что неизвестно какие первые 6 шаров вы выкинете, все одинаковые или с тем самым 12-м
  • 0

#6
Joe Hollenbeck

Joe Hollenbeck

    "Доцент"

  • В доску свой
  • 3 473 сообщений

Условия:
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно)
Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну"
Есть 3 взвешивания, которые можно сделать
Необходимо определить какой из шаров - имеет аномальную массу

1. Если допустить что на каждую сторону весов можно положить только один шар то 3*2=6 => задача нерешаема.
2. Так что допустим что на весы можно класть неопределенное количество шаров.
Вариант с 6 и 6 на первом взешивании мертворожденный.
Пробуем так:
1. 4 и 4 (Допустим что первая четверка тяжелее)
2. первая четверка и оставшиеся невзвешенными 4.
Тут два варианта:
Если равный вес - значит в первом взвешивании более легкий шар во второй четверке.
Если Первая четверка тяжелее - значит в ней более тяжелый шар.
В 1 пункте можно сделать любое допущение - выводы будут аналогичными.
Таким образом после 2х взвешиваний мы получаем 4 шара среди которых есть один аномальный и мы точно знаем тяжелее остальных он или легче.
НО за одно взвешивание узнать который из них ОН я не знаю как.
Так что задачку я не решил :fie:
Будем думать дальше...
  • 0

#7
Vadziku

Vadziku

    Один, просто Один

  • В доску свой
  • 17 674 сообщений
Задачка нетривиальная. Понятно, что надо перегруппировывать шарики, вопрос в алгоритме перегруппировки.
  • 0

#8
Joe Hollenbeck

Joe Hollenbeck

    "Доцент"

  • В доску свой
  • 3 473 сообщений
А вот и решение:
Все как в моем предыдущем варианте но взвешивание производится по 3 шара! Все сходится - ЭВРИКА!!!!!
  • 0

#9
Joe Hollenbeck

Joe Hollenbeck

    "Доцент"

  • В доску свой
  • 3 473 сообщений
Задачку я увидел в 17.35 ответ пришел в голову в 18.05. Даже если не учитывать то, что меня отвлекали на работе, то получается 30 минут - это получше чем 45 минут :fie:
  • 0

#10
Старая Волчица

Старая Волчица

    .

  • В доску свой
  • 2 693 сообщений

А вот и решение:
Все как в моем предыдущем варианте но взвешивание производится по 3 шара! Все сходится - ЭВРИКА!!!!!

это как это?  :fie: а если при первом взвешивании 3+3 вес равный?  :smoke:
  • 0

#11
шрайбикус

шрайбикус

    вечный глюк

  • В доску свой
  • 4 891 сообщений
Решил вроде  :fie:

надо только сначала пометить шары: 1 2 3 4 5 6 7 8 9 10 11 12

1. (1 2 3 4 х 5 6 7 8) уравнялись - см.2, не уравнялись - см.3

2. (1 2 3 х 10 11 12) уравнялись - искомый ?9, не уравнялись - см.2-2

2-2. Из 2. известно, тяжелее или легче дефектный, потому что 1 2 3 нормальные. Поэтому (10 х 11) уравнялись - дефектный ?11, не уравнялись - дефектный тот, кто ведет себя, как 10 11 12 в 2.

3. Тасуем колоду. 9 10 11 12 - нормальные, взвешиваем теперь (1 6 7 8 х 5 10 11 12). Если перекос весов не изменился, то дефектный или 1 или 5 (см.3-1) Если изменился, то дефектный 6 7 8 (см.3-2), если весы уравнялись, то дефектный 2 3 4(см.3-3)

3-1. взвешиваем (1 х 10) Если равны, то 5, если неравны, то 1

3-2. взвешиваем (6 х 7). Равны - искомый ?8, не равны - тот, кто перекосил, как в п.1.

3-3. взвешиваем (2 х 3) Равны - искомый ?4, не равны - тот, кто перекосил, как в п.1.

блин сколько бумаги исписал  :smoke:
уж подумал консилиум с секретаршей созвать
  • 0

#12
шрайбикус

шрайбикус

    вечный глюк

  • В доску свой
  • 4 891 сообщений
надо отдать должное Joe Hollenbeck

он дал кое-какие идеи в своем посте для дальнейших размышлений

итог: полтора часа раздумий с перекурами
  • 0

#13
Старая Волчица

Старая Волчица

    .

  • В доску свой
  • 2 693 сообщений
кажется ошибочка вышла...
:fie:
  • 0

#14
шрайбикус

шрайбикус

    вечный глюк

  • В доску свой
  • 4 891 сообщений

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


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

#15
Старая Волчица

Старая Волчица

    .

  • В доску свой
  • 2 693 сообщений

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

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

да, написала, потом Ваш ответ прочитала и поняла, где моя ошибка... стереть бесследно не успела    :smoke:  :)
  • 0

#16
шрайбикус

шрайбикус

    вечный глюк

  • В доску свой
  • 4 891 сообщений

да, написала, потом Ваш ответ прочитала и поняла, где моя ошибка... стереть бесследно не успела    :smoke:  :)


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

тему мона закрывать, если кто нибудь не найдет более легкого решения
  • 0

#17
Старая Волчица

Старая Волчица

    .

  • В доску свой
  • 2 693 сообщений

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

в смысле, как у Вишневского "Любимая, да ты и собеседник?!... "  :)  :) peace :)

сорри за офф :smoke:
  • 0

#18
Vadziku

Vadziku

    Один, просто Один

  • В доску свой
  • 17 674 сообщений

А вот и решение:
Все как в моем предыдущем варианте но взвешивание производится по 3 шара! Все сходится - ЭВРИКА!!!!!

А как именно по 3 шара? Решение - в студию  :fie:
У aday решение отличается от того что было на экслеровском. Там были группы по 4, правда группы по 4 позволяют различить 13 шаров, и это теоретический предел.
  • 0

#19
шрайбикус

шрайбикус

    вечный глюк

  • В доску свой
  • 4 891 сообщений

У aday решение отличается от того что было на экслеровском. Там были группы по 4, правда группы по 4 позволяют различить 13 шаров, и это теоретический предел.


но ведь правильно я решил, неважно по 3 или 4  :fie:
можете опубликовать решение экслеровского форума?
спасибо
  • 0

#20
Vadziku

Vadziku

    Один, просто Один

  • В доску свой
  • 17 674 сообщений

У aday решение отличается от того что было на экслеровском. Там были группы по 4, правда группы по 4 позволяют различить 13 шаров, и это теоретический предел.

но ведь правильно я решил, неважно по 3 или 4  :fie:
можете опубликовать решение экслеровского форума?
спасибо

Да кто спорит - правильно. Я просто сказал, что решение другое.
  • 0




Количество пользователей, читающих эту тему: 0

пользователей: 0, неизвестных прохожих: 0, скрытых пользователей: 0

X

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

© 2011-2016 vse.kz. При любом использовании материалов Форума ссылка на vse.kz обязательна.