Математика

Интересный вопрос

Оригинально это задача была представлена на конкурсе им. Савина в журнале Квант #4 в 2006 году. В такой формулировке:

В ряд выложены 28 одинаковых по внешнему виду монет. Среди них есть две рядом лежащие фальшивые монеты — более тяжёлые, чем настоящие. Можно ли за 3 взвешивания на чашечных весах без гирь найти фальшивые монеты?

Решения в интернете я не нашёл, поэтому приведу своё решение. Любая задача на взвешивание монет на каждом шаге даёт 3 варианта: тяжелее, легче или равны. В самом сбалансированном случае это означает принадлежность искомого объекта к одной из кучек, большая из которых не может быть меньше, чем 1/3 от размера исходного числа монет. Тогда поиск одной монеты за 3 взвешивания осуществим только для 3^3=27 монет (или меньше).

В нашей постановке задачи есть дополнительная информация о том, что пара монет лежит рядом, поэтому мы будем искать позицию пары. Таких позиций будет ровно 27 (1-2, 2-3, ..., 27-28) -- значит у нас всё может получиться!

Разделим монеты на 3 кучки по 10 штук с перекрытием в одну монету: 1-10, 10-19, 19-28, и попробуем определить принадлежность нашей пары к одной из этих кучек. Для этого взвесим на весах первые 9 монет (1-9) и последние 9 (20-28). Если они равны, в них нет фальшивых монет, а обе тяжёлые монеты принадлежат средней кучек из 10 монет (10-19). Если одна из них окажется тяжелее, это значит, что 1 или 2 тяжёлые монеты попали в неё. Мы знаем, что тяжёлые монеты ходят парами, поэтому мы гарантируем, что обе попадут в "расширенную" кучку (1-10) или (19-28).

Теперь у нас есть кучка из 10 монет, в которой прячется фальшивая пара. Повторим процедуру для 3 кучек размером 4 монеты с перекрытием: 1-4, 4-7, 7-10. Взвесим 1-3 и 8-10 и найдём четвёрку, в которой скрывается наша пара монет, по тому же принципу.

Последний шаг - найти пару среди 4 монет. Взвесим крайние 1 и 4. Если равны - пара посередине, если 1я тяжелее, то фальшивые 1-2, если легче - 3-4.

Как максимально корректно выстроить взаимосвязь между объектами по имеющимся у них признакам, при этом расчеты не должны быть чрезмерными? — 1 ответ

Имеем некоторое N условных абстрактных объектов. N - конечное значение и не чрезмерно большое. Объекты появляются в поле нашего зрения в произвольные моменты времени и имеют один дополнительный признак в каждый момент появления. Признаки могут повторяться, могут все время быть одинаковыми для какого-то объекта, но могут и не быть таковыми. Количество признаков - конечное значение, но, теоретически, большее чем количество объектов. Условно можно составить такую таблицу: Объект_1 | дата\время появления_1 | Признак_1 Объект_1 | дата\время появления_2 | Признак_3 Объект_2 | дата\время появления_2 | Признак_4 Объект_3 | дата\время появления_2 | Признак_3 Объект_N | дата\время появления_Z | Признак_X (Объект_1 и Объект_3 в этом примере можно считать связанными с большой долей вероятности) Требуется установить наиболее устойчивые взаимосвязи между ОБЪЕКТАМИ, на основании ПРИЗНАКОВ. При этом нужно учитывать тот факт, что чем больше временное окно между появлениями двух объектов с одинаковыми признаками, тем менее вероятна связь между ними. Так же нужно учитывать тот факт, что один из объектов может в один и тот же временной интервал, условно, допустим, месяц, может появиться 300 раз, а другой объект - всего 1 раз. Естественно, связь между такими объектами весьма сомнительна, и может быть случайностью. Приветствуются любые идеи, но чем менее они ресурсоемки в плане нагрузки на вычислительную систему, тем лучше.
2 человека оценили этот вопрос
Интересный вопрос

Идея 1.

Дискретные признаки все вывести в one-hot encoding, числовые отнормировать, время тоже. Получим сколько-то мерный вектор для каждого объекта, при этом каждому признаку прикручено время. И дальше можно считать попарные разности векторов (евклидово расстояние, L1-норма), но с поправкой на временное расстояние. Условно (v1[i] - v2[i])^2 * (1 - (t1[i] - t2[i]))^2. Можно также натравить на эти векторы кластеризацию, например DBSCAN.

Идея 2.

Итерационные процесс - собрать объекты в мешки по признакам, а затем прореживать "мешки" в соответствии с эвристическим правилами (если вы имеете какое-то понимание о том, что значат те или иные признаки).

Интересный вопрос
Главный редактор издания «Популярный университет», химик по образованию, продвигаю массы в науку!popuni.ru

Очень просто:
1) Сначала нужно убедиться, что раскладываемое число делится не только на 1 и на само себя. В противном случае это будет простое число, которое само же и является своим множителем.
2) После того, как мы поняли, что число делится не только на 1 и на само себя, нужно разделить его на самое маленькое простое число, которое является его делителем. Например, если взять число 12, то самым маленьким простым числом для него будет 2. Смотрим остаток их деления: 12/2=6. Продолжаем те же действия, но уже с цифрой 6 – для 6 наименьшим простым числом будет тоже 2: 6/2=3. Продолжать такие действия нужно, пока в конце мы не получим простое число (в нашем случае – 3). Таким образом, разложение будет выглядеть так: 12=2*2*3.

Интересный вопрос
Редактор, переводчик книг по математике. zen.yandex.ru/maths

Сначала разберемся с функцией Римана.

Посмотрим на такую лесенку:

лесенка.jpg

В ней высота ступенек постепенно уменьшается. Первая ступенька высоты 1, вторая – ½, третья – 1/3 и так далее.

Эта лесенка ограничена по высоте или пробьет потолок любой высоты? На этот вопрос ответили братья Бернулли в конце XVII века. Так начались приключения гипотезы Римана.

Высота первых n ступенек лесенки равна

ряд.jpg

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

Математики решили попробовать такие ступеньки, высота которых уменьшается побыстрее. Первая ступенька высоты 1, вторая – (½)^2=1/4, третья – (1/3)^2=1/9 и так далее:

лесенка2.jpg

И да, такая лестница уже ограничена. Если установить потолок на высоте (π^2)/6≈1,645, то лестница подойдет к нему сколь угодно близко, но не коснется его. Эта высота есть сумма обратных квадратов:

ряд2.JPG

Первым эту сумму вычислил Леонард Эйлер. Появление числа π в ответе выглядит удивительно, ведь ничего кругленького в этой сумме не наблюдается. Потом Эйлер решил вычислить сумму обратных кубов:

ряд3.JPG

Но вот это уже не вышло. Не вышло не только у Эйлера, но и у следующих поколений математиков. Найти сумму обратных кубов – знаменитая нерешенная задача математики (хотя и не самая важная). Если ты ее решишь, то прославишься (хотя и не очень).

А теперь посмотрим на важнейший прием в математике: обобщай и обозначай.

Рассмотрим суммы всех степеней сразу, вот так:

ряд4.JPG

Мы уже знаем, что ζ(1) не имеет смысла, что ζ(2)=π^2/6, и что ζ(3) мы вычислять не умеем. Наш соотечественник Пафнутий Львович Чебышев рассмотрел функцию ζ(s), когда s принимает не только натуральные значения 1, 2, 3, … , но и действительные значения. На этом пути Чебышев смог получить серьезные результаты о распределении простых чисел.

Чебышев не любил комплексные и мнимые числа, считал их слишком далекими от реальности. А жаль. Если бы Чебышев разрешил переменной s принимать комплексные значения, то сейчас мы бы с вами изучали функцию Чебышева и проверяли гипотезу Чебышева.

Но гениальную догадку сделал именно Риман: он впустил в игру комплексные числа. Функция ζ(s), где s – комплексное число, называется функцией Римана.

Гипотеза Римана описывает поведение этой функции, а именно, где находятся ее нули (во всяком случае, самые интересные). Видимо, все они находятся на одной прямой – такой, что действительная часть s равна ½. Это числа вроде s=1/2+iz. Не все эти числа являются нулями дзета-функции, но гипотеза говорит, что все нетривиальные нули находятся среди таких чисел.

Существует ли алгоритм упрощения большого числа до нескольких простых операции, с меньшим количеством символов? — 1 ответ

Возьмем к примеру число 1020. Его можно упростить, таким образом 10^2+20. Но это короткое число. Так что возьмем для примера число чуть побольше: 10 000 002 985 984 (14 символов) Его можно упростить так: 10^13 + 12^6 (10 символов). Но это всё ещё маленькое число. В самой задаче присутствует число из 30↑30 символов в 36'чной системе счисления. Есть ли какой-нибудь алгоритм, который позволит упростить любое такое большое число, до простых математических операции, хотя бы из 10↑10 символов? В условии математических операциях можно использовать любые простые операции, не требующего больших ресурсов для вычисления или из класса NP. К примеру, можно использовать: плюс, минус, деление, возведение в степень, стрелочные нотации Кнута, и др. И ещё можно использовать любую систему счисления, вплоть до 36'чной. Можно также разделить число на несколько частей, чтобы упростить их. И при вычислении этих чисел, они обратно встают друг за другом. Сам алгоритм упрощения тоже должен быть простым и не быть из класса NP. Так вот, существует ли такой алгоритм, которым можно упростить любое большое число до простых мат. операции с самым минимальным количеством символов?
Интересный вопрос

Ответа не знаю, но давайте порассуждаем вместе.

1) Снижать число символов могут унарные функции, которые растут быстрее линейных по отношению к аргументу (например, факториал).

2) Функция двух и более аргументов должна рости быстрее, чем умножение: любая запись умножения длиннее, чем результат (степени, стрелки Кнута, функция Аккермана, ...).

При этом, как вы сами показали, ни от сложений, ни от умножений отказаться нельзя. Вряд ли для числа 2^65536+6 можно придумать запись, короче чем A(4,2)+9 или 2↑↑5+6 .

Таким образом, есть функции, "ухудшающие" запись, есть "улучшающие". Результат - это композиция этих функций. Дальше исключтельно рассуждения, не подтверждённые доказательствами :) Если отказаться от применения ухудщающих операций мы не можем, то пространство поиска у нас не выпуклое (иногда лучше декомпозировать число как сумму, чтобы потому получить что-то типа 2↑↑↑↑5+8^13). Кажется, поэтому ни динамика, ни DnC, ни жадный алгоритм нам не помогут. Скорее всего решение будет вполне себе экспоненциальным. Например, обход по дереву операций с отсечениями. Кажется, что задав изначальный набор унарных и бинарных операций, такой метод написать совсем несложно, но увы, это будет экспонента.

Интересный вопрос
Редактор, переводчик книг по математике. zen.yandex.ru/maths

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

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

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

Все-таки, мне представляется, что вычисление все большего числа цифр числа π -- проявление обычного для человека стремления достичь большего. Мы встречаем его не только в математике: пробежать быстрее всех, подняться в горы выше всех, набрать лайков и подписчиков больше всех, найти цифр больше всех...

О смысле числа π, истории его вычисления и нерешенных задачах, связанных с ним, рекомендую коротенькую и емкую брошюру А.В.Жукова "О числе π"

Интересный вопрос
Редактор, переводчик книг по математике. zen.yandex.ru/maths

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

А в математике критерий правильности или неправильности иной: доказательство. Утверждение считают истинным, верным, только если оно доказано. А неверным -- если противоречит базовым аксиомам или их следствиям.

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

Математики давно предвидели такую неприятность. В начале XX века они тщательно проработали основания математики: определили, какими свойствами должны обладать системы аксиом, и проверили, что существующие системы непротиворечивы.

В будущем возможен некий кризис оснований математики, если требования к строгости и обоснованиям возрастут. Тогда математики еще поработают в основаниях своей науки. Они не станут перестраивать все здание, а укрепят фундамент. Они уже не раз это делали, и в другой раз тоже справятся. Можно спать спокойно.

Интересный вопрос
Редактор, переводчик книг по математике. zen.yandex.ru/maths

Сначала разберемся, что такое "делить". Скажем, у мамы трое детей, и она желает разделить между ними 12 слив. Им необязательно уметь считать для этого. Можно усадить детей в круг и раздавать им по кругу сливы по одной, пока они не кончатся. О чудо! Всем хватит поровну!

В задачах посложнее так делить не получится. В математике иногда приходится делить на 3,6 или на корень из 3 или даже на π. Тут уж деток в кружок не посадишь. Какой же смысл вкладывают тогда в слово "разделить"?

Что значит "разделить 12 на 3"? Это значит подобрать такое число х, которое даст 12, будучи умноженным на 3. Мы хорошо знаем, что это число 4. Разделить 10,8 на 3,6 -- значит подобрать число х такое, что 3,6*х=10,8.

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

Угадай, на какое число надо умножить 4, чтобы получить 20? Если ты угадал, значит, смог разделить 20 на 4 и получить 5.

Угадай, на какое число надо умножить 10, чтобы получить 130? Если ты угадал, значит, смог разделить 130 на 10 и получить 13.

А теперь внимание: угадай, на какое число надо умножить 0, чтобы получить 4? Если ты угадал, то смог разделить 4 на 0.

Но вот незадача -- угадать не получится. И не потому, что ты плохо старался. Дело в том, что на какое число не умножай 0, все равно получится 0. А вовсе не 4, не 312 и не 2019. Мы не можем разделить на 0 не потому, что нехорошие люди не разрешают, не потому, что плохо старались, а потому что такое деление означает бессмыслицу вроде 0*15=2019.

По моим наблюдениям, в младшей школе гораздо больше времени уделяют умению делить в столбик, чем объяснению смысла деления. Люди чаще умеют делить в столбик, чем знают, что такое "разделить".

На День Рождения Фоксфорда к мистеру Фоксу и мистеру Форду пришло много гостей. Оказалось, что мистер Фокс знает 65 % гостей, а мистер Форд  — 1 ответ

— 45 %. Каждый гость знаком хотя бы одним из хозяев, а не менее 5 человек знакомы им обоим. Какое наименьшее число гостей могло было на празднике?
10 человек оценили этот вопрос
Интересный вопрос

Гости принадлежат или знакомым мистера Фокса (множество A), или знакомым мистера Форда (множество B) или их пересечению (A⋂B). Больше вариантов нет. Пусть число гостей - x.

Тогда

|A| = 0.65 * x

|B| = 0.45 * x

|A⋃B| = x

А также (из условия)

|A⋂B| ≥ 5

Воспользуемся формулой включений-исключений.

|A⋃B| = |A| + |B| - |A⋂B|

Перепишем, подставив:

x = 0.65x + 0.45x - |A⋂B| = 1.1x - |A⋂B| ≤ 1.1x - 5

x ≤ 1.1x - 5

0.1x ≥ 5

x ≥ 50

Значит минимальное число гостей - 50

НО! (как меня тут правильно поправляют)

Необходимо, чтобы выполнялось ещё одно условие: |A| и |B| - целые числа.

Т.е. x * 0.65 - целое. В простых дробях это 13/20x - целое, значит x кратно 20.

Так же для x * 0.45 - целое. В простых дробях это 9/20x - значит опять же x кратно 20.

Минимально число, кратное 20, но большее 50 - 60.

Ответ - 60.

Интересный вопрос
Не кочегары мы, не плотники.

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

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

Популярные темы