Китайские весы

[Capella]

Все свои выкладки я написала выше, может быть можно лишь ещё добавить $... x_a = x_b, a \ne b$, но я думаю, что это и так ясно.
Вы в очередной раз более, чем не внимательны. Изначально функция $f_i$ отображется у меня в $\mathbb{R}$ и $f_1$ это лишь одно из её частных значений (т.е. именно элемент множества $\mathbb{R}$)
А использовала я обычное определение функции:
$f: X \to Y$, и если Вам не нравится, что здесь стоит элемент, то обзавите его большой буковкой и будет Вам счастье. Уверяю, смысл от этого не поменяется (поскольку множество одноэлементное). Или это из той-же серии, что лучше работать с группами монет, а не с монетами?

В общем и целом, я похоже завязываю отвечать в этой теме, поскольку ничего такого конкретного пока не вижу.

[juna]

Профессор Снэйп писал(а):

Зачем нам смешивать информацию?

Под "расшифровкой" я понимал расшифровку в первом смысле. И меня интересует возможность/невозможность произвести такую расшифровку за 3 действия.

Дело в том, что информация первого типа излишняя для решения исходной задачи о нахождении фальшивой монеты неизвестного веса на китайских весах.
Можно рассмотреть, варьируя количество монет $n$:
$n=2$ - вообще ничего нельзя определить при любом числе взвешиваний
$n=3$ - можно определить только информацию второго типа при любом числе взвешиваний
$n>3$ - можно определить информацию первого типа за четыре взвешивания. Единственная возможность определить перевес- недовес, это использовать только настоящие монеты, поскольку для фальшивки нам неизвестно легче она или тяжелее (и сможет стать известно только после получения информации первого типа). Достаточно трех настоящих монет. Тогда задача сводится к доказательству невозможности за два взвешивания найти хотя бы три настоящие монеты. Этот поиск придется совмещать с расшифровыванием иероглифа равенство. Тогда нужно доказать, что за два взвешивания в начале невозможно детерминированно опредедить иероглиф равенство, но ведь это очевидно - за два взвешивания отделить фальшивку нельзя (может только повезти).

arqady писал(а):

Julia доказала, что из 14 монет можно определить фальшивую за 4 взвешивания на китайских весах и 14 - это максимальное число монет для 4 взвешиваний.

Кто такая Julia?
Она это доказала теоретически или предъявила конкретный алгоритм как это сделать?
Вообще, известен такой результат ("Математическое просвещение"):
Максимальное число монет, из которых можно найти фальшивую за $k$ взвешиваний, не определяя ее относительный вес, равно $\frac{3^k-1}{2}$.
Но это на европейских весах.
Тогда с учетом задачи Профессора Снэйпа для китайских весов оценка получается такая:$\frac{3^{k-c}-1}{2}$, где $c<5$

[arqady]

juna писал(а):

arqady писал(а):

Julia доказала, что из 14 монет можно определить фальшивую за 4 взвешивания на китайских весах и 14 - это максимальное число монет для 4 взвешиваний.

Кто такая Julia?

Она не уполномочивала меня рассказывать про неё. Думаю, её ника вполне достаточно.

juna писал(а):

Она это доказала теоретически или предъявила конкретный алгоритм как это сделать?

Доказала - это означает доказала.

juna писал(а):

Вообще, известен такой результат ("Математическое просвещение"):
Максимальное число монет, из которых можно найти фальшивую за $k$ взвешиваний, не определяя ее относительный вес, равно $\frac{3^k+1}{2}$.
Но это на европейских весах.

Может Вы имеете в виду из

$$\frac{3^k-3}{2}$$

монет за

$$k$$

взвешиваний?
Если да, то этот результат был известен лет за тридцать до появления "Математического Просвещения".
Мне эта задача известна ( про обычные весы и

$$k$$

взвешиваний ) с одного из мат-боёв 679 школы Москвы ( боюсь ошибиться, но по-моему, со 2-ой, закончившийся разгромной победой 679 ) в конце 80-ых годов прошлого века.

[juna]

Там была ошибка, я ее поправил.
Статья Д. А. Михалин, И. М. Никонов "Одна задача о нахождении фальшивой монеты" здесь.
По вашей формуле считается с учетом определения веса фальшивки.

arqady писал(а):

Доказала - это означает доказала.

Это конструктивное доказательство или доказательство существования?

[arqady]

juna, конечно конструктивное!

[CD_Eater]

arqady писал(а):

juna писал(а):

arqady писал(а):

Julia доказала, что из 14 монет можно определить фальшивую за 4 взвешивания на китайских весах и 14 - это максимальное число монет для 4 взвешиваний.

Кто такая Julia?

Она не уполномочивала меня рассказывать про неё. Думаю, её ника вполне достаточно.

Может, он так ласково свой компьютер называет? Задачка вполне решаема перебором...

Больше 14 монет за 4 взвешивания не определить, потому что всего имеется только 14 четырёхсимвольных последовательностей на алфавите из 3 "неизвестных" иероглифов.

[Профессор Снэйп]

CD_Eater писал(а):

Больше 14 монет за 4 взвешивания не определить, потому что всего имеется только 14 четырёхсимвольных последовательностей на алфавите из 3 "неизвестных" иероглифов.

А разве не $3^4 = 81$?

Или Вы с точностью до перестановки символов считаете? Тогда их вроде бы действительно $14$ получается:

1) $aaaa$
2) $aaab$
3) $aaba$
4) $abaa$
5) $baaa$
6) $abab$
7) $abba$
8) $aabb$
9) $abcc$
10) $acbc$
11) $accb$
12) $aabc$
13) $abac$
14) $abca$

[juna]

CD_Eater писал(а):

Может, он так ласково свой компьютер называет?

Возможно. Тогда мы можем не дожить до того момента, когда она уполномочит.

CD_Eater писал(а):

Больше 14 монет за 4 взвешивания не определить, потому что всего имеется только 14 четырёхсимвольных последовательностей на алфавите из 3 "неизвестных" иероглифов.

Вы имеете в виду это:
1. АААА
2. АААВ
3. ААВА
4. ААВВ
5. ААВС
6. АВАА
7. АВАВ
8. АВАС
9. АВВА
10.АВВВ
11.АВВС
12.АВСА
13.АВСВ
14.АВСС
Что дальше?

Добавлено спустя 1 минуту 28 секунд:

Профессор Снэйп опередил.

Добавлено спустя 42 минуты 44 секунды:

Кстати, когда я говорил, что отделить фальшивку за два взвешивания нельзя, был не совсем прав. Если количество монет делится на 2, то можно.
Кладем поровну на каждую чашку, получаем иероглиф А (неравенство)
Убираем с каждой чашки весов однинаковое количество монет.
Если остается иероглиф А, то все монеты, которые убрали настоящие;
если получаем иероглиф В, то на чашках весов все монеты настоящие, и иероглиф В - равенство.
Но в худшем первом случае за оставшееся взвешивание мы все равно сможем определить только один иероглиф на выбор.

[Профессор Снэйп]

По моему, фиксирование показаний весов до и после "убирания монет" считается за 2 разных взвешивания.

[maxal]

arqady писал(а):

Может Вы имеете в виду из

$$\frac{3^k-3}{2}$$

монет за

$$k$$

взвешиваний?
Если да, то этот результат был известен лет за тридцать до появления "Математического Просвещения".
Мне эта задача известна ( про обычные весы и

$$k$$

взвешиваний ) с одного из мат-боёв 679 школы Москвы ( боюсь ошибиться, но по-моему, со 2-ой, закончившийся разгромной победой 679 ) в конце 80-ых годов прошлого века.

Доказательство также уже приводилось на нашем форуме.

[arqady]

CD_Eater писал(а):

arqady писал(а):

Julia доказала, что из 14 монет можно определить фальшивую за 4 взвешивания на китайских весах и 14 - это максимальное число монет для 4 взвешиваний.

Задачка вполне решаема перебором...

И не только им! Только как?

CD_Eater писал(а):

Больше 14 монет за 4 взвешивания не определить, потому что всего имеется только 14 четырёхсимвольных последовательностей на алфавите из 3 "неизвестных" иероглифов.

Вы абсолютно правы.