Вспомнилась старая добрая задачка. Формулировок много, одна из них такая:
К королю пришли два мудреца. Он загадал 2 целых числа, каждое больше 1 и меньше 100. Первому мудрецу сообщил их произведение, второму — сумму. И спрашивает — знаете?
1-й мудрец: не знаю.
2-й: я знал, что ты не знаешь.
1-й: тогда я знаю.
2-й: тогда я тоже знаю.
Вопрос: какие числа загадал король?
Re: Задача с сингапурской олимпиады для школьников
Слишком уж стандартная задача на последовательное исключение вариантов, если честно.
Ответ
Первая фраза исключает май и июнь, так как именно в них есть уникальные числа.
Вторая исключает 14 число, так как только оно присутствует в обоих оставшихся месяцах.
Третья означает, что ответ — 16 июля, так как в ином случае Альберт не смог бы однозначно назвать дату рождения.
A>К королю пришли два мудреца. Он загадал 2 целых числа, каждое больше 1 и меньше 100. Первому мудрецу сообщил их произведение, второму — сумму. И спрашивает — знаете?
A>Вопрос: какие числа загадал король?
Хорошо подходят 6 и 2. Только мне тут совсем не очевидно что это единственные подходящие числа.
Такая задача решается только перебором или есть что то из теории чисел что тут может помочь?
Re[3]: Задача с сингапурской олимпиады для школьников
A>>К королю пришли два мудреца. Он загадал 2 целых числа, каждое больше 1 и меньше 100. Первому мудрецу сообщил их произведение, второму — сумму. И спрашивает — знаете?
A>>Вопрос: какие числа загадал король?
J>Хорошо подходят 6 и 2.
Ммм. Первой реплике эти числа удовлетворяют, а вот второй реплике — нет.
J>Только мне тут совсем не очевидно что это единственные подходящие числа.
Ответ в этой задаче единственный. И этим она и примечательна
J>Такая задача решается только перебором или есть что то из теории чисел что тут может помочь?
Я решал перебором на бумажке (точнее, в Excel, закрашивая клеточки с числами в разные цвета)
Времени отняло уйму, но было очень интересно!
Re[4]: Задача с сингапурской олимпиады для школьников
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, johny5, Вы писали:
A>>>
A>>>К королю пришли два мудреца. Он загадал 2 целых числа, каждое больше 1 и меньше 100. Первому мудрецу сообщил их произведение, второму — сумму. И спрашивает — знаете?
A>>>Вопрос: какие числа загадал король?
J>>Хорошо подходят 6 и 2. A>Ммм. Первой реплике эти числа удовлетворяют, а вот второй реплике — нет.
Сорри, сам понял что неверно, поторопился. Второй должен быть уверен что все возможные комбинации приведут к неоднозначности в 1м варианте.
4 и 13?
J>>Только мне тут совсем не очевидно что это единственные подходящие числа. A>Ответ в этой задаче единственный. И этим она и примечательна
A>Я решал перебором на бумажке (точнее, в Excel, закрашивая клеточки с числами в разные цвета) A>Времени отняло уйму, но было очень интересно!
Вы все 200 сумм перебрали? С ростом суммы вероятность конечно сильно падает что ещё такая комбинация попадётся, но всё таки строгое доказательство не помешало бы, иначе задача не может считаться решённой.
Re[5]: Задача с сингапурской олимпиады для школьников
A>>>>К королю пришли два мудреца. Он загадал 2 целых числа, каждое больше 1 и меньше 100. Первому мудрецу сообщил их произведение, второму — сумму. И спрашивает — знаете?
A>>>>Вопрос: какие числа загадал король?
J>>>Хорошо подходят 6 и 2. A>>Ммм. Первой реплике эти числа удовлетворяют, а вот второй реплике — нет.
J>Сорри, сам понял что неверно, поторопился. Второй должен быть уверен что все возможные комбинации приведут к неоднозначности в 1м варианте. J>4 и 13?
Насколько я помню, да.
J>>>Только мне тут совсем не очевидно что это единственные подходящие числа. A>>Ответ в этой задаче единственный. И этим она и примечательна
A>>Я решал перебором на бумажке (точнее, в Excel, закрашивая клеточки с числами в разные цвета) A>>Времени отняло уйму, но было очень интересно!
J>Вы все 200 сумм перебрали? С ростом суммы вероятность конечно сильно падает что ещё такая комбинация попадётся, но всё таки строгое доказательство не помешало бы, иначе задача не может считаться решённой.
Решал много лет назад, вроде бы всё честно тогда перебрал — решение единственным было.
Re[6]: Задача с сингапурской олимпиады для школьников
Здравствуйте, andy1618, Вы писали:
A>>>Я решал перебором на бумажке (точнее, в Excel, закрашивая клеточки с числами в разные цвета) A>>>Времени отняло уйму, но было очень интересно!
J>>Вы все 200 сумм перебрали? С ростом суммы вероятность конечно сильно падает что ещё такая комбинация попадётся, но всё таки строгое доказательство не помешало бы, иначе задача не может считаться решённой.
A>Решал много лет назад, вроде бы всё честно тогда перебрал — решение единственным было.
Я проверил для 4 и 19, тоже подходят.
Удивительное "совпадение" что один из членов всегда 4ре а второй — простое число. Правда не все простые подходят.
Re[3]: Задача с сингапурской олимпиады для школьников
import math
def dividers(num):
rez = []
divider = 2
while num != 1:
if num % divider == 0:
rez = rez + [divider]
num = num / divider
else:
divider = divider + 1
return rez
for sum in range(4, 199):
a_max = math.floor(sum/2)
mayBeObvious = False
a_candidates = []
for a in range(2, a_max+1):
b = sum - a
commonDividers = dividers(a) + dividers(b)
if len(set(commonDividers)) == 2 and len(commonDividers) == 3:
# print(commonDividers)
a_candidates = a_candidates + [a]
if len(commonDividers) <= 2:
mayBeObvious = True
break
if mayBeObvious == False and len(a_candidates) == 1:
print(a_candidates[0], sum - a_candidates[0])
Re[2]: Задача с сингапурской олимпиады для школьников
A>Вспомнилась старая добрая задачка. Формулировок много, одна из них такая: A>К королю пришли два мудреца. Он загадал 2 целых числа, каждое больше 1 и меньше 100. Первому мудрецу сообщил их произведение, второму — сумму. И спрашивает — знаете?
