Ребята, дела тухлые...
Я тут задачу про "тюремщика и заключенных" задал одному шутнику.
Он немного поднапрягся и выдал следущее.
Грит, что все эти твои "маски" - полная лажа и "надувание щёк".
На самом деле там всё проще пареной репы.
Можно просто взять и, например, отксорить все порядковые номера аверсов (без всяких "масок" и прочей ерунды). После чего полученное шестибитовое число отксорить с порядковым номером "волшебной" монеты и всё - это и будет порядковый номер той монеты, которую надо перевернуть! Т.е. на полученной доске, если теперь отксорить снова все аверсы - получишь порядковый номер "волшебной" монеты.
ВСЁ!
Проверяйте
P.s. Я прямо был очень сильно разочарован, потому как стращал его, что эта задача простыми способами не решается
Вот вам более интересная загадка: двое заключенных были приговорены к смерти...
Хорошая задача, спасибо, приятно вечером после рабочей недели немного поразмышлять.
Цитата:
Сообщение от 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;
}
Ребята, дела тухлые...
Я тут задачу про "тюремщика и заключенных" задал одному шутнику.
Он немного поднапрягся и выдал следущее.
Грит, что все эти твои "маски" - полная лажа и "надувание щёк".
На самом деле там всё проще пареной репы.
Можно просто взять и, например, отксорить все порядковые номера аверсов (без всяких "масок" и прочей ерунды). После чего полученное шестибитовое число отксорить с порядковым номером "волшебной" монеты и всё - это и будет порядковый номер той монеты, которую надо перевернуть! Т.е. на полученной доске, если теперь отксорить снова все аверсы - получишь порядковый номер "волшебной" монеты.
ВСЁ!
Проверяйте
P.s. Я прямо был очень сильно разочарован, потому как стращал его, что эта задача простыми способами не решается
Да, это будет работать. А слабо обосновать почему? Впрочем, это действительно лаконичный, хотя и не самый вычислительно простой способ. Спасибо!
А чего разочаровываться-то? Было бы это просто, все бы сразу догадались То, что решение легко формулируется, не означает его очевидности. Да и собственно, тот способ, который выше приводился — это те же самые XOR-ы, только несколько иначе организованные. Разве XOR-ы - это сложно?
Последнее редактирование от alexer : 04-05-2019 в 09:38.
Хорошая задача, спасибо, приятно вечером после рабочей недели немного поразмышлять.
Ох-ох, ну, мне для решения математика всё же пригодилась, но, верю, кому-то будет достаточно просто очень хорошего воображения
Очень часто мне сложно понять как мыслят программисты, да и вообще любой человек, и, возможно, наоборот может быть верно тоже, поэтому я кратко опишу свой ход мыслей, а если будет кому-нибудь непонятно и интересно, то смогу более детально рассказать.
На мой взгляд задачу можно переформулировать попроще: представить раскраску вершин 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-мерные кубы не надо
Да, это будет работать. А слабо обосновать почему? Впрочем, это действительно лаконичный, хотя и не самый вычислительно простой способ. Спасибо!
А чего разочаровываться-то? Было бы это просто, все бы сразу догадались То, что решение легко формулируется, не означает его очевидности.
Это следует из определения операции XOR.
Для случая, когда монета, которую надо перевернуть, увеличивает количество монет, которые ксорятся получаем:
S XOR (S XOR A) = A
Где S - первоначальная сумма аверсов;
А - порядковый номер "волшебной монеты;
(S XOR A) = В - порядковый номер монеты, которую надо перевернуть.
Для случая, когда переворачиваемая монета уменьшает количество монет, которые "ксорятся", получаем по сути то же самое, т.к. убрать ксорящееся слагаемое равносильно его повторному добавлению - всё по тому же самому правилу
Это следует из определения операции XOR.
Для случая, когда монета, которую надо перевернуть, увеличивает количество монет, которые ксорятся получаем:
S XOR (S XOR A) = A
Где S - первоначальная сумма аверсов;
А - порядковый номер "волшебной монеты;
(S XOR A) = В - порядковый номер монеты, которую надо перевернуть.
Для случая, когда переворачиваемая монета уменьшает количество монет, которые "ксорятся", получаем по сути то же самое, т.к. убрать ксорящееся слагаемое равносильно его повторному добавлению - всё по тому же самому правилу
Да, все верно. Как видите, такое решение вполне можно предложить за 45 минут. Кстати, только что посмотрел, в комментариях к статье на "хабре" это решение уже предлагали.
Да, все верно. Как видите, такое решение вполне можно предложить за 45 минут. Кстати, только что посмотрел, в комментариях к статье на "хабре" это решение уже предлагали.
В принципе да, наверное можно было придумать решение за 45 минут
Просто уж очень страшно звучит. А после прочтения решения с "масками", только укрепляешься во мнении о том, что "и правильно, что даже браться не стал!"
Но для любителей логических задач есть и такая прекрасная задача:
"
«Привет!» — «Привет!» — «Как дела?» — «Хорошо. Растут два сына, дошкольника». — «А сколько им лет?» — «Произведение их возрастов равно числу голубей около этой скамейки». — «Этой информации мне недостаточно!» — «Старший похож на мать». — «Вот теперь я знаю ответ на свой вопрос!»
"
Сколько лет детям?
Задача про трёх Богов (позиционируется как "самая сложная логическая задача")
Цитата:
Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Каждый вопрос задаётся только одному богу, но можно задавать одному богу более одного вопроса. Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja», причём неизвестно, какое слово обозначает «да», а какое «нет».
=================================== =================================== ==================
Только что решил с небольшой подсказкой. Долго мучился, но доволен
Сообщений: 6,621
Проживание: 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.
Эта сумма и будет номером монеты, которую нужно перевернуть.
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от Димыч
Но для любителей логических задач есть и такая прекрасная задача:
"
«Привет!» — «Привет!» — «Как дела?» — «Хорошо. Растут два сына, дошкольника». — «А сколько им лет?» — «Произведение их возрастов равно числу голубей около этой скамейки». — «Этой информации мне недостаточно!» — «Старший похож на мать». — «Вот теперь я знаю ответ на свой вопрос!»
"
Сколько лет детям?
Что в ней прекрасного?
Число голубей - N
N является квадратом (информация, что один из детей старше другого - помогла в решении, исключив вариант одинакового возраста).
Для дошкольников есть всего один вариант, N = 4. Старшему сыну 4 года, а младшему - 1.
Следующий квадрат - 9. Но старшему сыну не может быть 9 лет, ведь он дошкольник. 16 тоже не подходит, так как 8 лет - тоже уже школьный возраст.
Косяк в этой задаче в том, что не написано, одна ли мать у этих детей? Если дети от разных матерей, либо же один из них усыновлен, то вполне возможно, что обоим на самом деле по 2 года, но родились они в разные дни, и один из них все же старше другого.
Число голубей - N
N является квадратом (информация, что один из детей старше другого - помогла в решении, исключив вариант одинакового возраста).
Для дошкольников есть всего один вариант, N = 4. Старшему сыну 4 года, а младшему - 1.
Следующий квадрат - 9. Но старшему сыну не может быть 9 лет, ведь он дошкольник. 16 тоже не подходит, так как 8 лет - тоже уже школьный возраст.
Косяк в этой задаче в том, что не написано, одна ли мать у этих детей? Если дети от разных матерей, либо же один из них усыновлен, то вполне возможно, что обоим на самом деле по 2 года, но родились они в разные дни, и один из них все же старше другого.
Но думать при "решении" здесь вообще не нужно.
Почему квадратом? Почему N не может быть 2, 3, 5, 6?
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Почему квадратом? Почему N не может быть 2, 3, 5, 6?
Информация, что один из детей старше другого, могла помочь только, если был выбор между двумя ситуациями, одна из которых - близнецы (одинаковый возраст, произведение возрастов является квадратом какого-то числа).
Информация, что один из детей старше другого, могла помочь только, если был выбор между двумя ситуациями, одна из которых - близнецы (одинаковый возраст, произведение возрастов является квадратом какого-то числа).
Пример N=3, это произведение 3*1, и так далее. Квадрат не обязателен, поэтому вариантов больше.
Не сложная. Математика нужна. На решение ушла 1 минута. Никуда не смотрел, ваши решения не читал.
Обозначим все монеты как Mi, где i меняется от 0 до 63, а Mi принимает значения 0 (орел) или 1 (решка).
Вычислим сумму по модулю два (XOR) произведений позиций монет на их значения:
S - будет числом в диапазоне 0...63 и, таким образом, указывать на позицию монеты от 0 до 63.
Пусть P - номер позиции магической монеты. Вычислим сумму по модулю два S и P.
Эта сумма и будет номером монеты, которую нужно перевернуть.
Давай по другому.
Проведем 2 эксперимента. 1. надзиратель указывает клетку А4, 2. надзиратель указывает А5. Как будет изменяться твоя формула для этих экспериментов? Она же должна меняться.
Мне кажется вы не можете понять что именно надзиратель выбирает магическую монету. Если бы заключенный, то ясно что они могут договориться об одной формуле, и находить по ней число. Но для этого и формула не нужна, можно просто договориться какую клетку выбирать.
А в голову надзирателя вы не залезете, он может выбрать любой из 64 вариантов, поэтому договориться об одной формуле нереально. Переворачиванием одной монеты можно сократить область поиска, но не указать точное местоположение.
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Давай по другому.
Проведем 2 эксперимента. 1. надзиратель указывает клетку А4, 2. надзиратель указывает А5. Как будет изменяться твоя формула для этих экспериментов? Она же должна меняться.
Формула не меняется. Меняется ответ, полученный по формуле - сумма по модулю два (оператор XOR) чисел S и P. Она четко зависит от P и после переворачивания монеты с полученным порядковым номером S начинает указывать на P.
Сумма по модулю два обладает одним полезным свойством, которое здесь и используется.
Y xor X xor X = Y
Это свойство широко используется, например, в криптографии: в одноразовых блокнотах, в скрэмблерах. Очень близкой аналогией к данной задаче является задача разделения секрета между многими участниками. Именно поэтому эта задача с монетами решается без всяких усилий за минуту. Я много лет преподавал (в числе прочего) защиту информации в университете, так что более-менее ориентируюсь в соответствующей алгоритмической базе...
Формула не меняется. Меняется ответ, полученный по формуле - сумма по модулю два (оператор XOR) чисел S и P. Она четко зависит от P и после переворачивания монеты с полученным порядковым номером S начинает указывать на P.
Сумма по модулю два обладает одним полезным свойством, которое здесь и используется.
Y xor X xor X = Y
Это свойство широко используется, например, в криптографии: в одноразовых блокнотах, в скрэмблерах. Очень близкой аналогией к данной задаче является задача разделения секрета между многими участниками. Именно поэтому эта задача с монетами решается без всяких усилий за минуту. Я много лет преподавал (в числе прочего) защиту информации в университете, так что более-менее ориентируюсь в соответствующей алгоритмической базе...
Хорошо, не формула меняется, а значение переменной в формуле. Поэтому и ответ меняется. Логично?
То что вы математически можете описать доску это понятно. Но в сотый раз повторю. У нас есть 3 действующих лица в задаче. Как в театре. Есть 64 варианта ответа, один из которых случайным образом выбирает надзиратель. Первый заключенный не может передать второму как изменилось значение переменной в формуле. Тоже логично? Поэтому точного ответа быть в принципе не может.
Если есть формула, о использовании которой можно договориться и она даст правильный ответ на любую из 64 монет, то почему только 64 а не 1000000 например. И вообще, где была такая волшебная формула когда я женился?
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Как говорится, слив засчитан?
Какой слив? В условии задачи прямо говорится, что человек сказал, что имеющейся информации ему не достаточно.
Если бы там было три голубя, то он бы такого не мог сказать, так как в этой ситуации вариант всего один (3 и 1 год) и информации достаточно.
Для N=3 дополнительная информация не нужна. А по условию задачи она понадобилась.
Поэтому Ваш вариант отпадает, как противоречащий исходным данным задачи. Какой слив?
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от Одиссей
Только по модулю 64 все-таки.
Почему? Я имею ввиду именно по модулю 2. Числа там будут 6-ти битные (0..63). И над ними должна выполняться побитная операция XOR (сложение по модулю 2).
Сообщений: 6,621
Проживание: 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.
Ничего передавать второму заключенному от первого не нужно.
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от Димыч
Задача про трёх Богов (позиционируется как "самая сложная логическая задача")
Уважаю. Я не решил, хотя сразу было ясно, что нужно использовать отрицание отрицания для нивелирования лжи всегда лгущего бога, и неопределенности слов ja и da. Не хватило терпения подобрать правильный вопрос и продумать ветвление возможных ответов.
Эти "ja" и "da" порядком запутывают. Лучше бы боги отвечали Y и Z.
Сообщений: 2,821
Проживание: default city
Регистрация: 26-01-2010
Status: Offline
Цитата:
Сообщение от ponom
Почему? Я имею ввиду именно по модулю 2. Числа там будут 6-ти битные (0..63). И над ними должна выполняться побитная операция XOR (сложение по модулю 2).
Да это я уже запутался. В таком варианте решения нужно ксорить побитно.
Первый заключенный вычисляет в уме по формуле это значение 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 есть.
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от R60
Второй заключенный что бы вычислить S' по формуле должен знать какая монета перевернутая, то-есть D. По условиям задачи он этого не должен знать. Свою формулу посмотри, там D есть.
Нет, не должен. Он просто суммирует (мо модулю два) произведения позиций ВСЕХ монет на доске на значения монет. Среди этих монет на доске - и перевернутая. Сам факт переворачивания уже изменил значение суммы, вычисляемой по формуле так, чтобы она указывала на магическую монету.
В теме про НЛО цитата из Дугласа Адамса. Коротко: количество планет бесконечно. Часть планет обитаема, то есть обитаемых планет конечное число. Конечное число, поделенное на бесконечность, стремится к нулю. Следовательно, Вселенная необитаема.
А почему часть бесконечности обязательно конечна? Мне кажется, не обязательно.
В теме про НЛО цитата из Дугласа Адамса. Коротко: количество планет бесконечно. Часть планет обитаема, то есть обитаемых планет конечное число. Конечное число, поделенное на бесконечность, стремится к нулю. Следовательно, Вселенная необитаема.
А почему часть бесконечности обязательно конечна? Мне кажется, не обязательно.
Или?
Ну не... Часть от бесконечности может быть как конечным числом так и бесконечным.
Если ты имеешь в виду "несколько штук из бесконечности" - это одно дело, а если ты говоришь что-то типа "1% от бесконечности" - то это тоже будет бесконечность.
Выражение "часть из них обитаема" - больше подходит ко второй постановке вопроса, и тогда получается, что обитаемых планет бесконечное множество. Но, наверное, можно так сказать и для конечного числа планет, хотя тут по-хорошему надо говорить не "часть из них обитаема", а "из них Х планет обитаема"
Сообщений: 2,821
Проживание: default city
Регистрация: 26-01-2010
Status: Offline
Цитата:
Сообщение от sineemore
В теме про НЛО цитата из Дугласа Адамса. Коротко: количество планет бесконечно. Часть планет обитаема, то есть обитаемых планет конечное число. Конечное число, поделенное на бесконечность, стремится к нулю. Следовательно, Вселенная необитаема.
А почему часть бесконечности обязательно конечна? Мне кажется, не обязательно.
Или?
Не обязательно. Часть может быть и конечной и бесконечной и пустой.
Забавно, что, допустим, половина бесконечного множества может оказаться "равна" ему целиком. Например если взять все целые числа, а потом разделить их на две кучи - четные и нечетные, то каждая из этих куч будет равна изначальной общей куче.
Если копать дальше, например выяснять все ли бесконечные множества одинаково бесконечны, то быстро становится ясно что не все. Некоторые бесконечные бесконечнее других. Например бесконечное число действительных чисел "больше" бесконечного числа целых.
Если копать еще дальше, разбираться насколько бесконечными бывают бесконечные множества, то там возникает уже вполне взрослая математика (aka аксиоматическая теория множеств) со своими очень специфичными приколами (например парадоксы Рассела, а потом Банаха-Тарского).
Да, я поняла, что бесконечность, деленная на число - это тоже бесконечность. Совершенно какие-то парадоксальные свойства у нее (особенно для обывателя, меня )
Это можно себе и без математики представить даже, представляя себе эти планеты. Несмотря ведь на то, что необитаемых больше, чем обитаемых, обитаемых тоже потенциально бесконечно. То есть их и меньше, и равно необитаемым.
Если, разумеется, принять на веру то, что обитаемых меньше, может, на каком-то участке вселенной начинается очень высокая плотность именно обитаемых планет.
Не обязательно. Часть может быть и конечной и бесконечной и пустой.
Забавно, что, допустим, половина бесконечного множества может оказаться "равна" ему целиком. Например если взять все целые числа, а потом разделить их на две кучи - четные и нечетные, то каждая из этих куч будет равна изначальной общей куче.
С чего бы это вдруг?
Множество четных чисел составляет половину от множества целых чисел. Хотя и то и другое - бесконечность.
Ни разу не делили "бесконечность на бесконечность " что ли?
Да, я поняла, что бесконечность, деленная на число - это тоже бесконечность. Совершенно какие-то парадоксальные свойства у нее (особенно для обывателя, меня )
Бесконечность-то бесконечность... Но если количество всех целых чисел разделить на количество всех четных чисел, то будет два. Т.е. эти две бесконечности не равны друг другу конечно же
С чего бы это вдруг?
Множество четных чисел составляет половину от множества целых чисел. Хотя и то и другое - бесконечность.
Ни разу не делили "бесконечность на бесконечность " что ли?
Это, вроде, и есть пример с планетами, а также пример с % от бесконечности. Ну и разве Одиссей не то же самое сказал, что и ты?
Бесконечность-то бесконечность... Но если количество всех целых чисел разделить на количество всех четных чисел, то будет два. Т.е. эти две бесконечности не равны друг другу конечно же
Да, но они при этом все равно бесконечности.
А бесконечность вообще - это число? То есть да, конечно.
Но у него тогда свойства отличаются от свойств обычных чисел.
Сообщений: 2,821
Проживание: default city
Регистрация: 26-01-2010
Status: Offline
Цитата:
Сообщение от sineemore
Да, но они при этом все равно бесконечности.
А бесконечность вообще - это число? То есть да, конечно.
Но у него тогда свойства отличаются от свойств обычных чисел.
Нет, не число. В данном контексте это "кардинал" (или мощность множества).
Для кардиналов тоже можно ввести арифметические операции (сложение, деление итд), даже возведения в степень и логарифмы. Но это на пальцах уже не покажешь.
Цитата:
Это можно себе и без математики представить даже, представляя себе эти планеты. Несмотря ведь на то, что необитаемых больше, чем обитаемых, обитаемых тоже потенциально бесконечно. То есть их и меньше, и равно необитаемым.
Если, разумеется, принять на веру то, что обитаемых меньше, может, на каком-то участке вселенной начинается очень высокая плотность именно обитаемых планет.
Или у меня ошибка?
Из этого можно задачку сделать:
выдумайте такую числовую последовательность f(k), что
1. lim k->inf (k/f(k)) = 0
2. Для любого n существует m, такое что для всех k от m до m+n f(k+1)=f(k)+1
первое условие простыми словами - обитаемых планет очень мало
второе - если перебирать все планеты, то всегда можно найти любое заданное число обитаемых подряд.
Задачка вполне детская, решается моментально, выдумать такую последовательность можно.
Это, вроде, и есть пример с планетами, а также пример с % от бесконечности. Ну и разве Одиссей не то же самое сказал, что и ты?
Мне просто не понравился тезис о том, что бесконечности "равны".
Хотя сейчас я посмотрел ещё раз, и увидел, что "равны" там в кавычках написано. Тогда да, - "равны" (но не равны)
Нет, не число. В данном контексте это "кардинал" (или мощность множества).
Для кардиналов тоже можно ввести арифметические операции (сложение, деление итд), даже возведения в степень и логарифмы. Но это на пальцах уже не покажешь.
Из этого можно задачку сделать:
выдумайте такую числовую последовательность f(k), что
1. lim k->inf (k/f(k)) = 0
2. Для любого n существует m, такое что для всех k от m до m+n f(k+1)=f(k)+1
первое условие простыми словами - обитаемых планет очень мало
второе - если перебирать все планеты, то всегда можно найти любое заданное число обитаемых подряд.
Задачка вполне детская, решается моментально, выдумать такую последовательность можно.
Вы говорите на привычном математическом языке, дле меня он непривычен. Но вообще неплохо бы немножко, наверное, просветиться.
Забавно, какие вещи существуют в мире, о которых обыватель и не думает даже)
Интересно, а могут бесконечности быть равно по какому-то одному параметру, а по другому - не равны. Например, если представить две бесконечно длинных ленты, но одна шире другой. Такие вещи в математике рассматривают?
Нет, не число. В данном контексте это "кардинал" (или мощность множества).
Для кардиналов тоже можно ввести арифметические операции (сложение, деление итд), даже возведения в степень и логарифмы. Но это на пальцах уже не покажешь.
Это только если касается множеств, или вообще никогда не число?
Ведь с одной стороны, это - качество множества. С другой стороны - и число тоже, которое не имеет конца.
Сообщений: 2,821
Проживание: default city
Регистрация: 26-01-2010
Status: Offline
Цитата:
Сообщение от sineemore
Это только если касается множеств, или вообще никогда не число?
Ведь с одной стороны, это - качество множества. С другой стороны - и число тоже, которое не имеет конца.
Проще считать что никогда не число. С бесконечностью слишком много возни: не понятно как с ней выполнять обычные арифметические операции. А с "обычными" числами, вплоть до комплексных, все арифметические операции делаются просто замечательно.
Пример возни с бесконечностью как с числом есть в курсе матанализа Кудрявцева. (По мне так это упражнение для особо утонченных извращенцев).
Цитата:
Сообщение от sineemore
Интересно, а могут бесконечности быть равно по какому-то одному параметру, а по другому - не равны. Например, если представить две бесконечно длинных ленты, но одна шире другой. Такие вещи в математике рассматривают?
Конечно рассматривают. Конкретно с лентами - они любой ширины будут одинаково бесконечными (есть термин "равномощные"). И даже если ленту в плоскость растянуть - ничего не изменится.
А вот если из ленты сделать бесконечную рулетку с делениями, то бесконечное число делений будет "меньше" бесконечно длинны ленты. (Это тоже рассматривают.)
Упоминая логику обычно подразумевают использование дедуктивного метода для вывода умозаключений, в целом это неплохой метод для своей простоты, уверенное им владение позволяет выводить одну тавтологию из другой, а такое замечательное умение не навредит никому, кроме молодых красивых девушек.
Развитие метода было положено Аристотелем, который достаточно насмотрелся на Афинскую демократию в действии вплоть до захвата полиса более уважаемыми людьми, не мог Аристотель равнодушно смотреть на то, как естественные рабы благодаря численному преимуществу угнетают умных и богатых, и принялся писать труд "Риторика" для описания способов убеждения через речь, что включает в себя этос, пафос и логос. После смерти Македонского-младшего афиняне вспомнили хорошо проверенный способ борьбы с философами, недостойный доверия Аристотель решил не доводить дело до суда, но на всякий случай вскоре отравился артосом по другую сторону Эврипа. Обращение к рассуждению, используемый для выявления и устранения ошибочных аргументов и утверждений, логос, был выделен перипатетиками в отдельный труд «Органон», или «прибор» по-русски.
Труды Аристотеля не пропали зря, книги были переоткрыты и разрекламированы Цицероном, к несчастью, и он неблагополучно скончался из-за малодушия и предательства вольноотпущенного раба Филолога, с тех пор филология стала дисфемизмом герменевтики, а, напротив, логика Аристотеля была развита до уровня пропозициональной логики и далее до предикативной логики, которая является единственным верным методом верификации новых знаний в формальных науках: математике, философии и лингвистике. Дедуктивные умозаключения и есть применение предикативной логики, описываемой всего тремя простейшими аксиомами: ((a.b).c).(a.((a.c).a)) = c, где символ точки обозначает штрих Шеффера, универсальное подтверждение и экзистенциальное обобщение.
Краем глаза взглянув на «Органон» Аристотеля, Бэкон даже не задумался постесняться продемонстрировать публике свой собственный «Органон», а совершенно зря. Мало ли рождается людей, неспособных оперировать соритами, эпихейремами и энтимемами, но индуктивная логика хоть и выходит за рамки idem per idem, но годится лишь для подтверждения теоремы Байеса и не более того, даже тавтологию не вывести в её рамках. К счастью, Пирс-младший формально описал систему абдуктивных логических рассуждений, которая качественно лучше дедуктивной и индуктивной в смысле практического применения и созидательного описания законов нашего прекрасного мира.
И всё-таки, как же дедукция? Этот красивый в простоте метод постоянно царапает нашу культуру, воображение и самомнение, онтологические доказательства существования Бога следуют одно за другим, и теперь современно их делать в модальной логике, кто-то вообще не понимает область применимости дедуктивных рассуждений, ну а мне ближе всего мудрые слова Ревущего Льва:
Цитата:
So from a logical point of view
Always love a woman uglier than you
Сообщений: 6,621
Проживание: Tampere
Регистрация: 13-04-2016
Status: Offline
Цитата:
Сообщение от sineemore
Это цитата из юмористической книжки. И он не доказывал именно это .
Стремный юмор - спорное утверждение, затем псевдологическая связка "то есть" (хотя на самом деле совсем не "то есть"), затем неверный вывод.
Такие шутки можно клепать десятками в день. Например:
Количество возможных звуков - бесконечно. Часть звуков представляют собой человеческую речь, то есть число таких звуков - конечно. Следовательно вероятность услышать человеческую речь равна конечной величине, деленной на бесконечную, а проще говоря нулю.
Стремный юмор - спорное утверждение, затем псевдологическая связка "то есть" (хотя на самом деле совсем не "то есть"), затем неверный вывод.
Такие шутки можно клепать десятками в день. Например:
Количество возможных звуков - бесконечно. Часть звуков представляют собой человеческую речь, то есть число таких звуков - конечно. Следовательно вероятность услышать человеческую речь равна конечной величине, деленной на бесконечную, а проще говоря нулю.
"Автостопом по галактике " это. На мой взгляд чудесный образец бредового юмора в сочетании с глубокими идеями.
Смысл этой шутки просто в ее абсурдности