Автор Тема: Задача про шарики и взвешивания  (Прочитано 2490 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Zwer

  • Новичок
  • *
  • Сообщений: 1
    • Просмотр профиля
Задача про шарики и взвешивания
« : 24 Октябрь 2013, 02:10:15 »
Всем привет.

Ребята, помогите решить очень интересную задачу.

Дано: 18 шаров, 15 из них весом 100 гр. остальные 3 - по 99 гр. Весы показывающие точный вес. Все шары пронумерованы, 3 шара по 99 гр. обязательно лежат подряд.

Вопрос: как за 2 взвешивания найти 3 шара по 99 гр.?

Оффлайн zer0

  • Ветеран
  • *****
  • Сообщений: 688
    • Просмотр профиля
    • E-mail
Re: Задача про шарики и взвешивания
« Ответ #1 : 24 Октябрь 2013, 03:06:52 »
Попробуй для 1-го взвешивания взять 1-3, 8-10, 15-18 шары.

Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Задача про шарики и взвешивания
« Ответ #2 : 26 Октябрь 2013, 03:11:47 »
весы могут определить количество лёгких шаров среди взвешиваемых
x=0..3 - количество лёгких шаров на весах при первом взвешивании
y=0..3 - при втором
нужно распознать позицию тройки лёгких шаров (16 вариантов)
если мысленно прогнать эту тройку лёгких шаров подряд по всем их возможным позициям с 1-3 по 16-18, то в терминах (x,y) мы получим обход королём всех клеток шахматной доски 4х4.  но не все пути могут получиться (грубо говоря, нельзя разворачиваться в центре доски).  поэтому возьмём какой-нибудь допустимый путь обхода (напр., спираль или змейку) и восстановим по нему взвешиваемые множества шаров
спираль даёт взвеш.№1(1,2,4,7-12) и взвеш.№2(3,4,10-15)
змейка даёт взвеш.№1(4-7,12-15) и взвеш.№2(1-6,8,9,12)

Оффлайн zer0

  • Ветеран
  • *****
  • Сообщений: 688
    • Просмотр профиля
    • E-mail
Re: Задача про шарики и взвешивания
« Ответ #3 : 30 Октябрь 2013, 19:14:57 »
CD_Eater, можно поподробнее, с картинками?   Для простых форумчан, у которых не столь развито абстрактное мышление :)

Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Задача про шарики и взвешивания
« Ответ #4 : 31 Октябрь 2013, 00:10:30 »
я ступил и подумал, что требуется найти 2 независимых взвешивания (когда второе взвешивание не зависит от результатов первого), отсюда такое нетривиальнео решение
на самом деле этого не требуется ))

пояснение к моему решению: пусть первые ходы обхода доски королём будут
(0,0) - (0,1) - (0,2) - (0,3) - (1,3) - (1,2) - ...
тогда найдём такие два множества А и Б чисел от 1 до 18, чтобы
среди чисел (1,2,3) было 0 чисел из А и 0 чисел из Б,
среди чисел (2,3,4) было 0 чисел из А и 1 число из Б,
среди чисел (3,4,5) было 0 чисел из А и 2 числа из Б,
среди чисел (4,5,6) было 0 чисел из А и 3 числа из Б,
среди чисел (5,6,7) было 1 число из А и 3 числа из Б,
среди чисел (6,7,8) было 1 число из А и 2 числа из Б,
...
взвешиваем в первый раз те шары, номера которых которые вошли в мн-во А, во второй раз - в мн-во Б.
по количеству лёгких шаров (x, y) определяем клетку на шахматной доске и её порядковый номер (k) при обходе королём, тогда лёгкие шары - это k, k+1 и k+2.

Оффлайн NEDLAND

  • Новичок
  • *
  • Сообщений: 2
    • Просмотр профиля
    • E-mail
Re: Задача про шарики и взвешивания
« Ответ #5 : 05 Декабрь 2013, 02:27:30 »
1 взвешивание: шары 1-9, если вес 899 или 898 - ответ очевиден, если 900 или 897, то взвешиваем три средние шара легкой группы, если 297 - определили, но если 298 или 299 или 300, то нужно 3-е взвешивание.

Оффлайн zer0

  • Ветеран
  • *****
  • Сообщений: 688
    • Просмотр профиля
    • E-mail
Re: Задача про шарики и взвешивания
« Ответ #6 : 05 Декабрь 2013, 22:04:36 »
И какой смысл в этом "решении" ?  :o