Задача для Xenia 1996 и не только

Ludina · Сообщение **Ludina** » 02 апр 2011, 19:27

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

12d3 · Сообщение **12d3** » 02 апр 2011, 20:17

Я гарантирую, что сначала нужно проверять 5 шаров.

Equinoxe · Сообщение **Equinoxe** » 03 апр 2011, 00:47

12d3 писал(а):Source of the post
Я гарантирую, что сначала нужно проверять 5 шаров.

12d3
Умею доказывать невозможность для случаев 1..4 и 11..15 (уже приводила) и 8..10 (a там нужно рассмотреть мин. кол-во проверок для 9-ти, т.к. кол-во вариантов событий для 5-ти действий $$2^5=32$$

, a кол-во возможных ответов $$= 9*4 = 36$$

, для 9-ти необходимо минимум 6 проверок), но для 6..7 — нет. Подскажите, a то мне кажется, что для 6-ти решение вполне себе существует.

Таланов

Equinoxe писал(а):Source of the post
Подскажите, a то мне кажется, что для 6-ти решение вполне себе существует.

Померили 6 шаров - запищало, осталось 6 измерений. Что делать будете?

vicvolf · Сообщение **vicvolf** » 03 апр 2011, 14:59

12d3 писал(а):Source of the post
Я гарантирую, что сначала нужно проверять 5 шаров.

Давайте решение

Ludina писал(а):Source of the post
Виктор B, для того, чтобы на первом шаге обнаружить что в каждой группе есть радиоактивный шар нужно затратить 2 измерения. Следовательно, для нахождения каждого шара не хватает измерений.

Согласен

Таланов

vicvolf писал(а):Source of the post
12d3 писал(а):Source of the post
Я гарантирую, что сначала нужно проверять 5 шаров.

Давайте решение

Да вы и сами к этому придёте.

Equinoxe · Сообщение **Equinoxe** » 03 апр 2011, 16:16

Таланов писал(а):Source of the post
vicvolf писал(а):Source of the post
Давайте решение

Да вы и сами к этому придёте.

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

T.к. если мы проверяем t элементов первого вместе c k элементов второго, то чтобы определить хоть что-нибудь про какое-то конкретное из них, нам нужно ещё хотя бы одно измерение. За те же два измерения можно проверить раздельно t элементов первого и k элементов второго.

Если это верно, то рассмотрим случай для 7:
Если первые 7 радиоактивны, то либо в первых 7-ми содержатся оба шарика, либо в других 8-ми есть второй. Чтобы это узнать, нам так и так придется проверить последние 8, если они радиоактивны, нам придется сделать ещё минимум 3 действия для нахождения первого и столько же для второго (это следует из мин. кол-ва действий для нахождения одного шарика). Ho $$2+3*2$$

больше 7-ми.
Абсолютно аналогично всё для 6-ти, т.к. если среди первых 7-ми есть оба шарика, то первые 6 точно будут радиоактивны.

Звучит довольно сомнительно, но других док-в для 6-ти и 7-ми у меня нет.

Drigota · Сообщение **Drigota** » 04 апр 2011, 06:36

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

Ludina · Сообщение **Ludina** » 04 апр 2011, 06:45

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

Пусть, например, радиоактивны шары c "координатами" (2;4) (3;5). После такой серии измерений можно будет только утверждать, что радиоактивны либо эти шары, либо шары (2;5) (3;4)

Drigota · Сообщение **Drigota** » 04 апр 2011, 08:58

Ваша ситуация возникла после пятого измерения. B этом случае шестым измерением проверю диагональ (2;4), (3;5).

yourdomain.com