Ага. ЕГЭ. Угу.
Jun. 2nd, 2013 01:24 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
phd_ruМой сын закончил школу и сдаёт ЕГЭ. В промежутке готовится. И вот в школе ему дали ссылку на сайт с тестовыми заданиями: http://alexlarin.net/ege/2013/trvar33.html
До чего интересные задачи там бывают! А уж решения!…
C6. Геологи взяли в экспедицию 80 банок консервов, веса которых все известны и различны (имеется список). Через некоторое время надписи на банках стали нечитаемыми, и только завхоз знает, где что. Он может всем это доказать (т. е. обосновать, что в какой банке находится), не вскрывая консервов и пользуясь только сохранившимся списком и двухчашечными весами со стрелкой, показывающей разницу весов на чашках. Докажите, что ему для этой цели
— а) достаточно четырех взвешиваний;
— б) недостаточно трех взвешиваний.
Комментарий. Отметим еще раз, что завхоз должен обосновать, что в какой банке находится для всех 80 банок.
Решение
а) Нам будет удобнее работать с количеством банок, делящимся на 3. Поэтому введем еще одну "фиктивную" банку с нулевым весом.
Пусть, сначала, завхоз положит 27 самых легких банок на левую чашу, а 27 самых тяжелых — на правую. Этим он убедит всех геологов, что на левой чаше действительно 27 самых легких, а на правой — 27 самых тяжелых. Все банки разделились на 3 кучки по 27 банок, и про каждую из этих кучек геологи верят, что там действительно банки из этой кучки.
Теперь завхоз положит 9 самых легких банок из каждой из трех кучек на левую чашу, а 9 самых тяжелых — на правую. При этом геологи видят действия завхоза, а он не смешивает банки из разных кучек.
Теперь все банки разделились на 9 кучек по 9 банок, и геологи знают, какие банки в какой кучке. Завхоз положит по 3 самых легких банки из каждой кучки на левую чашу и по 3 самых тяжелых — на правую. Банки разделятся на 27 кучек, и геологи верят в распределение банок по кучкам. Остается взять по самой легкой банке в каждой кучке и положить на левую чашу, а самые тяжелые банки в кучках положить на правую.
б) Каждым взвешиванием банки делятся на три группы — банки на левой чаше, банки на правой чаше и банки, не участвующие во взвешивании. Самое большее, что могут узнать геологи в результате одного взвешивания, — это определить, какой набор банок лежит в каждой группе.
После первого взвешивания в одной из групп будет не меньше трети всех банок, т. е. не меньше 27 (принцип Дирихле); при этом для геологов (кроме завхоза) они будут неразличимы. При втором взвешивании эта группа также разделится на 3 группы, в одной из которых будет не меньше 9 банок, неразличимых для геологов. При третьем взвешивании из этих 9 банок в одну из новых групп попадут не меньше трех банок. Поэтому трех взвешиваний недостаточно.
До чего интересные задачи там бывают! А уж решения!…
C6. Геологи взяли в экспедицию 80 банок консервов, веса которых все известны и различны (имеется список). Через некоторое время надписи на банках стали нечитаемыми, и только завхоз знает, где что. Он может всем это доказать (т. е. обосновать, что в какой банке находится), не вскрывая консервов и пользуясь только сохранившимся списком и двухчашечными весами со стрелкой, показывающей разницу весов на чашках. Докажите, что ему для этой цели
— а) достаточно четырех взвешиваний;
— б) недостаточно трех взвешиваний.
Комментарий. Отметим еще раз, что завхоз должен обосновать, что в какой банке находится для всех 80 банок.
Решение
а) Нам будет удобнее работать с количеством банок, делящимся на 3. Поэтому введем еще одну "фиктивную" банку с нулевым весом.
Пусть, сначала, завхоз положит 27 самых легких банок на левую чашу, а 27 самых тяжелых — на правую. Этим он убедит всех геологов, что на левой чаше действительно 27 самых легких, а на правой — 27 самых тяжелых. Все банки разделились на 3 кучки по 27 банок, и про каждую из этих кучек геологи верят, что там действительно банки из этой кучки.
Теперь завхоз положит 9 самых легких банок из каждой из трех кучек на левую чашу, а 9 самых тяжелых — на правую. При этом геологи видят действия завхоза, а он не смешивает банки из разных кучек.
Теперь все банки разделились на 9 кучек по 9 банок, и геологи знают, какие банки в какой кучке. Завхоз положит по 3 самых легких банки из каждой кучки на левую чашу и по 3 самых тяжелых — на правую. Банки разделятся на 27 кучек, и геологи верят в распределение банок по кучкам. Остается взять по самой легкой банке в каждой кучке и положить на левую чашу, а самые тяжелые банки в кучках положить на правую.
б) Каждым взвешиванием банки делятся на три группы — банки на левой чаше, банки на правой чаше и банки, не участвующие во взвешивании. Самое большее, что могут узнать геологи в результате одного взвешивания, — это определить, какой набор банок лежит в каждой группе.
После первого взвешивания в одной из групп будет не меньше трети всех банок, т. е. не меньше 27 (принцип Дирихле); при этом для геологов (кроме завхоза) они будут неразличимы. При втором взвешивании эта группа также разделится на 3 группы, в одной из которых будет не меньше 9 банок, неразличимых для геологов. При третьем взвешивании из этих 9 банок в одну из новых групп попадут не меньше трех банок. Поэтому трех взвешиваний недостаточно.
