2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Взвешивания
Сообщение19.10.2014, 15:19 
Заслуженный участник
Аватара пользователя


18/12/10
1600
spb
Есть 9 шаров: 8 из них одинаковы по массе, а один - легче. Можно ли на чашечных весах за 4 взвешивания определить шар, который легче, если известно, что весы ровно один раз показывают неправильный результат

 Профиль  
                  
 
 Re: Взвешивания
Сообщение20.10.2014, 07:22 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
I) Для начала рассмотрим случай, когда весы никогда не врут.
Пронумеруем шары и расположим их в таблице 3x3:
    1 2 3
    4 5 6
    7 8 9
Все взвешивания будем производить таким образом: разбиваем шары на 3 группы по 3 шара в каждом, на одну чашку весов кладём первую группу, на другую — вторую, а третью группу оставляем.
Одно взвешивание определяет, в какой группе лёгкий шар: если весы в равновесии, то в третьей, иначе — в легчайшей.
Если сначала взвесить шары по строкам таблицы: (1, 2, 3), (4, 5, 6), (7, 8, 9), а затем по столбцам: (1, 4, 7), (2, 5, 8), (3, 6, 9), то видим, что эта пара взвешиваний даст нам строку и столбец, в котором находится лёгкий шар, т.е. однозначно его определит.

II) Проанализируем, что дало нам такой замечательный результат. Его дало нам то свойство, что каждая группа первого взвешивания пересекается с каждой группой второго взвешивания ровно по одному шару. Назовём это свойство "ортогональностью" пары взвешиваний.
Вспоминая, как считается определитель матрицы 3x3, мы можем легко представить ещё одну ортогональную пару взвешиваний:
(1, 5, 9), (2, 6, 7), (3, 4, 8)
и
(1, 6, 8), (2, 4, 9), (3, 5, 7).
Оказывается, они ортогональны не только друг другу. Все четыре выписанных взвешивания попарно ортогональны, а значит, любая пара из этих четырёх позволит нам определить лёгкий шар при условии, что весы не врут.

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

IV) Теперь рассмотрим исходную задачу с четырьмя выписанными взвешиваниями. Будем удалять из этой четвёрки по одному взвешиванию и анализировать оставшиеся три. Если мы удалили неправильное взвешивание, то осталось три правильных, и какую бы пару из них мы ни взяли, получится один и тот же шар, и этот шар действительно будет легчайшим. Если же мы удалили правильное взвешивание, то у нас остаётся одно неправильное взвешивание и два правильных. Проанализируем попарно все три взвешивания. Пара правильных взвешиваний даст нам правильный шар в то время как любая другая пара (неправильное+правильное) обязательно даст другой шар (см. п. III). По этой несогласованности мы и определим, что данная тройка взвешиваний содержит неправильное. Единственная согласованная тройка даст нам правильный ответ.

 Профиль  
                  
 
 Re: Взвешивания
Сообщение22.10.2014, 10:47 
Заслуженный участник
Аватара пользователя


18/12/10
1600
spb
worm2
Очень симпатично, а у меня возня на последних этапах

 Профиль  
                  
 
 Re: Взвешивания
Сообщение26.10.2014, 19:45 


05/08/08
55
Санкт-Петербург
Worm2, поздравляю, Вы повторили авторское решение.

Источник олимпиады - заочный тур олимпиады ЮМШ, 2014. Автор - ВПС

 Профиль  
                  
 
 Re: Взвешивания
Сообщение31.10.2014, 07:31 


31/10/14
1
There are nine balls 8 are identical in weight and one - easier. Is it possible to beam balance for weighing 4 to determine the ball, which is easier if you know that the scales only once show an incorrect result






_____
hanif

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group