Шифроване с орехи

[ql^2/8]

Задача:
Двама шпиони разполагали с торба с 26 ореха. С тяхна помощ
трябва единият да предаде на другия таен код (число) и обратно.
Всеки от тях последователно можел да вземе от торбата няколко
ореха (поне един, а може и всичките) и да ги счупи пред другия.
Броят на счупените орехи е единствената информация, която си обменят!
Кой да почне пръв са решили предварително, без да знаят кодовете си.
В края на срещата трябва да са счупени всички орехи.
Търси се алгоритъм да се обменят кодове от цели числа от 1 до 1700?

[zxc0]

Най-прегледният и лесен начин за кодиране на числа е с двоичнодесетичен код. За числа до 1799 са необходими 12 числа. Едно за хилядите, три за стотиците(до число 7) и по 4 за десетиците и единиците.
Ако разделим по равно орехите имаме 13, т.е. един повече даже.
Този орех в повече може да го ползваме като като индикатор че числото е валидно(написано, готово...) и за заблуда на врага.
Единият взема 13 ореха, нарежда ги в редица или в колона или в 5 реда. Аз ще обясня за 5 реда за по-лесно обяснение, иначе реално е по-добре да са в редица подредени.
1 ред - 1 орех - хиляди
2 ред - 3 ореха - стотици
3 ред - 4 ореха - десетици
4 ред - 4 ореха - единици
5 ред - 1 орех - готово.

Счупен орех означава логическа единица, може и нула- както се разберат въпрос на вкус. Приемаме че е лог 1 и счупен ще бележа с Х, а здрав с О.
Идеята е да почне да чупи орехи както иска: отляво-надясно, отгоре-надолу, обратно, произволно. В момента в който счупи ореха в петият ред(готово), другият шпионин трябва да го разчете. След което дочупва останалите в произволен ред.
Колегата му прави същото с другите 13.
Предаването на числото 1396 би изглеждало така:
Х
ОХХ
ХООХ
ОХХО
О--> Х - този се счупва и се продължава с чупенето.
На един ред биха изглеждали така:
ХОХХХООХОХХОО-->Х - последният се счупва.

Орехът "готово" може да бъде, където и да е в редицата за по-голяма заблуда на врага.

[ql^2/8]

Пояснявам условието:
Всеки от шпионите взема няколко ореха и ги счупва. Всичките.
Здрав орех не остава накрая!

[zxc0]

Пояснявам условието:
Всеки от шпионите взема няколко ореха и ги счупва. Всичките.
Здрав орех не остава накрая!

Да де, шпионин 1 взема 13 и ги счупва, а шпионин 2 взема другите 13 и ги счупва.
Просто е важен момента в който се счупва ореха в петият ред.
В случая счупва 7 ореха за кода, осмият е за ореха "готово", след което счупва останалите 5. Общо 13 станаха.
Другият прави същото с другите 13.

[ql^2/8]

Прочети условието:
Броят на счупените орехи е единствената информация, която си обменят!
Само броят в даден ход е съществен, не реда на счупване. Ходовете може да се повече.
В твоя случай:
първи шпионин - първи ход - 13
втори шпионин - първи ход - 13
Няма повече ходове, защото орехите свършиха.

[Bibi]

13 на брой са възможните прости делители: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.
Може би тях трябва да подскажем с броя орехи?

Имам предвид, че намисленото число или само по себе си е просто, или е произведение на някои от описаните делители.

[MitkoS]

Що да са само 13 ?
..., 37, 41, 43, 47, 53, 59, 61, 67, 71 ...
https://en.wikipedia.org/wiki/List_of_prime_numbers

Аз мисля, че можем да ползваме 4-ична бройна система
1700 е по-малко от 2¹¹
С четири ореха кодираме число от нула до три, така че с три хода всеки не повече от четири взети и счупени ореха можем да кодираме трицифрено число в 4-ична бройна система.
И ако не бъркам нещо максималното трицифрено число в 4-ична бройна система е 2¹²
Т.е. с 12 ореха можем да кодираме от 0 до 2047 (до 2¹² -1)
Последния тринадесети, ще го ползваме да оправим някак си проблема с нулата ... това в случай, че има такъв проблем

ПП.
Големи глупости мога да сътворя понякога, ужас !

[Bibi]

@MitkoS, идеята ми беше по-друга.
Първият път взимаме толкова орехи, колкото делители има числото.
Ако е просто - взимаме 1 орех. Остава с 12 маркера да уточним кое измежду общо 266 възможни.
Ако не е, не знам какво да правим, Делителите му са измежду горните 13. Може да са най-много 4 различни. Никой не участва повече от 10 пъти...

[zxc0]

Позволено ли е Ш1 да направи 2 хода, а Ш2 да направи 10хода примерно?
Ако не е, се усложняват още нещата. Логично е и двамата да могат да предадат достатъчно сложни числа.
Ако на единият му се пада да чупи повече орехи, очевидно ще изхарчи своите 13 по-бързо и ще почне да взема от 13-те на другия.
Как всеки да счупи общо 13 ореха при еднакъв брой опити?

Кой почва първи е уточнено предварително! - тука каква е уловката, не знам.

[MitkoS]

Делителите му са измежду горните 13.

Е може да не са само горните тринадесет.
Числото 710 има три делителя - 2, 5, 71
А делителя 71 не е между горните 13

Позволено ли е Ш1 да направи 2 хода, а Ш2 да направи 10хода примерно?

Доколкото разбирам, чупенето разграничава ходовете.
Например първия е имал само 2-3 хода и ги е приключил, а втория има още няколко хода. Взима орехи и ги чупи. Щом ги счупи, то хода е свършил и почва следващия ход от същия шпионин с ново взимане на орехи.

[Bibi]

Дам. Може изобщо да не помагат делителите.
Двоичното представяне е с максимум 11 цифри. Може би някак с него тогава?
Мисля, че трябва да намерим нещо, за което 1700 е праг.
Освен това защо ги чупи? Ако просто ги вземе явно не е същото. Може пък да им значение как ги чупи?

[zxc0]

За начина на чупене - дадох решение горе, ама не е позволено.
Така позволено ли е?
Ш1 чупи 12
Ш2 чупи 1
Ш1 чупи 1
Ш2 чупи 1
Ш2 чупи 1
Ш2 чупи 2
... и т.н.
Ш2 чупи останалите докрая по колкото му трябват.

[Bibi]

Със битовете би трябвало да се получи. Всеки ще счупи по 13 ореха.
Представяме избраното число двоично и го допълваме отпред с нули до 13 цифрено.
получаваме 00...01..10...0...
A нули, B единици, C нули, D едници,...
Но наистина проблемът е, че единият може много рано да си свърши ходовете.

[ql^2/8]

Двамата се редуват да правят ход. При всеки ход се чупи поне един орех
Единият може да счупи повече от 13 ореха, може да счупи всички останали
в торбата. Няма значение как ги чупи - само броят има значение.

[MitkoS]

При всеки ход се чупи поне един орех

Ако искаме на един ход да предадем "0" или "1", то при 13 на брой ореха можем да предадем най-много 6 или 7 общо на брой нули и единици.
Но понеже знаем какво ни е казал другия, то можем да се изхитрим да ползваме неговата предадена информация и да спестим малко орехи.
Пример
Първия трябва да предаде 1010
Втория трябва да предаде 1100
Първи ход на първия - чупи два ореха с което казва "първата позиция при мен е "1"".
Първи ход на втория - чупи два ореха с което казва "първата позиция при мен е "1"" и евентуално ще счупи трети орех с който ще потвърди, че неговата следваща позиция съвпада с тази на първия. В конкретния пример втория ще счупи и трети орех с което е предал "втората ми позиция е като твоята предишната, т.е."1""
Втори ход на първия - чупи един орех за неговата нула на втора позиция и още един да потвърди, че третата му позиция съвпада с втората на първия. Т.е., чупи два ореха, което може още и да значи, че при него слдат не 0 и 1, а 1 и 0 ... ЛОШО ! НЕ СТАВА С ТАЗИ СТРАТЕГИЯ ! Но няма да я трия щото идеята да ползваме вече съществуваща информация от другия си заслужава, ... нещо като XOR