elis

The Show Must Go On

7.17 КБ

Mas sei
Que uma dor assim pungente
Não há de ser inutilmente
A esperança dança
Na corda bamba de sombrinha
E em cada passo dessa linha
Pode se machucar
Azar
A esperança equilibrista
Sabe que o show de todo artista
Tem que continuar
  • Current Music
    Elis Regina -- O Bêbado e A Equilibrista
тигр

задача дня-12

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

Имеется стандартный игральный кубик. Мы бросаем его несколько раз, и все выпавшие очки суммируем. Цель игры -- набрать заданное число очков, равное n. Если в какой-то момент мы его набрали, это означает выигрыш. Если превысили, то проиграли.

а) При каком значении n шансы на выигрыш максимальны?

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

Если бы на кубике выпадали всего два значения 1 и 2, то ответ на пункт б) достаточно прост. Но уже для значений 1, 2, 3 закономерность перестаёт быть понятной.

Комментарии не скрываются.
тигр

о невычислимых функциях

Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля".

Что такое невычислимая функция? Это такая функция, которую нельзя вычислить при помощи алгоритма, то есть невозможно написать программу для её вычисления. Хотя достаточно легко доказать, что невычислимые функции существуют, не так просто предъявить конкретный пример, а тем более интересный пример. В посте по ссылке такой пример был приведён, но описанная там функция Busy Beaver слишком уж быстро растёт. Мы её слабо себе представляем, зная только то, что её значения -- какие-то огромные числа. Здесь я хочу привести другой пример невычислимой функции, которая растёт очень медленно, и поведение которой мы можем себе представить намного лучше. Дополнительным соображением, побудившим меня написать этот текст, является связь с известными логическими парадоксами, а этой проблематики я в прошлом частенько касался.

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

Итак, пусть нам дано число, и надо написать программу, которая его распечатывает, останавливаясь при этом. Будем считать, что для печати у нас есть команда print. Тогда, чтобы распечатать число, скажем, 2021, достаточно написать команду print(2021). Программа будет готова.

Ясно, что бывают числа, распечатывать которые таким способом нежелательно. Допустим, вместо 2021 у нас есть очень большое число типа 100...0 с миллионом нулей на конце. Мы не хотим составлять программу из миллиона символов. Тогда можно распечатать нули в цикле. Примерно так:

print(1);
for i:=1 to 1000000 do print(0)

Такая программа напечатает то, что мы хотим, и символов в ней не миллион, а меньше пятидесяти.

Обозначим то число, которое мы хотим напечатать, через n. Самый простой способ написания программы требует порядка lg n + C символов, где C -- небольшая константа. В тех случаях, когда число является "случайным", то есть состоит из случайно выбираемых цифр, скорее всего, нет принципиально другого способа распечатать число кроме как указать его явно. Однако зачастую оказывается возможным поступить как-то более хитро. Один такой пример мы привели. Другие примеры могут возникнуть на следующей основе.
Collapse )
тигр

задача дня-11

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

Рассмотрим числа 1, 2, 3. Их сумма равна 6, и произведение также равно 6. Легко проверить, что никаких других целых чисел с такими свойствами больше нет. А можно ли найти три дробных (положительных рациональных) числа, у которых и сумма, и произведение равны 6?

В идеале, хотелось бы описать все решения системы a+b+c=6, abc=6 в рациональных числах.

Комменты скринятся.

UPD 01.01.21 Раскрыл основные комментарии.
тигр

задача дня -- 10

Давненько уже постов не помещал! А тут интересная головоломка попалась.

Даны натуральные числа от 1 до 2018. Их нужно разбить на пары, и числа в каждой паре сложить. Требуется, чтобы произведение полученных 1009 чисел было точной четвёртой степенью.

Задача хороша тем, что её можно решать, условно говоря, "в трамвае". Если бы чисел было 2016, то решение совсем простое: разбиваем по принципу 1+2016, 2+2015, ... , и получаем 1008 одинаковых чисел. Их произведение, конечно, будет 4-й степенью натурального числа. А вот для 2018 решение далеко не очевидное. Но оно есть.

Забавно, что мой предыдущий пост из этой серии имел место два года (и один день) назад.

Комменты до времени "скринятся".

UPD (29.12.18) Верные решения (причём весьма разнообразные) предоставили relf, roman_rogalyov и fiviol.

UPD (03.01.19) Раскрываю все комментарии. Принципы решения здесь были самые разнообразные. Наиболее эффектными мне показались решения, в которых для первых нескольких чисел осуществляется какая-то нетривиальная группировка (то есть не по принципу "первый с последним"), и всё остальное под неё "подгоняется".

Всем спасибо за участие, и с наступившим Новым годом!
pequim1

задача дня -- 9

Снова очень давно ничего не писал. А сейчас как бы "грех" это не сделать, поскольку я вышел на где-то трёхнедельные "мини-каникулы".

Вот интересная головоломка, и она как бы "для всех", то есть не требует никаких специальных знаний. Требуется расположить по окружности перестановку чисел от 1 до 32 так, чтобы любые два стоящие рядом числа в сумме давали точный квадрат. Для большей ясности заметим, что в данном случае значениями таких сумм могут быть 4, 9, 16, 25, 36, 49.

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

Комментарии я временно прячу под "скрин". Там можно приводить не только сам пример, но и способ его получения -- особенно если они связаны с "вынужденными" рассуждениями, а не с "разветвлённым" перебором вариантов.

UPD (31.12.16) Открываю комментарии. Решения в целом порадовали. В нескольких комментариях изложен подробный ход мысли без "разветвлений", откуда единственность решения прямо следует. Очень приятно было также увидеть рассуждения наиболее "близкородственно" мыслящих людей, то есть филологов :)

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

Всех с наступающим!
тигр

задача дня -- 8

Давным-давно ничего уже здесь не писал. Октябрь у меня традиционно является "авральным" месяцем, а в этом году он был таковым вдвойне. Нужно было в сжатые сроки составить задачи сразу к двум местным олимпиадам. Но я вроде как справился (несмотря на неудачно составленное расписание в этом семестре), так что теперь можно и в ЖЖ заглянуть. За время моего "бездействия" так называемый "социальный капитал" журнала упал до отметки "ниже 10". Что, впрочем, когда-то уже было. Но это я так, чисто для информации. А теперь собственно задача.

Она в этот раз не олимпиадная, не из области "занимательного" наподобие "головоломок", поэтому, скорее всего, заинтересует меньший круг читателей. Это упражнение по матанализу, не слишком трудное, но мне понравилось условие. Вот оно.

Дан сходящийся числовой ряд a_1+a_2+...+a_n+... . Обязательно ли сходится ряд из синусов, то есть sin(a_1)+sin(a_2)+...+sin(a_n)+... ?

Замечу на всякий случай, что для знакопостоянных рядов эта задача тривиальна. А как обстоит дело в общем случае?

Думаю, что многие эту задачу решат, и в данном случае комментарии я до времени буду скрывать. Тем более, что интересно было бы увидеть разные способы решения.

UPD (25.12.16) Комментарии я раскрыл (на самом деле, это давно надо было сделать). Спасибо всем, кто участвовал в обсуждениях. Предложенные здесь способы решения основаны примерно на одних и тех же соображениях. К тому решению, которым я располагал, ближе всего оказались рассуждения mikev.
тигр

задача дня -- 7

Вот неплохая, на мой взгляд, задача.

Рассматриваются возрастающие арифметические прогрессии с натуральными членами, не превосходящими N. Требуется, чтобы все члены такой прогрессии были попарно взаимно просты. Какова максимально возможная длина такой последовательности

а) при N=100

б) при N=1000?

Можно исследовать и другие значения N при желании.

Комментарии я не прячу.
тигр

задача дня -- 6

Хочу предложить задачу достаточно "традиционную" -- по сути дела, школьную. Особенность её в том, что поначалу кажется, будто данных для решения в ней не хватает. Когда я сам решал, но сначала так и подумал, так как предложена она была в чьём-то пересказе, причём даже двойном. Но потом выяснилось, что с условием всё в порядке.

Числовые данные я несколько изменил. Комментарии прятать не буду -- как по причине специфики задачи (решать её можно очень многими способами -- как при помощи формул, так и без них), так и потому, что далее я буду несколько дней вне Интернета. А вот само условие.

Из пункта А в пункт В ровно в 10:00 выехал автобус. Проехав половину пути, водитель увидел едущего навстречу велосипедиста. После того, как автобус приехал в пункт В, оттуда сразу же в направлении пункта А выехал мотоциклист. Он догнал велосипедиста в тот момент, когда до пункта А оставалась одна четверть пути. В какое время мотоциклист приехал в пункт А, если известно, что велосипедист прибыл туда в 15:00?

Соотношения скоростей не даны, но скорость каждого транспортного средства считается постоянной.
тигр

задача дня -- 5

Хочу предложить сразу две задачи: обе они комбинаторно-переборного типа.

Первую задачу когда-то предлагали на олимпиаде школьников. Поэтому просьба решать её только такими средствами. То есть не применять какую-либо "высокую" технику наподобие леммы Бернсайда. Компьютер привлекать в принципе можно, но чисто для себя (скажем, для контроля правильности ответа). Вот условие.

Требуется раскрасить грани куба в 4 цвета. Каждый из цветов должен быть использован; все грани монохромны. Раскраски, отличающиеся вращениями куба как "твёрдого тела", не различаются. Сколько имеется таких способов раскраски?

Вторая задача как бы дополнительная -- в ней мне не известен какой-либо "цивилизованный" способ подсчёта. То есть там можно и компьютер использовать, хотя программа пишется легко, работает быстро, и нахождение ответа не составляет проблемы. Если кто найдёт ответ чисто вручную -- совсем хорошо.

Сколькими способами можно заполнить клетки таблицы 4x4 нулями и единицами, чтобы никакие две единицы не находились в соседних по стороне клетках?

Комменты открыты. Я буду по возможности за ними следить, и если ответ будет дан верный, то я на время его буду скрывать.

Успехов!

UPD (03.07.16) Комменты с решениями раскрыты. Всем спасибо за участие!