Вернуться   Финляндия по-русски » Жизнь в Финляндии » Бойцовский клуб (вcякoe, off-topic, флeйм)
Логин
Пароль

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
Old 03-05-2019, 23:36   #301
Димыч
Пользователь
 
Сообщений: 2,751
Проживание:
Регистрация: 26-07-2015
Status: Offline
Ребята, дела тухлые...
Я тут задачу про "тюремщика и заключенных" задал одному шутнику.
Он немного поднапрягся и выдал следущее.
Грит, что все эти твои "маски" - полная лажа и "надувание щёк".
На самом деле там всё проще пареной репы.
Можно просто взять и, например, отксорить все порядковые номера аверсов (без всяких "масок" и прочей ерунды). После чего полученное шестибитовое число отксорить с порядковым номером "волшебной" монеты и всё - это и будет порядковый номер той монеты, которую надо перевернуть! Т.е. на полученной доске, если теперь отксорить снова все аверсы - получишь порядковый номер "волшебной" монеты.
ВСЁ!
Проверяйте
P.s. Я прямо был очень сильно разочарован, потому как стращал его, что эта задача простыми способами не решается
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 00:24   #302
ratel
Пользователь
 
Сообщений: 16
Проживание:
Регистрация: 17-03-2017
Status: Offline
Цитата:
Сообщение от alexer
Вот вам более интересная загадка: двое заключенных были приговорены к смерти...


Хорошая задача, спасибо, приятно вечером после рабочей недели немного поразмышлять.

Цитата:
Сообщение от alexer
Сразу говорю, что задача сложная, но для ее решения не нужно никакой математики: только аналитическое мышление.


Ох-ох, ну, мне для решения математика всё же пригодилась, но, верю, кому-то будет достаточно просто очень хорошего воображения

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

На мой взгляд задачу можно переформулировать попроще: представить раскраску вершин 64-мерного единичного куба в 64 цвета так, чтобы у любой вершины все её соседние вершины были разных цветов, это в предположении, что первый заключённый обязан перевернуть какую-нибудь монету, и заметим, что это более сложный случай, его и буду рассматривать.

В общем случае вершины n-мерного куба раскрасить в n цветов с таким условием нельзя, например, можете попытаться сделать такое перебором с обычным 3-мерным кубом. А вот с кубами размерности 2**n придумать такую раскраску можно, я отталкивался от естественной раскраски 4-мерного куба (смогу показать рисунок, если тут непонятно), надо добиться, чтобы изменение значения одной координаты вершины давало новый цвет. Другими словами если координаты вершины выписать в строку 2**n битов, то функция получения цвета вершины от изначальной с XOR от 2**k, где k от 0 до n-1, перебирала бы все n цветов, то есть была сюръективной. Если (2**n)-мерный куб представить как вытянутый по ещё одной оси уже раскрашенный (2**n - 1)-мерный куб, то изменение значения на этой последней координате не будет менять цвет, её можно исключить, а для остальных (2**n - 1) координат естественной функцией раскраски будет XOR от всех позиций(!) координат, где стоит единица. Для такой функции легко проверить выполнение требуемого свойства для раскраски вершин.

И, собственно, код для проверки моей идеи, надеюсь, что там всё достаточно очевидно. А если найдёте ошибку, то с меня подарок за ваше время и внимание.

Код:
#include <stdio.h> #include <stdlib.h> static unsigned int find_lsb_set(unsigned long long n) { unsigned int pos = 0; if (!(n & 0xffffffff)) { pos += 32; n >>= 32; } if (!(n & 0xffff)) { pos += 16; n >>= 16; } if (!(n & 0xff)) { pos += 8; n >>= 8; } if (!(n & 0xf)) { pos += 4; n >>= 4; } if (!(n & 0x3)) { pos += 2; n >>= 2; } if (!(n & 0x1)) pos += 1; return pos; } static unsigned int colour_decode(unsigned long long n) { unsigned int pos, colour = 0; /* Get the same colour if MSB is flipped, it also ensures that the resulting colour is in the expected range. */ n &= ~(1ULL << 63); for (; n; n &= ~(1ULL << pos)) { pos = find_lsb_set(n); colour ^= (pos + 1); } return colour; } static int save_prisoners(unsigned long long board, unsigned int secret) { unsigned int colour, flip, guess; /* Get an initial colour of the given configuration of coins */ colour = colour_decode(board); /* Select a cell to flip a coin to get the wanted colour of the board, remember that flipping MSB does not change the colour. */ if (secret != colour) flip = (colour ^ secret) - 1; else flip = 63; /* Flip a coin on the selected cell */ board ^= (1ULL << flip); /* Get a colour of the changed board */ guess = colour_decode(board); printf("board: %016llx, secret: %02u --> " "colour: %02u, flip: %02u, guess: %02u\n", board, secret, colour, flip, guess); return (secret == guess); } int main(int argc, char **argv) { unsigned long long board; unsigned int secret, i; for (i = 0; i < 8; i++) { srandom((1 << i) + i); /* Represent a 8x8 board with coins as a (2**6)-bit number */ board = (unsigned long long)random() << 32 | random(); /* Encode a secret cell position as a 6-bit colour */ secret = random() & 0x3f; /* Try to save prisoners */ if (save_prisoners(board, secret)) printf("Innocent people are saved.\n\n"); else printf("Guileful villains are executed.\n\n"); } return 0; }
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 08:34   #303
alexer
Пользователь
 
Сообщений: 1,495
Проживание:
Регистрация: 02-09-2016
Status: Offline
Thumbs up

Цитата:
Сообщение от Димыч
Ребята, дела тухлые...
Я тут задачу про "тюремщика и заключенных" задал одному шутнику.
Он немного поднапрягся и выдал следущее.
Грит, что все эти твои "маски" - полная лажа и "надувание щёк".
На самом деле там всё проще пареной репы.
Можно просто взять и, например, отксорить все порядковые номера аверсов (без всяких "масок" и прочей ерунды). После чего полученное шестибитовое число отксорить с порядковым номером "волшебной" монеты и всё - это и будет порядковый номер той монеты, которую надо перевернуть! Т.е. на полученной доске, если теперь отксорить снова все аверсы - получишь порядковый номер "волшебной" монеты.
ВСЁ!
Проверяйте
P.s. Я прямо был очень сильно разочарован, потому как стращал его, что эта задача простыми способами не решается

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

Последнее редактирование от alexer : 04-05-2019 в 09:38.
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 09:10   #304
alexer
Пользователь
 
Сообщений: 1,495
Проживание:
Регистрация: 02-09-2016
Status: Offline
Цитата:
Сообщение от ratel
Хорошая задача, спасибо, приятно вечером после рабочей недели немного поразмышлять.



Ох-ох, ну, мне для решения математика всё же пригодилась, но, верю, кому-то будет достаточно просто очень хорошего воображения

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

На мой взгляд задачу можно переформулировать попроще: представить раскраску вершин 64-мерного единичного куба в 64 цвета так, чтобы у любой вершины все её соседние вершины были разных цветов, это в предположении, что первый заключённый обязан перевернуть какую-нибудь монету, и заметим, что это более сложный случай, его и буду рассматривать.

В общем случае вершины n-мерного куба раскрасить в n цветов с таким условием нельзя, например, можете попытаться сделать такое перебором с обычным 3-мерным кубом. А вот с кубами размерности 2**n придумать такую раскраску можно, я отталкивался от естественной раскраски 4-мерного куба (смогу показать рисунок, если тут непонятно), надо добиться, чтобы изменение значения одной координаты вершины давало новый цвет. Другими словами если координаты вершины выписать в строку 2**n битов, то функция получения цвета вершины от изначальной с XOR от 2**k, где k от 0 до n-1, перебирала бы все n цветов, то есть была сюръективной. Если (2**n)-мерный куб представить как вытянутый по ещё одной оси уже раскрашенный (2**n - 1)-мерный куб, то изменение значения на этой последней координате не будет менять цвет, её можно исключить, а для остальных (2**n - 1) координат естественной функцией раскраски будет XOR от всех позиций(!) координат, где стоит единица. Для такой функции легко проверить выполнение требуемого свойства для раскраски вершин.

И, собственно, код для проверки моей идеи, надеюсь, что там всё достаточно очевидно. А если найдёте ошибку, то с меня подарок за ваше время и внимание.

Код:
#include <stdio.h> #include <stdlib.h> static unsigned int find_lsb_set(unsigned long long n) { unsigned int pos = 0; if (!(n & 0xffffffff)) { pos += 32; n >>= 32; } if (!(n & 0xffff)) { pos += 16; n >>= 16; } if (!(n & 0xff)) { pos += 8; n >>= 8; } if (!(n & 0xf)) { pos += 4; n >>= 4; } if (!(n & 0x3)) { pos += 2; n >>= 2; } if (!(n & 0x1)) pos += 1; return pos; } static unsigned int colour_decode(unsigned long long n) { unsigned int pos, colour = 0; /* Get the same colour if MSB is flipped, it also ensures that the resulting colour is in the expected range. */ n &= ~(1ULL << 63); for (; n; n &= ~(1ULL << pos)) { pos = find_lsb_set(n); colour ^= (pos + 1); } return colour; } static int save_prisoners(unsigned long long board, unsigned int secret) { unsigned int colour, flip, guess; /* Get an initial colour of the given configuration of coins */ colour = colour_decode(board); /* Select a cell to flip a coin to get the wanted colour of the board, remember that flipping MSB does not change the colour. */ if (secret != colour) flip = (colour ^ secret) - 1; else flip = 63; /* Flip a coin on the selected cell */ board ^= (1ULL << flip); /* Get a colour of the changed board */ guess = colour_decode(board); printf("board: %016llx, secret: %02u --> " "colour: %02u, flip: %02u, guess: %02u\n", board, secret, colour, flip, guess); return (secret == guess); } int main(int argc, char **argv) { unsigned long long board; unsigned int secret, i; for (i = 0; i < 8; i++) { srandom((1 << i) + i); /* Represent a 8x8 board with coins as a (2**6)-bit number */ board = (unsigned long long)random() << 32 | random(); /* Encode a secret cell position as a 6-bit colour */ secret = random() & 0x3f; /* Try to save prisoners */ if (save_prisoners(board, secret)) printf("Innocent people are saved.\n\n"); else printf("Guileful villains are executed.\n\n"); } return 0; }

ratel, ваше решение совпадает с решением, которое выше описал Димыч. На самом деле, обоснование можно получить из элементарных свойств операции XOR, представлять себе N-мерные кубы не надо
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 10:10   #305
Димыч
Пользователь
 
Сообщений: 2,751
Проживание:
Регистрация: 26-07-2015
Status: Offline
Цитата:
Сообщение от alexer
Да, это будет работать. А слабо обосновать почему? Впрочем, это действительно лаконичный, хотя и не самый вычислительно простой способ. Спасибо!
А чего разочаровываться-то? Было бы это просто, все бы сразу догадались То, что решение легко формулируется, не означает его очевидности.


Это следует из определения операции XOR.
Для случая, когда монета, которую надо перевернуть, увеличивает количество монет, которые ксорятся получаем:
S XOR (S XOR A) = A
Где S - первоначальная сумма аверсов;
А - порядковый номер "волшебной монеты;
(S XOR A) = В - порядковый номер монеты, которую надо перевернуть.

Для случая, когда переворачиваемая монета уменьшает количество монет, которые "ксорятся", получаем по сути то же самое, т.к. убрать ксорящееся слагаемое равносильно его повторному добавлению - всё по тому же самому правилу
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 10:50   #306
alexer
Пользователь
 
Сообщений: 1,495
Проживание:
Регистрация: 02-09-2016
Status: Offline
Цитата:
Сообщение от Димыч
Это следует из определения операции XOR.
Для случая, когда монета, которую надо перевернуть, увеличивает количество монет, которые ксорятся получаем:
S XOR (S XOR A) = A
Где S - первоначальная сумма аверсов;
А - порядковый номер "волшебной монеты;
(S XOR A) = В - порядковый номер монеты, которую надо перевернуть.

Для случая, когда переворачиваемая монета уменьшает количество монет, которые "ксорятся", получаем по сути то же самое, т.к. убрать ксорящееся слагаемое равносильно его повторному добавлению - всё по тому же самому правилу

Да, все верно. Как видите, такое решение вполне можно предложить за 45 минут. Кстати, только что посмотрел, в комментариях к статье на "хабре" это решение уже предлагали.
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 12:13   #307
Димыч
Пользователь
 
Сообщений: 2,751
Проживание:
Регистрация: 26-07-2015
Status: Offline
Цитата:
Сообщение от alexer
Да, все верно. Как видите, такое решение вполне можно предложить за 45 минут. Кстати, только что посмотрел, в комментариях к статье на "хабре" это решение уже предлагали.

В принципе да, наверное можно было придумать решение за 45 минут
Просто уж очень страшно звучит. А после прочтения решения с "масками", только укрепляешься во мнении о том, что "и правильно, что даже браться не стал!"
 
0
 
0
    Ответить с цитированием
Old 04-05-2019, 13:49   #308
Димыч
Пользователь
 
Сообщений: 2,751
Проживание:
Регистрация: 26-07-2015
Status: Offline
Но для любителей логических задач есть и такая прекрасная задача:
"
«Привет!» — «Привет!» — «Как дела?» — «Хорошо. Растут два сына, дошкольника». — «А сколько им лет?» — «Произведение их возрастов равно числу голубей около этой скамейки». — «Этой информации мне недостаточно!» — «Старший похож на мать». — «Вот теперь я знаю ответ на свой вопрос!»
"
Сколько лет детям?
 
0
 
0
    Ответить с цитированием
Old 20-05-2019, 16:49   #309
Димыч
Пользователь
 
Сообщений: 2,751
Проживание:
Регистрация: 26-07-2015
Status: Offline
Задача про трёх Богов (позиционируется как "самая сложная логическая задача")

Цитата:
Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Каждый вопрос задаётся только одному богу, но можно задавать одному богу более одного вопроса. Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja», причём неизвестно, какое слово обозначает «да», а какое «нет».


=================================== =================================== ==================
Только что решил с небольшой подсказкой. Долго мучился, но доволен
 
Old 29-06-2019, 00:30   #310
ratel
Пользователь
 
Сообщений: 16
Проживание:
Регистрация: 17-03-2017
Status: Offline
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 01:56   #311
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от alexer
Вот вам более интересная загадка: двое заключенных были приговорены к смерти. Однако им была предложена следующая сделка. Одного из заключенных (неважно, которого) надзиратель приглашает в комнату и выкладывает на шахматную доску 64 монеты, по одной в каждую клетку, произвольно вверх аверсом или реверсом. После того, как монеты выложены, надзиратель показывает на одну из них и говорит, что эта монета — "магическая" и если второй заключенный (который в комнате не присутствует) ее отгадает, то оба будут помилованы. В противном случае обоих казнят. Заключенный, присутствовавший в комнате, имеет право попросить надзирателя перевернуть одну из монет (заключенный может выбрать какую либо оставить все без изменений). Вопрос: о какой стратегии следовало договориться заключенным, чтобы второй из них, зайдя в комнату, всегда мог безошибочно угадать "магическую" монету. Оба заключенных очень умны и обладают превосходной памятью.

Сразу говорю, что задача сложная, но для ее решения не нужно никакой математики: только аналитическое мышление.

Не сложная. Математика нужна. На решение ушла 1 минута. Никуда не смотрел, ваши решения не читал.

Обозначим все монеты как Mi, где i меняется от 0 до 63, а Mi принимает значения 0 (орел) или 1 (решка).

Вычислим сумму по модулю два (XOR) произведений позиций монет на их значения:


S - будет числом в диапазоне 0...63 и, таким образом, указывать на позицию монеты от 0 до 63.

Пусть P - номер позиции магической монеты. Вычислим сумму по модулю два S и P.

Эта сумма и будет номером монеты, которую нужно перевернуть.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 08:51   #312
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от Димыч
Но для любителей логических задач есть и такая прекрасная задача:
"
«Привет!» — «Привет!» — «Как дела?» — «Хорошо. Растут два сына, дошкольника». — «А сколько им лет?» — «Произведение их возрастов равно числу голубей около этой скамейки». — «Этой информации мне недостаточно!» — «Старший похож на мать». — «Вот теперь я знаю ответ на свой вопрос!»
"
Сколько лет детям?

Что в ней прекрасного?

Число голубей - N
N является квадратом (информация, что один из детей старше другого - помогла в решении, исключив вариант одинакового возраста).
Для дошкольников есть всего один вариант, N = 4. Старшему сыну 4 года, а младшему - 1.

Следующий квадрат - 9. Но старшему сыну не может быть 9 лет, ведь он дошкольник. 16 тоже не подходит, так как 8 лет - тоже уже школьный возраст.

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

Но думать при "решении" здесь вообще не нужно.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 09:01   #313
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Что в ней прекрасного?

Число голубей - N
N является квадратом (информация, что один из детей старше другого - помогла в решении, исключив вариант одинакового возраста).
Для дошкольников есть всего один вариант, N = 4. Старшему сыну 4 года, а младшему - 1.

Следующий квадрат - 9. Но старшему сыну не может быть 9 лет, ведь он дошкольник. 16 тоже не подходит, так как 8 лет - тоже уже школьный возраст.

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

Но думать при "решении" здесь вообще не нужно.

Почему квадратом? Почему N не может быть 2, 3, 5, 6?
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 09:03   #314
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Не сложная. Математика нужна. На решение ушла 1 минута. Никуда не смотрел, ваши решения не читал.

Обозначим все монеты как Mi, где i меняется от 0 до 63, а Mi принимает значения 0 (орел) или 1 (решка).

Вычислим сумму по модулю два (XOR) произведений позиций монет на их значения:


S - будет числом в диапазоне 0...63 и, таким образом, указывать на позицию монеты от 0 до 63.

Пусть P - номер позиции магической монеты. Вычислим сумму по модулю два S и P.

Эта сумма и будет номером монеты, которую нужно перевернуть.

И как ты эту сумму передашь второму заключенному? Это уже выяснили, что можно только передвинуть одну фигуру, сообщать числа нельзя.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 10:16   #315
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Почему квадратом? Почему N не может быть 2, 3, 5, 6?

Информация, что один из детей старше другого, могла помочь только, если был выбор между двумя ситуациями, одна из которых - близнецы (одинаковый возраст, произведение возрастов является квадратом какого-то числа).
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 10:18   #316
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
И как ты эту сумму передашь второму заключенному? Это уже выяснили, что можно только передвинуть одну фигуру, сообщать числа нельзя.

Зачем ее передавать? Он посмотрит на доску и вычислит в уме эту сумму. Для вычисления суммы нужно лишь видеть монеты на доске.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 10:33   #317
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Информация, что один из детей старше другого, могла помочь только, если был выбор между двумя ситуациями, одна из которых - близнецы (одинаковый возраст, произведение возрастов является квадратом какого-то числа).

Пример N=3, это произведение 3*1, и так далее. Квадрат не обязателен, поэтому вариантов больше.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 11:32   #318
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Пример N=3, это произведение 3*1, и так далее. Квадрат не обязателен, поэтому вариантов больше.

Для ситуации N=3 человек из задачи нашел бы ответ без уточнения, что один из детей старше другого.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 16:59   #319
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Для ситуации N=3 человек из задачи нашел бы ответ без уточнения, что один из детей старше другого.

Ну и что? Какая разница, есть уточнение или нет. Всё равно ответов несколько.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 17:11   #320
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Не сложная. Математика нужна. На решение ушла 1 минута. Никуда не смотрел, ваши решения не читал.

Обозначим все монеты как Mi, где i меняется от 0 до 63, а Mi принимает значения 0 (орел) или 1 (решка).

Вычислим сумму по модулю два (XOR) произведений позиций монет на их значения:


S - будет числом в диапазоне 0...63 и, таким образом, указывать на позицию монеты от 0 до 63.

Пусть P - номер позиции магической монеты. Вычислим сумму по модулю два S и P.

Эта сумма и будет номером монеты, которую нужно перевернуть.

Давай по другому.
Проведем 2 эксперимента. 1. надзиратель указывает клетку А4, 2. надзиратель указывает А5. Как будет изменяться твоя формула для этих экспериментов? Она же должна меняться.
Мне кажется вы не можете понять что именно надзиратель выбирает магическую монету. Если бы заключенный, то ясно что они могут договориться об одной формуле, и находить по ней число. Но для этого и формула не нужна, можно просто договориться какую клетку выбирать.
А в голову надзирателя вы не залезете, он может выбрать любой из 64 вариантов, поэтому договориться об одной формуле нереально. Переворачиванием одной монеты можно сократить область поиска, но не указать точное местоположение.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 18:59   #321
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Ну и что? Какая разница, есть уточнение или нет. Всё равно ответов несколько.

Ну нет же. После уточнения для N=4 остается единственный ответ.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 19:05   #322
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Давай по другому.
Проведем 2 эксперимента. 1. надзиратель указывает клетку А4, 2. надзиратель указывает А5. Как будет изменяться твоя формула для этих экспериментов? Она же должна меняться.

Формула не меняется. Меняется ответ, полученный по формуле - сумма по модулю два (оператор XOR) чисел S и P. Она четко зависит от P и после переворачивания монеты с полученным порядковым номером S начинает указывать на P.

Сумма по модулю два обладает одним полезным свойством, которое здесь и используется.

Y xor X xor X = Y

Это свойство широко используется, например, в криптографии: в одноразовых блокнотах, в скрэмблерах. Очень близкой аналогией к данной задаче является задача разделения секрета между многими участниками. Именно поэтому эта задача с монетами решается без всяких усилий за минуту. Я много лет преподавал (в числе прочего) защиту информации в университете, так что более-менее ориентируюсь в соответствующей алгоритмической базе...
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 19:24   #323
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Формула не меняется. Меняется ответ, полученный по формуле - сумма по модулю два (оператор XOR) чисел S и P. Она четко зависит от P и после переворачивания монеты с полученным порядковым номером S начинает указывать на P.

Сумма по модулю два обладает одним полезным свойством, которое здесь и используется.

Y xor X xor X = Y

Это свойство широко используется, например, в криптографии: в одноразовых блокнотах, в скрэмблерах. Очень близкой аналогией к данной задаче является задача разделения секрета между многими участниками. Именно поэтому эта задача с монетами решается без всяких усилий за минуту. Я много лет преподавал (в числе прочего) защиту информации в университете, так что более-менее ориентируюсь в соответствующей алгоритмической базе...

Хорошо, не формула меняется, а значение переменной в формуле. Поэтому и ответ меняется. Логично?
То что вы математически можете описать доску это понятно. Но в сотый раз повторю. У нас есть 3 действующих лица в задаче. Как в театре. Есть 64 варианта ответа, один из которых случайным образом выбирает надзиратель. Первый заключенный не может передать второму как изменилось значение переменной в формуле. Тоже логично? Поэтому точного ответа быть в принципе не может.

Если есть формула, о использовании которой можно договориться и она даст правильный ответ на любую из 64 монет, то почему только 64 а не 1000000 например. И вообще, где была такая волшебная формула когда я женился?
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 19:28   #324
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Ну нет же. После уточнения для N=4 остается единственный ответ.

Детям 3 года и 1 год. N=3 . Тоже самое.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 21:17   #325
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Детям 3 года и 1 год. N=3 . Тоже самое.

В этом случае человеку хватило бы информации сразу, без уточнения, что старший сын похож на свою мать.
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 21:36   #326
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Unhappy

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

Как говорится, слив засчитан?
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 23:34   #327
Одиссей
Mamil
 
Аватар для Одиссей
 
Сообщений: 2,683
Проживание: default city
Регистрация: 26-01-2010
Status: Offline
Цитата:
Сообщение от ponom
Не сложная
...
Вычислим сумму по модулю два S и P.

Только по модулю 64 все-таки.

-----------------
μηδὲν ἄγαν
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 23:55   #328
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Как говорится, слив засчитан?

Какой слив? В условии задачи прямо говорится, что человек сказал, что имеющейся информации ему не достаточно.
Если бы там было три голубя, то он бы такого не мог сказать, так как в этой ситуации вариант всего один (3 и 1 год) и информации достаточно.

Для N=3 дополнительная информация не нужна. А по условию задачи она понадобилась.

Поэтому Ваш вариант отпадает, как противоречащий исходным данным задачи. Какой слив?
 
0
 
0
    Ответить с цитированием
Old 29-06-2019, 23:58   #329
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от Одиссей
Только по модулю 64 все-таки.


Почему? Я имею ввиду именно по модулю 2. Числа там будут 6-ти битные (0..63). И над ними должна выполняться побитная операция XOR (сложение по модулю 2).

https://ru.wikipedia.org/wiki/%D0%A...3%D0%BB%D1%8E_2
 
0
 
0
    Ответить с цитированием
Old 30-06-2019, 00:08   #330
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Хорошо, не формула меняется, а значение переменной в формуле. Поэтому и ответ меняется. Логично?
То что вы математически можете описать доску это понятно. Но в сотый раз повторю. У нас есть 3 действующих лица в задаче. Как в театре. Есть 64 варианта ответа, один из которых случайным образом выбирает надзиратель. Первый заключенный не может передать второму как изменилось значение переменной в формуле.

Объясняю еще раз на пальцах.

Формула указывает на монету S.

Первый заключенный вычисляет в уме по формуле это значение S. Затем вычисляет D = S xor P (P-позиция магической монеты).

После этого первый заключенный переворачивает монету D. Этим самым он меняет значение соответствующей переменной и формула начинает выдавать уже другое значние S' = S xor D.

Теперь подставим в эту формулу "S xor P" вместо D и получим S' = S xor S xor P.

По свойству операции xor любое прибавленное два раза число сокращается и остается S' = P.

Второй заключенный заходит, смотрит на доску (с уже перевернутой монетой D), вычисляет по формуле число S' и имеет таким образом правильный ответ P.

Ничего передавать второму заключенному от первого не нужно.
 
0
 
0
    Ответить с цитированием
Old 30-06-2019, 07:01   #331
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от Димыч
Задача про трёх Богов (позиционируется как "самая сложная логическая задача")

Уважаю. Я не решил, хотя сразу было ясно, что нужно использовать отрицание отрицания для нивелирования лжи всегда лгущего бога, и неопределенности слов ja и da. Не хватило терпения подобрать правильный вопрос и продумать ветвление возможных ответов.

Эти "ja" и "da" порядком запутывают. Лучше бы боги отвечали Y и Z.
 
0
 
0
    Ответить с цитированием
Old 30-06-2019, 11:04   #332
Одиссей
Mamil
 
Аватар для Одиссей
 
Сообщений: 2,683
Проживание: default city
Регистрация: 26-01-2010
Status: Offline
Цитата:
Сообщение от ponom
Почему? Я имею ввиду именно по модулю 2. Числа там будут 6-ти битные (0..63). И над ними должна выполняться побитная операция XOR (сложение по модулю 2).

Да это я уже запутался. В таком варианте решения нужно ксорить побитно.

-----------------
μηδὲν ἄγαν
 
0
 
0
    Ответить с цитированием
Old 30-06-2019, 19:27   #333
R60
Пользователь
 
Сообщений: 2,007
Проживание:
Регистрация: 20-12-2012
Status: Online
Цитата:
Сообщение от ponom
Объясняю еще раз на пальцах.

Формула указывает на монету S.

Первый заключенный вычисляет в уме по формуле это значение S. Затем вычисляет D = S xor P (P-позиция магической монеты).

После этого первый заключенный переворачивает монету D. Этим самым он меняет значение соответствующей переменной и формула начинает выдавать уже другое значние S' = S xor D.

Теперь подставим в эту формулу "S xor P" вместо D и получим S' = S xor S xor P.

По свойству операции xor любое прибавленное два раза число сокращается и остается S' = P.

Второй заключенный заходит, смотрит на доску (с уже перевернутой монетой D), вычисляет по формуле число S' и имеет таким образом правильный ответ P.

Ничего передавать второму заключенному от первого не нужно.

Второй заключенный что бы вычислить S' по формуле должен знать какая монета перевернутая, то-есть D. По условиям задачи он этого не должен знать. Свою формулу посмотри, там D есть.
 
0
 
0
    Ответить с цитированием
Old 30-06-2019, 19:59   #334
ponom
uusi jäsen
 
Аватар для ponom
 
Сообщений: 2,676
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Второй заключенный что бы вычислить S' по формуле должен знать какая монета перевернутая, то-есть D. По условиям задачи он этого не должен знать. Свою формулу посмотри, там D есть.

Нет, не должен. Он просто суммирует (мо модулю два) произведения позиций ВСЕХ монет на доске на значения монет. Среди этих монет на доске - и перевернутая. Сам факт переворачивания уже изменил значение суммы, вычисляемой по формуле так, чтобы она указывала на магическую монету.
 
0
 
0
    Ответить с цитированием
Ответ


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

vB коды Вкл.
[IMG] код Вкл.
HTML код Выкл.



» Объявления на Doska.fi

» Галерея Финляндии

» Реклама на Doska.fi

» Общение в городах

» Реклама на Russian.fi


Часовой пояс GMT +3, время: 22:47.

Russian.fi - Финляндия по-русски © Suomitech Oy, 2002-2019 При использовании материалов с сайта указание ссылки на russian.fi обязательно