задача дня-17

[falcao]

Не так давно встретилась задача -- скорее всего, она известная. Слишком уж естественная у неё формулировка. В таких случаях кому-то может быть известно "авторское" решение, которое мне было бы интересно узнать

Comments

[mathreader]

Это соображение уже используется в оценке n(n-1)/2, без него было бы (n+1)n/2. Действительно, чтобы установить, к какому замку подходит первый ключ, мы перепробуем n-1 замков (в худшем случае). В n-й замок первый ключ совать уже не обязательно, как вы заметили, мы его вычислили и так. Получается n-1 проб для первого ключа, а не n. В результате имеем (n-1) + (n-2) + ... + 1 = n(n-1)/2.

[yuv_k]

https://youtu.be/wWQ9YdreY9c - интересный вариант вашей задачи - но это для варианта без обратной связи - т.е. если бы проверку нового ключа каждый раз начинали не зная предыдущих результатов.

[falcao]

Ну, тут аналогия всё-таки очень далёкая. Особенно это касается сути решения. То есть математический "механизм" там и там сильно отличается.

[tetrod]

Прошу прощения. Отступление от темы.
85 = 36 + 49= 4 + 81
Существуют ли натуральные, которые можно представить суммой двух квадратов тремя, четырьмя и более способами?
Например, указать наименьшее натуральное, которое можно представить в виде суммы двух квадратов 5-ю способами. Или оценить его. Или доказать отсутствие такого числа. Пока не вижу никаких подходов.

[falcao]

Эта теория хорошо изучена, число способов представления может быть сколь угодно велико. Есть готовая формула, которая даёт это число. См. популярную статью в "Кванте":

http://kvant.mccme.ru/pdf/1999/03/kv0399senderov.pdf

Ответ там даётся в Теореме 10. Если не ошибаюсь, то для числа 65^2=4225 имеется 5 способов, включая 0^2+65^2, и оно будет наименьшим. Если брать только сумму квадратов двух натуральных, то наименьшим будет 5525, для которого не менее 5 способов (их будет 6). Для 8125=5^4*13 способов ровно 5.

[tetrod]

Премного Вам благодарен!

[cmt96]

Фразы "для каждого исполнения алгоритма" и "для каждого набора входных данных" я буду полагать синонимичными

[cmt96]

Мне бы хотелось задать вопрос на другую тему. Вы когда-то говорили, что у Вас есть рассуждение: в чём недостаток идеи разделения властей на три ветви (законодательная, исполнительная, судебная), вот такой идеократии (в том смысле, что предполагается, что правят не люди, а идеи; это ещё именуют, кажется, "rule of law"). Мне было бы любопытно знать, какие соображения Вы сделали на эту тему. То, что приходит в голову мне, - чисто техническое: непонятно, каким образом судебная власть может быть независимой, если верховные (тем более - "обычные") судьи не избираются и не назначаются изнутри корпорации, а назначаются чиновниками с других ветвей.

[falcao]

У меня был давний пост на тему "разделения властей", вот ссылка:

https://falcao.livejournal.com/22493.html

Написан он очень давно, но к сказанному (в том числе в комментариях) мне почти нечего добавить.

[cmt96]

"Access is denied."
Что ж, всё равно спасибо.

[stierliz]

Прощайте, Виктор. Спасибо за общение.