..и с учетом подсказок, вероятно, решение такое — повычеркивать все цифры кроме 4 и 5, используя знак / для зачеркивания

Здравствуйте Serge, Вы писали:

S>Здравствуйте fAX, Вы писали:

fAX>>Тут — продолжение чересчур длинной темы.

S>Вот еще одна жутко простая задачка (приведена в учебнике по математике для 6-го класса), однако большинство народу с первого раза дает неправильный ответ...

S>Есть комунальная квартира. В ней живут 3 хозяйки, которые решают приготовить обед. Поскольку газовой плиты в квартире нет, обед готовиться в печи на дровах. Обед они готвят вместе, на одном огне, одинаково долго и т.д., т.е. каждая из них тратит одинаковое количество ресурсов. Первая хозяйка принесла 3 полена, вторая — 5 поленьев, у третьей хозяйки поленьев не оказалось и она принесла 8 рублей (коммунистические цены) и отдала их первым двум.
S>Вопрос: как должны поделить между собой эти деньги первые две хозяйки?

1 и 7

( 3 — 8 / 3 ) = 1 / 3 (от первой)
( 5 — 8 / 3 ) = 7 / 3 (от второй)

Здравствуйте fAX, Вы писали:

fAX>Тут — продолжение чересчур длинной темы.

Имеется последовательность x_1, ..., x_n.
Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

Задача:
По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

Еще одна бородатая задачка.

Какой следующий член последовательности:
11, 21, 1112, ...

Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.

Здравствуйте fAX, Вы писали:

fAX>Тут — продолжение чересчур длинной темы.

А задачи с толстыми подвохами принимаются? Если да, то у меня есть одна.

Дан ряд цифр 0123456789. Нужно используя только знаки деления получить из этого 45.
(с) Мой гениальный папа.

Ниже идут подсказки. Без них врядли что-то получится.
.
.
.
.
.
.
.
.
1. Это задачка для тех, кто не умеет считать.
.
.
.
.
.
.
.
.
.
2. Знак деления — '/', а не ':'.

Здравствуйте fAX, Вы писали:

fAX>Тут — продолжение чересчур длинной темы.

Вот еще одна жутко простая задачка (приведена в учебнике по математике для 6-го класса), однако большинство народу с первого раза дает неправильный ответ...

Есть комунальная квартира. В ней живут 3 хозяйки, которые решают приготовить обед. Поскольку газовой плиты в квартире нет, обед готовиться в печи на дровах. Обед они готвят вместе, на одном огне, одинаково долго и т.д., т.е. каждая из них тратит одинаковое количество ресурсов. Первая хозяйка принесла 3 полена, вторая — 5 поленьев, у третьей хозяйки поленьев не оказалось и она принесла 8 рублей (коммунистические цены) и отдала их первым двум.
Вопрос: как должны поделить между собой эти деньги первые две хозяйки?

Тут — продолжение чересчур длинной темы.

1. Есть 27 шариков.
2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

Удачи.

Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

Удачи.

Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.

Нехорошо...

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

Условие неполное. Какого типа весы мы используем? Чашечные? Пружинные?

В классической постановке эта задача ставится с чашечными весами, которые могут назодиться в одном из трех состояний — левая чашка перевешивает, правая чашка перевешивает, равновесие.

Решение давать не буду.

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте fAX, Вы писали:

fAX>>1. Есть 27 шариков.
fAX>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

АТ>Условие неполное. Какого типа весы мы используем? Чашечные? Пружинные?

АТ>В классической постановке эта задача ставится с чашечными весами, которые могут назодиться в одном из трех состояний — левая чашка перевешивает, правая чашка перевешивает, равновесие.
Да, совершенно правильное уточнение, спасибо.
Решения давать тоже не буду

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

Предположим, что стратегия есть и мы придерживаемся такой схемы:

Проводим взвешивание. По его результатам определяем, что делать дальше.
Тогда
количество_вариантов_после_взвешивания( 1 ) = #(<,>,=) = 3 // больше, меньше, равно
количество_вариантов_после_взвешивания( 2 ) = количество_вариантов_после_взвешивания(1) * #(<,>,=) = 9
количество_вариантов_после_взвешивания( 3 ) = количество_вариантов_после_взвешивания(2) * #(<,>,=) = 27

Пусть есть стратегия:
На первом шаге делим на кучки a, a, b.
a и а --- на весах. b откладываем.
Тогда после взвешивания мы узнаем, что
"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
1. Утверждается, что b <= 9
Пусть выпало =. Тогда шарик в кучке b
Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
2. Утверждается a + a <= 9
Пусть выпало > или <
Тогда шарик в куче a+a.
Если a+a > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = a + a > 9 ("неправильный" шарик может быть любым из этих кучек).

Тогда общее число шариков а + а + b <= 18. Противоречие.

P.S. Если знать тяжелей "неправильный" шарик или легче, то решение есть:
1. 9-весы-9 в стороне-9
2. 3-весы-3 в стороне-3
3. 1-весы-1 в стороне-1

Здравствуйте fAX, Вы писали:

fAX>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

fAX>Удачи.

ИМХО задачка на много проще чем если бы было 2 демона...
Так вопрос такой: Это нужная арка?
Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте fAX, Вы писали:

fAX>>1. Есть 27 шариков.
fAX>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>Удачи.

KA>Предположим, что стратегия есть и мы придерживаемся такой схемы:

KA>Проводим взвешивание. По его результатам определяем, что делать дальше.
KA>Тогда
KA>количество_вариантов_после_взвешивания( 1 ) = #(<,>,=) = 3 // больше, меньше, равно
KA>количество_вариантов_после_взвешивания( 2 ) = количество_вариантов_после_взвешивания(1) * #(<,>,=) = 9
KA>количество_вариантов_после_взвешивания( 3 ) = количество_вариантов_после_взвешивания(2) * #(<,>,=) = 27

KA>Пусть есть стратегия:
KA>На первом шаге делим на кучки a, a, b.
KA>a и а --- на весах. b откладываем.
KA>Тогда после взвешивания мы узнаем, что
KA>"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
KA>1. Утверждается, что b <= 9
KA>Пусть выпало =. Тогда шарик в кучке b
KA>Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
KA>2. Утверждается a + a <= 9
KA>Пусть выпало > или <
KA>Тогда шарик в куче a+a.
KA>Если a+a > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = a + a > 9 ("неправильный" шарик может быть любым из этих кучек).

KA>Тогда общее число шариков а + а + b <= 18. Противоречие.

KA>P.S. Если знать тяжелей "неправильный" шарик или легче, то решение есть:
KA>1. 9-весы-9 в стороне-9
KA>2. 3-весы-3 в стороне-3
KA>3. 1-весы-1 в стороне-1

Лет 8 назад я решал (и решил) эту задачку на одной олимпиаде. Так что решение — есть. Просто оно не столь тривиально и не лежит на поверхности.

А что понимается под взвешиванием?
Какие действия могут быть допустимы ещё?

А что понимается под взвешиванием?
Какие действия могут быть допустимы ещё?

Здравствуйте Аноним, Вы писали:

А>А что понимается под взвешиванием?
Взвешивание на "чашечных" весах.

А>Какие действия могут быть допустимы ещё?
Никаких. Можно, конечно, со злостью выкинуть шарик, если это поможет решению

Ответ на задачу про 27 шариков настолько тривиален, что ...(главное понять почему 27 шариков)
Кстати, в своё время эта задача долго кочевала по городским, обласным, республиканским ... математическим олимпиадам.

Эта задача парализовала работу лучших умов отдела.
Срочно нужен ответ — иначе не видать преимии ...

Здравствуйте Nikto, Вы писали:

N>Здравствуйте fAX, Вы писали:

fAX>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

fAX>>Удачи.

N>ИМХО задачка на много проще чем если бы было 2 демона...
N>Так вопрос такой: Это нужная арка?
N>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ

Пояснение: Задаётся один вопрос произвольному демону.

Здравствуйте fAX, Вы писали:

fAX>Лет 8 назад я решал (и решил) эту задачку на одной олимпиаде. Так что решение — есть. Просто оно не столь тривиально и не лежит на поверхности.

Встречное предложение --- найти ошибку в рассуждении.

Здравствуйте Аноним, Вы писали:

А>Эта задача парализовала работу лучших умов отдела.
А>Срочно нужен ответ — иначе не видать преимии ...
У всех конец месяца... Что же касается решения, то какие ж это "лучшие умы" ?! (шютка). Совет — решите для 9-и, а потом чуть подумайте. Или запаситесь терпением — недолго осталось, я думаю...

Здравствуйте KonstantinA, Вы писали:

KA>Предположим, что стратегия есть и мы придерживаемся такой схемы:

KA>Проводим взвешивание. По его результатам определяем, что делать дальше.
KA>Тогда
KA>количество_вариантов_после_взвешивания( 1 ) = #(<,>,=) = 3 // больше, меньше, равно
KA>количество_вариантов_после_взвешивания( 2 ) = количество_вариантов_после_взвешивания(1) * #(<,>,=) = 9
KA>количество_вариантов_после_взвешивания( 3 ) = количество_вариантов_после_взвешивания(2) * #(<,>,=) = 27

KA>Пусть есть стратегия:
KA>На первом шаге делим на кучки a, a, b.
KA>a и а --- на весах. b откладываем.
KA>Тогда после взвешивания мы узнаем, что
KA>"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
KA>1. Утверждается, что b <= 9
KA>Пусть выпало =. Тогда шарик в кучке b
KA>Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
KA>2. Утверждается a + a <= 9
Это неверно.

KA>Пусть выпало > или <
KA>Тогда шарик в куче a+a.
KA>Если a+a > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = a + a > 9 ("неправильный" шарик может быть любым из этих кучек).

KA>Тогда общее число шариков а + а + b <= 18. Противоречие.

KA>P.S. Если знать тяжелей "неправильный" шарик или легче, то решение есть:
KA>1. 9-весы-9 в стороне-9
KA>2. 3-весы-3 в стороне-3
KA>3. 1-весы-1 в стороне-1

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

KA>>Предположим, что стратегия есть и мы придерживаемся такой схемы:

KA>>Проводим взвешивание. По его результатам определяем, что делать дальше.
KA>>Тогда
KA>>количество_вариантов_после_взвешивания( 1 ) = #(<,>,=) = 3 // больше, меньше, равно
KA>>количество_вариантов_после_взвешивания( 2 ) = количество_вариантов_после_взвешивания(1) * #(<,>,=) = 9
KA>>количество_вариантов_после_взвешивания( 3 ) = количество_вариантов_после_взвешивания(2) * #(<,>,=) = 27

KA>>Пусть есть стратегия:
KA>>На первом шаге делим на кучки a, a, b.
KA>>a и а --- на весах. b откладываем.
KA>>Тогда после взвешивания мы узнаем, что
KA>>"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
KA>>1. Утверждается, что b <= 9
KA>>Пусть выпало =. Тогда шарик в кучке b
KA>>Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
KA>>2. Утверждается a + a <= 9
fAX>Это неверно.

Да? А почему?
Шарик может быть любым из a+a, а комбинаций <<, <=, <>, ><, >=, >>, =<, ==, => всего 9.

Здравствуйте KonstantinA, Вы писали:


KA>>>Пусть есть стратегия:
KA>>>На первом шаге делим на кучки a, a, b.
KA>>>a и а --- на весах. b откладываем.
KA>>>Тогда после взвешивания мы узнаем, что
KA>>>"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
KA>>>1. Утверждается, что b <= 9
KA>>>Пусть выпало =. Тогда шарик в кучке b
KA>>>Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
KA>>>2. Утверждается a + a <= 9
fAX>>Это неверно.

KA>Да? А почему?
KA>Шарик может быть любым из a+a, а комбинаций <<, <=, <>, ><, >=, >>, =<, ==, => всего 9.
В своих рассуждениях Вы отказываетесь от дополнительной информации, получаемой в результате первого взвешивания. При таких ограничениях это действительно невозможно. В оригинальных же условиях их нет.

Удачи.
Этой подсказки должно хватить...

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте fAX, Вы писали:

fAX>>Здравствуйте KonstantinA, Вы писали:

KA>>>Предположим, что стратегия есть и мы придерживаемся такой схемы:

KA>>>Проводим взвешивание. По его результатам определяем, что делать дальше.
KA>>>Тогда
KA>>>количество_вариантов_после_взвешивания( 1 ) = #(<,>,=) = 3 // больше, меньше, равно
KA>>>количество_вариантов_после_взвешивания( 2 ) = количество_вариантов_после_взвешивания(1) * #(<,>,=) = 9
KA>>>количество_вариантов_после_взвешивания( 3 ) = количество_вариантов_после_взвешивания(2) * #(<,>,=) = 27

KA>>>Пусть есть стратегия:
KA>>>На первом шаге делим на кучки a, a, b.
KA>>>a и а --- на весах. b откладываем.
KA>>>Тогда после взвешивания мы узнаем, что
KA>>>"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
KA>>>1. Утверждается, что b <= 9
KA>>>Пусть выпало =. Тогда шарик в кучке b
KA>>>Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
KA>>>2. Утверждается a + a <= 9
fAX>>Это неверно.

KA>Да? А почему?
KA>Шарик может быть любым из a+a, а комбинаций <<, <=, <>, ><, >=, >>, =<, ==, => всего 9.

Потому что опять надо на три кучки делить и учитывать не только количество комбинаций показаний весов, но и какие кучки на весы попали. Так как кучек два типа — с дефекным шариком или без него, то комбинаций 18.

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

По-моему, 27 — это ты загнул. Я попытаюсь продолжить начинание KonstantinA и доказать, что это невозможно.

Мы разделили все шарики на три кучки взвешиваем две из них и (о чудо) они одинаковые, значит фальшивый шарик в третьей, назовём её куча_2.

Теперь проделываем тоже самое с кучей_2, и опять весы уравновесились, фальшивый шарик в куче_3.

Итак, у нас куча_3 в ней X шариков, которые мы ни разу не взвешивали, одно взвешивание и куча шариков, про которые известно, что они нормальные.

Попытаемся оценить максимальное Х, которое нам подходит. Поскольку всё шарики в куче_3 одинаковы, для определения нужного за одно взвешивания нужно разделить их по одному (взвешивать в одной чашке два шарика не имеет смысла). Т.к. у нас всего три таких места (две чашки и место вне весов), то Х не более чем 3 (у меня не вышло даже с 3-мя, но предположим за вас играет интуиция).

Теперь предположим, что предпоследнее взвешивание закончилось не так удачно. Т.е. у нас есть две кучки по У шариков, которые мы взвешивали один раз, одна "легкая", другая "тяжёлая", одно взвешивание и куча нормальных шариков.

Попытаемся оценить У. Здесь ситуация аналогична предидущей. Складывать в одну чашку два подозрительных шарика не имеет сысла (не совсем так, но в данном случае это не спасает), т.к. будет непонятно, какой из них фальшивый. Складывать два подозрительных шарика рядом с весами тем более не имеет смысла. Итого, Y должно быть 1,5. Но, так и быть, с учётом интуиции, пусть Y 2.

Итак, в куче_2 должно быть не более 7-ми шариков, иначе нам не хватит на неё двух взвешиваний. Значит за первое взвешивание мы должны отбросить 20 шариков => в кучках, которые мы с начала кладём на весы их по 10.

А теперь предположим, что одна из кучек в 10 шариков перевесила. И пусть интуиция подсказывает вам, что фальшивый шарик тяжелее, т.е. "легкую" кучку вы с чистой совестью можете выбросить. Итак, вы имеете два взвешивания, десять шариков, информацию о том, что фальшивый тяжелее и ни одного шанса решить задачу.

А если интуиция вам не поможет, всё закончится ещё печальнее...

Единственная возможность — не делить на кучки, а использовать принципиально другой подход. Какой?

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте Nikto, Вы писали:

N>>Здравствуйте fAX, Вы писали:

fAX>>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

fAX>>>Удачи.

N>>ИМХО задачка на много проще чем если бы было 2 демона...
N>>Так вопрос такой: Это нужная арка?
N>>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ

fAX>Пояснение: Задаётся один вопрос произвольному демону.

Понятно. Тогда она решается так же как если бы демона было два...

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте Аноним, Вы писали:

А>>А что понимается под взвешиванием?
fAX>Взвешивание на "чашечных" весах.

Я не очень сильно разбираюсь в весах, поэтому, может быть, мой вопрос не к месту. Но все-таки.
Знаю два типа весов с двумя "чашами". Один тип просто показывает, груз на какой из чаш тяжелее. А второй (тот, который в магазинах стоит, например) показывает еще и разницу в весе.
Какой тип используется (т.е. знаем ли мы разницу в весе?)

Здравствуйте KonstantinA, Вы писали:

KA>Имеется последовательность x_1, ..., x_n.
KA>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

KA>Задача:
KA>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

Легко. Хотя и не очень понятно, что такое просто монотонной. Я решил это понимать, как невозрастающую или неубывающую.

Работающий пример

Код: (ногами не пинать =))

<?
if (!isset($chain)){
  ?>
  <form action=chain.php method=post>
  Введите последовательность:<br>
  <input type=text size=50 name=chain> <br><br>
  <input type=submit value=Отправить>
  </form>
  <?
  exit;
}

if(ereg("[^0-9]",$chain)) {
  print "введена неверная (нечисловая) последовательность <a href=chain.php>попробовать еще раз</a>";
  exit;
}

print "Введена последовательность <i>$chain</i><br><br>";
$subch = array();
// 0 - невозрастающая
// 1 - неубывающая
for ($i=0;$i<strlen($chain);$i++){
  $dig = $chain{$i};
  $subch[] = array($dig,$dig);
  for ($j=0;$j<(count($subch)-1);$j++){
    $asc  = $subch[$j][1]; // неубывающая
    $desc = $subch[$j][0]; // невозрастающая
    if ($asc{strlen($asc)-1} <= $dig)   $subch[$j][1] .= $dig;
    if ($desc{strlen($desc)-1} >= $dig) $subch[$j][0] .= $dig;
  }
}

$max = 0;
for ($i=0;$i<count($subch);$i++){
 $max = (strlen($subch[$i][0])>$max)?strlen($subch[$i][0]):$max;
 $max = (strlen($subch[$i][1])>$max)?strlen($subch[$i][1]):$max;
}

print "Максимальная длина подпоследовательности <b>$max</b>";
print "<br>Такую длину имеют следующие подпоследовательности:<br><br>";

for ($i=0;$i<count($subch);$i++){
 if (strlen($subch[$i][0]) == $max) print "Невозрастающая: <i>".$subch[$i][0]."</i><br>"; 
 if (strlen($subch[$i][1]) == $max) print "Неубывающая: <i>".$subch[$i][1]."</i><br>"; 
}

print "<br><a href=chain.php>попробовать еще раз</a>";

?>

Добавьте php подсветку!!!!!!!!!!!!

R>Легко. Хотя и не очень понятно, что такое просто монотонной. Я решил это понимать, как невозрастающую или неубывающую.

Виноват, ошибся. Продолжаю думать.

Здравствуйте Rumata, Вы писали:

R>Здравствуйте KonstantinA, Вы писали:

KA>>Имеется последовательность x_1, ..., x_n.
KA>>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

KA>>Задача:
KA>>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

R>Легко. Хотя и не очень понятно, что такое просто монотонной. Я решил это понимать, как невозрастающую или неубывающую.

Монотонная это либо убывающая, либо возрастающая. Но это неважно. Если надется решение для возрастающих, то остальное просто...

Здравствуйте Linuxoid, Вы писали:

L>..и с учетом подсказок, вероятно, решение такое — повычеркивать все цифры кроме 4 и 5, используя знак / для зачеркивания

Правильно

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

Всё очень просто, надо только немного подумать.
I. делим на три кучки по 9 шаров, взвешиваем 2 кучи, если есть равновесие, то выкидываем обе если нет, то оставляем более тяжёлую, а остальные две выкидываем (осталось 9 шаров)
II. делим на три кучи по 3 шара, проводим ту же манипуляцию что и при I осталось 3 шара.
III. Взвешиваем 2 шара ........

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

Пронумеруем шарики от 1 до 27.
Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1.
Определение Алгоритм --- следующая последовательность действий
(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( l_1, ..., l_a ), где все k_i, l_j попарно различны и лежат в интервале [1,27].
(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( l_1, ..., l_a ), смотрим результат взвешивания
(шаг 2).
a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( l_1, ..., l_a ). Идем на (шаг 1).
a) Если шаг 1 выполнялся 3 раза, то выход.

Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2).
Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2).
Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)

Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27
Доказательство
Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.

Обозначение (n,*) = (n,+) + (n,-)
Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число
--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1)
--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2)
Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.

Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто.
Доказательство
k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)

Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это
либо {(n,+), если n из A1},
либо {(n,-), если n из A1},
либо {(n,*), если n из A2}.
Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.

Скомбинируем теорему 1, теорему 2, теорему 3 и все

Здравствуйте YuriS, Вы писали:

YS>Здравствуйте fAX, Вы писали:

fAX>>1. Есть 27 шариков.
fAX>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>Удачи.

YS>Всё очень просто, надо только немного подумать.
YS>I. делим на три кучки по 9 шаров, взвешиваем 2 кучи, если есть равновесие, то выкидываем обе если нет, то оставляем более тяжёлую, а остальные две выкидываем (осталось 9 шаров)

А кто сказал, что неправильный шарик тяжелее?

YS>II. делим на три кучи по 3 шара, проводим ту же манипуляцию что и при I осталось 3 шара.
YS>III. Взвешиваем 2 шара ........

Решается простой рекурсией. (Если я опять не ошибся =))))

Решение. Исходник.

Здравствуйте Rumata, Вы писали:

R>Решается простой рекурсией. (Если я опять не ошибся =))))

R>Решение. Исходник.

R> :user:

Возможно работает все правильно, но это далеко не оптимально.
Уточню задачу:
найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!

P.S. А вообще спасибо за ответ...

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте Rumata, Вы писали:

R>>Решается простой рекурсией. (Если я опять не ошибся =))))

R>>Решение. Исходник.

R>> :user:

KA>Возможно работает все правильно, но это далеко не оптимально.
KA>Уточню задачу:
KA>найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!

Да кстати совсем не обязательно находить эту последовательность...

Здравствуйте KonstantinA, Вы писали:

fAX>>1. Есть 27 шариков.
fAX>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>Удачи.

[/i]День добрый. Мне серьёзно нравится Ваша настойчивость и аргументированнотсь (то, чего мне самому не хватает)[/i] :beer:

Теперь по теме. К сожалению ( :shuffle: ), явной ошибки я пока обнаружить не смог. У меня есть некоторые соображения, но об этом после. Вы не могли бы пояснить Теорему 2 (и, если можно, поменять индексы, а то "1" и "l" очень похожи, отчего плохо воспринимаются. Спасибо.

ЗЫ. Я всё же думаю, что знаю, что и где не так, но хочу дождаться Вашего ответа на этот пост.
ЗЗЫ. Я сейчас лихорадочно вспоминаю решение как самый сильный аргумент :)

fAX

KA>Пронумеруем шарики от 1 до 27.
KA>Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1.
KA>Определение Алгоритм --- следующая последовательность действий
KA>(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( l_1, ..., l_a ), где все k_i, l_j попарно различны и лежат в интервале [1,27].
KA>(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( l_1, ..., l_a ), смотрим результат взвешивания
KA>(шаг 2).
KA>a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( l_1, ..., l_a ). Идем на (шаг 1).
KA>a) Если шаг 1 выполнялся 3 раза, то выход.

KA>Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2).
KA>Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2).
KA>Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)

KA>Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27
KA>Доказательство
KA>Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.

KA>Обозначение (n,*) = (n,+) + (n,-)
KA>Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
KA>Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число
KA>--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1)
KA>--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2)
KA>Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.

KA>Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто.
KA>Доказательство
KA>k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)

KA>Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это
KA>либо {(n,+), если n из A1},
KA>либо {(n,-), если n из A1},
KA>либо {(n,*), если n из A2}.
KA>Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.

KA>Скомбинируем теорему 1, теорему 2, теорему 3 и все :shuffle:

Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

Здравствуйте Nikto, Вы писали:

N>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

На север, однако.

Здравствуйте Аноним, Вы писали:

А>Здравствуйте Nikto, Вы писали:

N>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

А>На север, однако.

А точнее?

Здравствуйте Nikto, Вы писали:

N>Здравствуйте Аноним, Вы писали:

А>>Здравствуйте Nikto, Вы писали:

N>>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

А>>На север, однако.

N>А точнее?

На северном магнитном полюсе, если идти по компасу.

Здравствуйте Boroda, Вы писали:

B>Здравствуйте Nikto, Вы писали:

N>>Здравствуйте Аноним, Вы писали:

А>>>Здравствуйте Nikto, Вы писали:

N>>>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

А>>>На север, однако.

N>>А точнее?

B>На северном магнитном полюсе, если идти по компасу.

А если не по компасу? Допустим ты знаешь в каждой точке куда нужно сделать шаг чтобы шагнуть на северо-восток...

З.Ы.: Про компас, кстати, ничего сказано не было...

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

fAX>>>1. Есть 27 шариков.
fAX>>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>>Удачи.

fAX>Теперь по теме. К сожалению ( :shuffle: ), явной ошибки я пока обнаружить не смог. У меня есть некоторые соображения, но об этом после. Вы не могли бы пояснить Теорему 2 (и, если можно, поменять индексы, а то "1" и "l" очень похожи, отчего плохо воспринимаются. Спасибо.

fAX>ЗЫ. Я всё же думаю, что знаю, что и где не так, но хочу дождаться Вашего ответа на этот пост.
fAX>ЗЗЫ. Я сейчас лихорадочно вспоминаю решение как самый сильный аргумент :)

fAX>fAX

KA>>Пронумеруем шарики от 1 до 27.
KA>>Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1.
KA>>Определение Алгоритм --- следующая последовательность действий
KA>>(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( p_1, ..., p_a ), где все k_i, p_j попарно различны и лежат в интервале [1,27].
KA>>(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( p_1, ..., p_a ), смотрим результат pвзвешивания
KA>>(шаг 2).
KA>>a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( p_1, ..., p_a ). Идем на (шаг 1).
KA>>a) Если шаг 1 выполнялся 3 раза, то выход.

KA>>Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2).
KA>>Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2).
KA>>Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)

KA>>Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27
KA>>Доказательство
KA>>Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.

KA>>Обозначение (n,*) = (n,+) + (n,-)
KA>>Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
KA>>Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число
KA>>--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1)
KA>>--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2)
KA>>Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.

KA>>Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто.
KA>>Доказательство
KA>>k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)
Пояснение
При фиксированном алгоритме у нас на первом шаге фиксированы a (k_1,...,k_a) и (p_1,...p_a). Рассмотрим конфигурацию (k_1,sign). Тогда A(k_1,sign)=(k_1,sign) или A(k_1,sign)=(k_1,*). Докажем, что второй вариант невозможен. Действительно для конфигураций (k_1,+) и (k_1,-) мы имеем разные результаты взвешивания на первом шаге, поэтому A(k_1,+) != A(k_1,-). Следовательно A(k_1,sign)=(k_1,sign).
То же верно в отношении k_2,..., k_a, p_1,..., p_a (выбранные на первом шаге).

KA>>Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это
KA>>либо {(n,+), если n из A1},
KA>>либо {(n,-), если n из A1},
KA>>либо {(n,*), если n из A2}.
KA>>Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.

KA>>Скомбинируем теорему 1, теорему 2, теорему 3 и все :shuffle:

Здравствуйте Nikto, Вы писали:


N>А если не по компасу? Допустим ты знаешь в каждой точке куда нужно сделать шаг чтобы шагнуть на северо-восток...

N>З.Ы.: Про компас, кстати, ничего сказано не было...

Тогда на северный полюс.(где ось земли)

З.Ы.
А как же без компаса на север-то ходить?
Заблудишься.

Здравствуйте Boroda, Вы писали:

B>Здравствуйте Nikto, Вы писали:


N>>А если не по компасу? Допустим ты знаешь в каждой точке куда нужно сделать шаг чтобы шагнуть на северо-восток...

N>>З.Ы.: Про компас, кстати, ничего сказано не было...

B>Тогда на северный полюс.(где ось земли)

Тогда правильно . Если б еще доказательство... Но мне оно не интересно .

B>З.Ы.
B>А как же без компаса на север-то ходить?
B>Заблудишься.

Таковы условия задачи, значит не заблудишься...

Здравствуйте fAX, Вы писали:

fAX>Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.

fAX>Нехорошо...

Насчет диска все довольно просто.
Имеется два возможных сочетания среди 4-х переключателей.
1). Два переключателя в одном положении, два в другом.
2). Три переключателя в одном положении, один в другом.
Алгоритм.
1. Переключить два выключателя, находящиеся напротив друг друга.
2. Переключить два выключателя, находящиеся рядом.
3. Переключить два выключателя, находящиеся напротив друг друга.
Очевидно, что проделав эти шаги мы однозначно добъемся того, чтоб загорелась лампочка если первоначальное состояние выключателей удовлетворяло условию (1).
А в случае, если первоначально состояние выключателей удовлетворяло условию (2), то после трех шагов, соотношение так и останется 3:1. Тогда прдолжаем.
4. Переключаем 3 выклюмателя.
Соотношение стало 2:2.
После чего повторяем 1,2,3 шаги.

PS. Если для того чтоб загорелась лампочка нужно не просто, чтоб все выключатели были в одинаковом положении, а именно в каком-то определенном, то после каждого шага алгоритма можно переключать 4-ре выключателя.

Здравствуйте fAX, Вы писали:

fAX>Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.

fAX>Нехорошо... :shuffle: :shuffle: :shuffle: :(

По поводу диска чем не нравиться cool site

Автор: KonstantinA
Дата: 09.08.02

Здравствуйте KonstantinA, Вы писали:

KA>>Возможно работает все правильно, но это далеко не оптимально.
KA>>Уточню задачу:
KA>>найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!

KA>Да кстати совсем не обязательно находить эту последовательность...

Думал, думал ...

Вот до чего додумался:
Как-то так изменяем данную последовательность, что длина самой длинной подпоследовательности не меняется — подойдет, анпример, любая монотонная функция, примененая к каждому члену последовательности.

А дальше ничего не придумал
Я хотя бы в правильном направлении мыслю?

Здравствуйте KonstantinA, Вы писали:

KA>Имеется последовательность x_1, ..., x_n.
KA>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

KA>Задача:
KA>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

Довольно простая задача на динамическое программирование.

Здравствуйте achp, Вы писали:

A>Довольно простая задача на динамическое программирование.
A>

По словам "динамическое программирование" ее решение ищется влет:
http://algolist.manual.ru/olimp/rec_sol.php#a20

Вот только я так и не понял, какой из вариантов решения имел в виду KonstantinA

Здравствуйте Rumata, Вы писали:

R>Здравствуйте KonstantinA, Вы писали:

KA>>>Возможно работает все правильно, но это далеко не оптимально.
KA>>>Уточню задачу:
KA>>>найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!

KA>>Да кстати совсем не обязательно находить эту последовательность...

R>Думал, думал ...

R>Вот до чего додумался:
R>Как-то так изменяем данную последовательность, что длина самой длинной подпоследовательности не меняется — подойдет, анпример, любая монотонная функция, примененая к каждому члену последовательности.

R>А дальше ничего не придумал :crash:
R>Я хотя бы в правильном направлении мыслю? :???:

Не знаю, что это может дать, но к известному мне решению это не имеет никакого отношения... :(

Здравствуйте Nikto, Вы писали:

N>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

На мой вгляд — на Сверней полюс(или бесконечно близко к нему).
Sam from Il.

Здравствуйте achp, Вы писали:

A>Здравствуйте KonstantinA, Вы писали:

KA>>Имеется последовательность x_1, ..., x_n.
KA>>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

KA>>Задача:
KA>>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

A>Довольно простая задача на динамическое программирование.
A> :))

Я счастлив!!! :-\

Здравствуйте Rumata, Вы писали:

R>Здравствуйте achp, Вы писали:

A>>Довольно простая задача на динамическое программирование.
A>> :))

R>По словам "динамическое программирование" ее решение ищется влет:
R>http://algolist.manual.ru/olimp/rec_sol.php#a20

R>Вот только я так и не понял, какой из вариантов решения имел в виду KonstantinA

a)

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте fAX, Вы писали:

fAX>>Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.

fAX>>Нехорошо...

KA>По поводу диска чем не нравиться cool site

Автор: KonstantinA
Дата: 09.08.02

Sorry, примите мои извинения, не видел. Ощенка уже обновлена...

Здравствуйте KonstantinA, Вы писали:

KA>Я счастлив!!!

Что такое? Я не прав?

Здравствуйте KonstantinA, Вы писали:

Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

KA>Здравствуйте fAX, Вы писали:

fAX>>Здравствуйте KonstantinA, Вы писали:

fAX>>>>1. Есть 27 шариков.
fAX>>>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>>>Удачи.

fAX>>Теперь по теме. К сожалению ( ), явной ошибки я пока обнаружить не смог. У меня есть некоторые соображения, но об этом после. Вы не могли бы пояснить Теорему 2 (и, если можно, поменять индексы, а то "1" и "l" очень похожи, отчего плохо воспринимаются. Спасибо.

fAX>>ЗЫ. Я всё же думаю, что знаю, что и где не так, но хочу дождаться Вашего ответа на этот пост.
fAX>>ЗЗЫ. Я сейчас лихорадочно вспоминаю решение как самый сильный аргумент

fAX>>fAX

KA>>>Пронумеруем шарики от 1 до 27.
KA>>>Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1.
KA>>>Определение Алгоритм --- следующая последовательность действий
KA>>>(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( p_1, ..., p_a ), где все k_i, p_j попарно различны и лежат в интервале [1,27].
KA>>>(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( p_1, ..., p_a ), смотрим результат pвзвешивания
KA>>>(шаг 2).
KA>>>a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( p_1, ..., p_a ). Идем на (шаг 1).
KA>>>a) Если шаг 1 выполнялся 3 раза, то выход.

KA>>>Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2).
KA>>>Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2).
KA>>>Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)

KA>>>Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27
KA>>>Доказательство
KA>>>Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.

KA>>>Обозначение (n,*) = (n,+) + (n,-)
KA>>>Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
KA>>>Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число
KA>>>--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1)
KA>>>--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2)
KA>>>Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.

KA>>>Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто.
KA>>>Доказательство
KA>>>k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)
KA>Пояснение
KA>При фиксированном алгоритме у нас на первом шаге фиксированы a (k_1,...,k_a) и (p_1,...p_a). Рассмотрим конфигурацию (k_1,sign). Тогда A(k_1,sign)=(k_1,sign) или A(k_1,sign)=(k_1,*). Докажем, что второй вариант невозможен. Действительно для конфигураций (k_1,+) и (k_1,-) мы имеем разные результаты взвешивания на первом шаге, поэтому A(k_1,+) != A(k_1,-). Следовательно A(k_1,sign)=(k_1,sign).
KA>То же верно в отношении k_2,..., k_a, p_1,..., p_a (выбранные на первом шаге).

KA>>>Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это
KA>>>либо {(n,+), если n из A1},
KA>>>либо {(n,-), если n из A1},
KA>>>либо {(n,*), если n из A2}.
KA>>>Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.

KA>>>Скомбинируем теорему 1, теорему 2, теорему 3 и все

Здравствуйте Nikto, Вы писали:

N>Здравствуйте fAX, Вы писали:

fAX>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

fAX>>Удачи.

N>ИМХО задачка на много проще чем если бы было 2 демона...
N>Так вопрос такой: Это нужная арка?
N>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ
Вы задаёте вопрос произвольному демону!!! Т.е. в первом и третьем случае Вы можете на Ваш вопрос получить ответ и 1, и 0 , выражаясь Вашим языком.

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

fAX>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

Что еще за swap??? Это уже новое взвешивание!

Здравствуйте Rumata, Вы писали:

R>Здравствуйте fAX, Вы писали:

fAX>>Здравствуйте KonstantinA, Вы писали:

fAX>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

R>Что еще за swap??? Это уже новое взвешивание!
Нет, почему? Вы согласны, что если при первом взвешивании перевесила левая чаша, можно поменять левую и правую чаши и продолжить алгоритм как если бы изначально перевесила правая?..

Здравствуйте fAX, Вы писали:

fAX>Нет, почему? Вы согласны, что если при первом взвешивании перевесила левая чаша, можно поменять левую и правую чаши и продолжить алгоритм как если бы изначально перевесила правая?..

Ну да — это очевидно, я уж было испугался, что Вы собираетесь менять шарики на весах =)))

Здравствуйте achp, Вы писали:

A>Здравствуйте KonstantinA, Вы писали:

KA>>Я счастлив!!! :-\

A>Что такое? Я не прав?

Да нет прав, извини, если обидел. Просто жаль, что нашелся человек, который знает решение. Я в свое время поломал над этим голову...

Здравствуйте KonstantinA, Вы писали:

KA>Да нет прав, извини, если обидел. Просто жаль, что нашелся человек, который знает решение. Я в свое время поломал над этим голову...

Нет, не обидел, но там такая ухмылка... Подозрительная .

А вообще-то это не слишком занимательная задача. Честно-честно.

Здравствуйте achp, Вы писали:

A>А вообще-то это не слишком занимательная задача. Честно-честно.

А Вы не могли бы привести свое решение этой задачи? А еще "занимательную" задачу в придачу =)?

Здравствуйте fAX, Вы писали:

fAX>Нет, почему? Вы согласны, что если при первом взвешивании перевесила левая чаша, можно поменять левую и правую чаши и продолжить алгоритм как если бы изначально перевесила правая?..

Задача в данной формулировке имеет решение только для 13 монет. И даже для такого, казалось бы много меньшего колличества, решение намного сложнее, чем для 27 монет с условием, что известно легче фальшивка или тяжелее.
Забыл решение для 27 монет? Предложи хотя бы для 14-ти. :)

Здравствуйте WeCom, Вы писали:
Что мне нравится в Вашем ответе, так это слово "однозначно". . Я должен после этого сразу согласиться?!!

WC>Задача в данной формулировке имеет решение только для 13 монет.
Аргументы??? (Заранее, не стоит предлагать решение KonstantinA, но я больше не вижу, откуда взялась эта цифра). Знаете, предложите, пожалуйста, решение для тринадцати, потом мы с Вами подискутируем.

WC>И даже для такого, казалось бы много меньшего колличества, решение намного сложнее, чем для 27 монет с условием, что известно легче фальшивка или тяжелее.
Если известно то, что Вы сказали, задача просто тривиальна.

WC>Забыл решение для 27 монет? Предложи хотя бы для 14-ти.
А кто, пардон, сказал, что для всех чисел меньше 27 оно есть (я не уверен, что это так, хотя и возможно. Тут надо подумать)???

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

fAX>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! :) ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

Честно говоря не очень понял, что такое swap, но это не так важно (по крайней мере не совсем понимаю что это может изменить).

Пронумеруем шарики (можно считать, что на каждом написан его номер). Теперь после каждого взвешивания ведем журнал --- какие шарики клали на какую чашу весов, какой результат был получен (то есть шарики с какими номерами перевесили, или было равенство).

Что такое алгоритм... На первом шаге у нас заранее определены (независимо от конфигурации --- мы представления не имеем какая она) те номера, которые мы положим на весы. Пусть мы должны положить шарик с номером 5 + остальные.
Теперь выберем конфигурацию = 5 шарик неправильный. Тогда в конце алгоритм скажет, что 5-й шарик фальшивый. Посмотрим записи, где будет написано, что на 1-м шаге 5-й шарик участвовал во взвешивании и посмотрим на результат этого взвешивания. Мы сразу увидим, тяжелее он или легче. Поэтому для данного алгоритма 5-й шарик будет из A1...

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте WeCom, Вы писали:
fAX>Что мне нравится в Вашем ответе, так это слово "однозначно". :( . Я должен после этого сразу согласиться?!! :no:

Ok.
Доказывать, что 27 шариков — это максимум для которого существует решение, когда известно легче искомый или тяжелее (задача1) надо? Если надо, см ниже.

Итак, считаем 27 — это максимум для задачи1. Тогда, в твоей задаче если есть решение, то после двух взвешиваний должно остаться 3 шарика не побававших на весах ни разу. Если больше, то задача1 имела бы решение для более 27 шариков. Если меньше, то аналогично. Понимаешь, почему так?
Но в твоей задаче определить из трех шариков отличный за одно взвешивание вариантов нет, согласен? Поэтому твоя задача для 27 шариков решения ОДНОЗНАЧНО не имеет. Теперь можно спокойно соглашаться. :)

Осталось доказать, что в задаче1 27 шариков — это максимум для которого существует решение. Как бы мы ни раскладывали шарики на весы, как бы их не переворачивали, но каждое взвешивание позволяет отсеить не более 2/3 шариков (3 положения весов). Есть 3 взвешивания. Поэтому 27 это действительно максимум.

Вроде все доказательно.

WC>>Задача в данной формулировке имеет решение только для 13 монет.
fAX>Аргументы??? (Заранее, не стоит предлагать решение KonstantinA, но я больше не вижу, откуда взялась эта цифра). Знаете, предложите, пожалуйста, решение для тринадцати, потом мы с Вами подискутируем.

Я решал по другому, с перекладываниями и выбором шариков на основании предыдуших взвешиваний. А недавно в нете нашел вот какое решение:
Один шарик в сторону. Остальные именуем буквами и проводим три вот каких взвешивания:
MA DO — LIKE; ME TO — FIND; FAKE — COIN
После чего можем однозначно определить отличающийся шарик. Как? А вот это задание на дом. :))

Здравствуйте KonstantinA, Вы писали:

fAX>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

KA>Честно говоря не очень понял, что такое swap, но это не так важно (по крайней мере не совсем понимаю что это может изменить).

KA>Пронумеруем шарики (можно считать, что на каждом написан его номер). Теперь после каждого взвешивания ведем журнал --- какие шарики клали на какую чашу весов, какой результат был получен (то есть шарики с какими номерами перевесили, или было равенство).

KA>Что такое алгоритм... На первом шаге у нас заранее определены (независимо от конфигурации --- мы представления не имеем какая она) те номера, которые мы положим на весы. Пусть мы должны положить шарик с номером 5 + остальные.
KA>Теперь выберем конфигурацию = 5 шарик неправильный. Тогда в конце алгоритм скажет, что 5-й шарик фальшивый. Посмотрим записи, где будет написано, что на 1-м шаге 5-й шарик участвовал во взвешивании и посмотрим на результат этого взвешивания. Мы сразу увидим, тяжелее он или легче. Поэтому для данного алгоритма 5-й шарик будет из A1...

Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.

С уважением,
fAX

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

fAX>>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! :) ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

KA>>Честно говоря не очень понял, что такое swap, но это не так важно (по крайней мере не совсем понимаю что это может изменить).

KA>>Пронумеруем шарики (можно считать, что на каждом написан его номер). Теперь после каждого взвешивания ведем журнал --- какие шарики клали на какую чашу весов, какой результат был получен (то есть шарики с какими номерами перевесили, или было равенство).

KA>>Что такое алгоритм... На первом шаге у нас заранее определены (независимо от конфигурации --- мы представления не имеем какая она) те номера, которые мы положим на весы. Пусть мы должны положить шарик с номером 5 + остальные.
KA>>Теперь выберем конфигурацию = 5 шарик неправильный. Тогда в конце алгоритм скажет, что 5-й шарик фальшивый. Посмотрим записи, где будет написано, что на 1-м шаге 5-й шарик участвовал во взвешивании и посмотрим на результат этого взвешивания. Мы сразу увидим, тяжелее он или легче. Поэтому для данного алгоритма 5-й шарик будет из A1...

fAX>Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.

fAX>С уважением,
fAX>fAX

Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте fAX, Вы писали:

fAX>>Здравствуйте KonstantinA, Вы писали:

fAX>>>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

fAX>>Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.

KA>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...

Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...)
KA> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

KA>>Здравствуйте fAX, Вы писали:

fAX>>>Здравствуйте KonstantinA, Вы писали:

fAX>>>>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! :) ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

fAX>>>Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.

KA>>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...

fAX>Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...)
KA>> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).

Может это разъяснит ситуацию...

A(n,sign) --- те конфигурации, для которых будут те же взвешивания, что и для (n,sign). Так всегда (n,sign) лежит в A(n,sign)

А --- решающий алгоритм, если A(n,sign)=(n,sign) или (n,*).
Это определение говорит о том, что не может быть ситуации, что для разных неправильных шариков получены одинаковые результаты взвешиваний (иначе наш алгоритм ничего не находит).

Предположим, что A(n,sign)=(n,*). Что это значит, что для конфигураций (n,+) и (n,-) результаты взвешиваний в процессе работы алгоритма совпадут.
Предположим, что A(n,sign) = (n,sign). Тогда A(n,-sign)=(n,-sign) т.к. невозможно чтобы было A(n,-sign)=(n,*) --- это означает, что для (n,+) и (n,-) результаты взвешиваний совпадают. Но это не так в силу того, что A(n,sign)=(n,sign) != (n,*).

Почему, если шарик вешали на первом шаге, то он из A1?
Потому что для (n,+) и (n,-) будут разные результаты взвешивания на первом шаге => A(n,+) != A(n,-) => ничего не остается как A(n,+)=(n,+) и A(n,-)=(n,-)

Здравствуйте KonstantinA, Вы писали:

KA>>>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...

fAX>>Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...)
KA>>> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).

KA>Может это разъяснит ситуацию...

KA>A(n,sign) --- те конфигурации, для которых будут те же взвешивания, что и для (n,sign). Так всегда (n,sign) лежит в A(n,sign)
Если те же взвешивания — то мой "алгоритм" (с заменой) легитимен при первом взвешиваниих (а мне больше и не надо, чтобы опровергнуть вторую теорему в её текущем виде. Если же Вы сможете доказать её дальше, т.е. опираясь на второе или третье взвешивание (если, конечно, сможете), то придётся искать другие аргументы... Про самый веский я уже писал Но я Вам скажу, решить эту задачу легче, чем доказать, что она не решаема )

Да, возможно, ещё есть путаница. Под "A(n,sign)" Вы понимаете какие взвешивания производятся или результаты этих взвешиваний??? В любом случае, проблема (на мой взгляд) Вашего доказательства в симметрии задачи на первом взвешивании.

Спасибо за дискуссию .

KA>А --- решающий алгоритм, если A(n,sign)=(n,sign) или (n,*).
KA>Это определение говорит о том, что не может быть ситуации, что для разных неправильных шариков получены одинаковые результаты взвешиваний (иначе наш алгоритм ничего не находит).

KA>Предположим, что A(n,sign)=(n,*). Что это значит, что для конфигураций (n,+) и (n,-) результаты взвешиваний в процессе работы алгоритма совпадут.
KA>Предположим, что A(n,sign) = (n,sign). Тогда A(n,-sign)=(n,-sign) т.к. невозможно чтобы было A(n,-sign)=(n,*) --- это означает, что для (n,+) и (n,-) результаты взвешиваний совпадают. Но это не так в силу того, что A(n,sign)=(n,sign) != (n,*).

KA>Почему, если шарик вешали на первом шаге, то он из A1?
KA>Потому что для (n,+) и (n,-) будут разные результаты взвешивания на первом шаге => A(n,+) != A(n,-) => ничего не остается как A(n,+)=(n,+) и A(n,-)=(n,-)

Здравствуйте fAX, Вы писали:

fAX>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.

А как насчет моего, менее строгого и математического доказательства?

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте Nikto, Вы писали:

N>>Здравствуйте fAX, Вы писали:

fAX>>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

fAX>>>Удачи.

N>>ИМХО задачка на много проще чем если бы было 2 демона...
N>>Так вопрос такой: Это нужная арка?
N>>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ
fAX>Вы задаёте вопрос произвольному демону!!! Т.е. в первом и третьем случае Вы можете на Ваш вопрос получить ответ и 1, и 0 , выражаясь Вашим языком.

Да я понял. Я имел ввиду что знаю эту задачку и в принципе не важно сколько там демонов, решение для 2-х такое же как для 3-х. Вопрос примерно такой: "Если бы я тебя спросил правильные ли эти врата, чтобы ты ответил?"

Здравствуйте Аноним, Вы писали:

А>Здравствуйте Nikto, Вы писали:

N>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)

А> На мой вгляд — на Сверней полюс(или бесконечно близко к нему).
А> Sam from Il.

Правильно. Попробуйте доказать...

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте KonstantinA, Вы писали:

KA>>>>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...

fAX>>>Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...)
KA>>>> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).

KA>>Может это разъяснит ситуацию...

KA>>A(n,sign) --- те конфигурации, для которых будут те же взвешивания, что и для (n,sign). Так всегда (n,sign) лежит в A(n,sign)

fAX>Если те же взвешивания — то мой "алгоритм" (с заменой) легитимен при первом взвешиваниих (а мне больше и не надо, чтобы опровергнуть вторую теорему в её текущем виде. Если же Вы сможете доказать её дальше, т.е. опираясь на второе или третье взвешивание (если, конечно, сможете), то придётся искать другие аргументы... Про самый веский я уже писал :))) Но я Вам скажу, решить эту задачу легче, чем доказать, что она не решаема :))) )

Замена алгоритма ни при чем --- он фиксирован и все обсуждается только для него... Не понимаю при чем здесь какой-то другой алгоритм...

fAX>Да, возможно, ещё есть путаница. Под "A(n,sign)" Вы понимаете какие взвешивания производятся или результаты этих взвешиваний??? В любом случае, проблема (на мой взгляд) Вашего доказательства в симметрии задачи на первом взвешивании.

A(n,sign) --- конфигурации, дающие те же результаты взвешивания

fAX>Спасибо за дискуссию :) .

Аналогично

Здравствуйте fAX,
Почему то не вижу возражений на свое доказательство. Возможно, в некоторых местах, не все понятно, попробую уточнить.

Итак, считаем 27 — это максимум для задачи1. Предположим у тебя есть алгоритм решения твоей задачи. Тогда, при применении твоего алгоритма, после двух взвешиваний с результатом обоих взвешиваний "равно" должно остаться ровно 3 шарика не побававших на весах ни разу.
Потому что:
Если больше, то задача1 имела бы решение для более чем 27 шариков. Потому что, существовал бы вот такой алгоритм решения задачи1, начинаем с оригинального алгоритма для задачи1 и если на хотя бы одном из двухпервых взвешиваний результат "не равно", то этим алгоритмом и завершием решение на третьем шаге. Если же оба результата "равно", то для третьего взвешивания переходим к твоему алгоритму. итого 9+9+6+(больше 3-х) > 27.
Если меньше, то аналогично. Начинаем решение с твоего алгоритма. Если хотя бы одно из двух первых взвешиваний "не равно", то им же и завершаем решение задачи. Если же оба взвешивания "равно", то для третьего взвешивания переходим к оригинальному алгоритму решения задачи1. Т.е. решаем для оставшихся шариков (меньше трех) плюс дополнение до трех. Итого получаем (больше 24 (т.к. осталось<3)) + 3 > 27.

Но в твоей задаче определить из трех шариков отличный за одно взвешивание вариантов нет, согласен? Т.е. с одной стотоны в твоем алгоритме (если он есть и решает задачу) после двух взвешиваний с результатами "равно" должно остаться ровно 3 шарика, а с другой стороны за одно взвешивание из трех шариков неправильный найти невозможно. Из этого противоречия следует, что алгоритма решения твоей задачи НЕ СУЩЕСТВУЕТ.

WC>Осталось доказать, что в задаче1 27 шариков — это максимум для которого существует решение. Как бы мы ни раскладывали шарики на весы, как бы их не переворачивали, но каждое взвешивание позволяет отсеить не более 2/3 шариков (3 положения весов). Есть 3 взвешивания. Поэтому 27 это действительно максимум.

Пора представлять "алгоритм" :maniac:

Здравствуйте Все:

Слудует отметить, что задача поиска фальшивой монеты (неправильного шарика) из K монет за N взвешиваний на чашечных весах когда неизвестно легче фальшивая или тяжелее и среди всех K монет фальшивая только одна, может иметь решение только когда K <= (3^N-1)/2 + 1.
Обьяснение:
Ясно, что фальшивка однозначно определяется N показаниями весов, соответственно в 1-м, 2-м ... N-м взвешивании. Число всевозможных комбинаций для N взвешиваний — 3^N. Когда же неизвестно легче фальшивка или тяжелее, то 2 комбинации в которых каждый результат взвешивания заменен на противоположный, т.е. "слева легче" на "слева тяжелее", "слева тяжелее" на "слева легче", а "равны" остается без изменений должны указывать на одну и ту же монету. У нас один случай для которого нет пары — "равны", "равны", "равны". Поэтому пар у нас 3^N-1. Максимальное число монет, которое может определять это кол-во пар — (3^N-1)/2. И соответственно еще одна монета может определяться случаем с тремя равенствами. Поэтому и получаем K <= (3^N-1)/2 + 1.
Для N=3, K<=14. Для 13 решение известно. Уверен, для 14 решения нет. Но интересно, может быть есть решение для 14-ти, когда в условии задачи есть неограниченное колличество эталонных монет (в отдельной куче). Для N=2, например, K<=5. Для 5 без эталонов, решения нет, а с эталонами есть. Верно ли аналогичное для любого N. Т.е. то, что есть решение для K = (3^N-1)/2 + 1 при условии с эталонами? Как получить точное значение K для общего случая (любого N) и без эталонов?
---
Возможно можно доказать, что если есть хоть какой-то алгоритм решения — то есть и алгоритм, когда последующие взвешивания не зависят от предыдущих.

Здравствуйте AlexKu, Вы писали:

AK>Еще одна бородатая задачка.

AK>Какой следующий член последовательности:
AK>11, 21, 1112, ...

AK>Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.

Не этот ли?

122111

Здравствуйте AlexKu, Вы писали:

AK>Еще одна бородатая задачка.


Тоже старая (кто знает, молчать!).

Приходит мужик в скобяную лавку и видит некий предмет. Он спрашивает:

- Сколько будет стоить 1?
- 6 ,- отвечают.
- А сколько будет стоить 12?
- 12 ,- был ответ
- А сколько будет стоить 237?
- 18 ,- сказали ему

Вопрос - чего покупал мужик? Задача на логику.

Здравствуйте Flamer, Вы писали:
F>122111

Нет...

Пока без дополнительных подсказок

Здравствуйте AlexKu, Вы писали:

AK>Здравствуйте Flamer, Вы писали:
F>>122111

AK>Нет...

AK>Пока без дополнительных подсказок

А может, тогда

1122



Больше пока ничего в голову не приходит Надо подумать...

Здравствуйте Flamer, Вы писали:

F>А может, тогда
F>1122
F>Больше пока ничего в голову не приходит Надо подумать...

Нет, подумай пока =)

Здравствуйте Flamer, Вы писали:

F>Здравствуйте AlexKu, Вы писали:

AK>>Еще одна бородатая задачка.


F>Тоже старая (кто знает, молчать!).



F>

F>Приходит мужик в скобяную лавку и видит некий предмет. Он спрашивает:

F>- Сколько будет стоить 1?
F>- 6 ,- отвечают.
F>- А сколько будет стоить 12?
F>- 12 ,- был ответ
F>- А сколько будет стоить 237?
F>- 18 ,- сказали ему

F>Вопрос - чего покупал мужик? Задача на логику.

F>

это номерки на дверь

1 цифра стоит 6.

Здравствуйте AlexKu, Вы писали:

AK>Еще одна бородатая задачка.

AK>Какой следующий член последовательности:
AK>11, 21, 1112, ...

AK>Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.

Не так: 3112, 211213, ... ?

Здравствуйте AlexKu, Вы писали:

AK>Еще одна бородатая задачка.

AK>Какой следующий член последовательности:
AK>11, 21, 1112, ...

AK>Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.
Есть замечательный сайт ... ловите: cool site

Соответственно следующий член либо 1231 — "одна двойка, три единицы", либо 3112 — "три единицы, одна двойка". Классная последовательность!

Здравствуйте vladsm, Вы писали:


V>Не так: 3112, 211213, ... ?

Именно.

Здравствуйте Rumata, Вы писали:

R>Есть замечательный сайт ... ловите: cool site

R>Соответственно следующий член либо 1231 — "одна двойка, три единицы", либо 3112 — "три единицы, одна двойка". Классная последовательность!

Вариант 1231 не проходит. Иначе третий член исходной последовательности был бы 1211.
А вот 3112 — правильнный ответ.