ну это почти определение предела в хаусдорфовом топологическом пространстве (если окрестность заменить на замкнутое множество). Для евклидовых пространств - одно из нескольких десятков эквивалентных, далеко не самое мощное. Собственно, такое количество эквивалентных определений и удобно, что для доказательства можно выбрать наиболее подходящее. Я очень сомневаюсь, что оно может упростить ряд доказательств, потому что для него даже метрики не нужно, только наличие свойства отделимости (я тут, конечно, говорю о строгих доказательствах)
ну это же просто неверно в общем случае. Возьмите последовательность 0, sinx, 0, sin2x, 0, sin3x, ... в пространстве непрерывных функций на отрезке от 0 до 2π (с практически любой метрикой, например, L2). У нее единственная точка сгущения - 0, но предела нет. вместо sin(nx) можно взять базис в любом бесконечномерном пространстве с метрикой.
Для полноты картины хочу оставить ссылку на статью 2003 года, которая обобщает задачу на произвольные фигуры, и вводит понятие partridge number как минимальное n, для которого задача имеет решение (то есть, partridge number квадрата равен 8) Так, partridge number равностороннего треугольника равен 9; а есть ли невыпуклые фигуры, для которых задача имеет решение - вроде как до сих пор неизвестно (возможно, потому что никто ей всерьез не занимался)
C# всегда был одним из моих основных языков программирования, и, пожалуй, самым любимым, еще до его официального релиза в 2002 году, когда к нам на мат-мех СПБГУ приходили ребята из Микрософт показать новый крутой язык. Я хорошо помню, как они на наших глазах открыли Visual Studio, написали "Console.", вызвали контекстную подсказку, и ноутбук завис намертво! Его перезагрузили, и со второго раза все получилось!
Потом я много лет на нем работал (вместе с Java и C++), но где-то после шестой версии он начал терять популярность и уступать яве и Go (хотя вы можете возразить, что Ява всегда была популярнее?). И такое впечатление, на самом высоком уровне в Микрософт было принято решение экстенсивного развития языка. Я помню, я читал тикет про nullable types (известное изменение в семантике языка, делающее все классы по умоллчанию non-nullable), еще до его официального принятия. Там один человек спросил: "Теперь выражение default(T) больше не имеет тип T - вам не кажется, что это не консистентно?" На что представилель Микрософта прямо ответил: "на данном этапе развития языка создание сообщества вокруг него для нас важнее его внутренней непротиворечивости."
Тем не менее, я признаю, что это было, наверно, правильное решение. Сейчас c# мультипарадигменный, я на нем писал и суровый энтерпрайз с абстрактными фабриками, и супербыстрые числодробилки с System.Runtime.Intrinsics и вычислениями на видеокарте с ILGPU.net, и ad-hoc скрипты как в питоне. Если кто увлекается программистскими задачками, и решает Advent of Code каждый год, знает, что подавляющее большинство их делают на питоне. Я решал их на c# два последних года, и даже пару раз попал на глобальный leaderboard (что лично для меня огромное достижение, так как приходится соревноваться и с competitive programmers, соревнующихся с детства, так и с LLMs, решающих простые задачи за секунды)! Я описал свой опыт использования c# вместо питона на реддите в этой статье.
Лично мое мнение - современный C# очень недооценен: он по удобству тулинга сопоставим с Ява, по скорости разработки - с Питоном, по скорости компиляции - с Go, по скорости работы - с C++. То ли Микрософт не вполне справились с продвижением языка, то ли это не было для них приоритетом...
Ну, вроде бы автор блога признает ваше авторство, в блоге есть ссылка на последовательность OEIS (или он это добавил после вашего комментария?). А автор видео, скорее всего, больше фокусировался на развлекательной составляющей, чем на научной.
Спасибо, интересно! Я бы никогда не узнал, что формулу Кардано придумал совсем не Кардано, если бы тут не прочитал. Что заставляет задуматься, сколько есть еще известных вещей, изобретение которых приписывают совсем не тем людям? Возможно оффтопик, но тема интересная, и хочу поделиться своими эмоциями из курса тфкп:
формула Эйлера для функции Римана обнаруживает связь между тфкп и простыми числами. Кстати, эта формула элементарно доказывается, доказательство доступно не математикам.
Вы упомянули основную теорему алгебры, самое тут крутое, что она доказывает, что комплексные числа являются алгебраическим замыканием действительных чисел. Известно, что любое поле имеет алгебраическое замыкание, и это доказывается с помощью аксиомы выбора! Это показывает связь тфкп с алгеброй и теорией множеств.
Голоморфные функции очень тесно связаны с гармоническими функциями (это почти одно и то же в каком-то смысле), что показывает тесную связь между тфкп и дифурами! Про это вообще редко говорят, но лично мне это кажется какой-то мистикой, что абстрактное алгебраическое расширение действительных чисел корнем квадратного уравнения можно наделить метрикой, кривизной и прочими векторными расслоениями (что, конечно же, показывает тесную связь между тфкп и геометрией/топологией)
Матановские техники, разработанные для тфкп (типа теоремы Коши) неожиданно позволяют решать разные задачи, напрямую никак не связанные с комплексными числами (например, посчитать сумму обратных квадратов натуральных чисел через вычеты). В каком-то смысле, это показывает связь тфкп с реальной жизнью (если для вас, как и для меня, решение интересных задачек является важной частью жизни!)
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
xx
O O
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.
я не физик и могу ошибаться, но насколько я понимаю, теорема как раз и доказывает, что удерживать плазму с помощью сферического поля в принципе невозможно. Сфера не является менее практичной, она физически невозможна. Так что если какой-то стартап и пытается это сделать, это не отличается от изобретения вечного двигателя. С другой стороны, я и не утверждаю, что изобретатели токомака явно пользовалсь этой теоремой - согласен, что они исходили из практических соображений.
Ага, правда, иногда случайности не случайны. Известна история, когда два студента Принстона обнаружили, что комбинация их фамилий звучит по-английски очень неприлично, и решили, что должны обязательно написать совместную статью. Теперь в математике есть машина Кокса-Цукера (Cox-Zucker Machine)
Это, конечно, баловство, но я уместил решение в восемь строчек на питоне! Тут смысла не очень много, это просто формальное преобразование ранее полученных формул с целью уменьшения количества кода.
def cnt(N, b):
f1, f2 = [1]*N, [1]*N
for k in range(1, N//(b-1) + 2):
for n in reversed(range(N)):
f1[n] += sum(f1[n - min(b-1, n, n+1-(k-1)*(b-1)) : n])
for t in range(1, min(2*b-1, n+1, n+2-(k-1)*(b-1))):
f2[n] += (b - abs(b-1-t))*f2[n-t]
return [f2[i] * 4 - f1[i] * 4 + 1 for i in range(N)]
Спасибо, интересная задача! Я немного подумал над ней, но в комментариях хабра мало места, чтобы подробно написать. Примерно так получилось (рассуждения, в принципе, повторяют ваши, но только в более привычных обозначениях): Во-первых, возьмем основание системы счисления произвольное b вместо 10, мне так формулы легче воспринимаются. Для положительных x обозначим сумму цифр Теперь сначала рассмотрим одномерный случай: посчитаем количество таких x, что для всех , будем называть такие числа достижимыми (из нуля). Для этого введем две функции: - количество достижимых чисел в отрезке и , равная единице, если сумма цифр последнего числа в отрезке не превосходит n, иначе нулю. То есть, она говорит, можем ли мы продолжать смотреть следующие отрезки, или надо остановиться. Тогда f и q можно выразить такими формулами:
Теперь точно так же рассмотрим двумерный случай. Удивительно, что условие на то, надо ли нам рассматривать следующий квадрат или нет, сводится к той же самой функции q (не зависящей от размерности!). Я строго не смог доказать это, но там должны быть примерно ваши рассуждения. Для двумерной f формула почти такая же:
Или можно ее сократить до одной суммы, если взять diag(t) равной количеству пар x, y в квадрате bxb, в сумме не превосходящих t:
Теперь, имея одномерную и двумерную функции, можно получить ответ по принципу inclusion-exclusion. Что касается кода, то проверить правильность результата можно обычным поиском (в глубину или ширину, неважно): код на питоне
Вычислить сразу все решения до заданного n можно по этой рекуррентной формуле: код на питоне, вроде бы результаты совпадают с вашими c b=10, N=900.
Сложность алгоритма O(n^2 * b), так как надо итерировать f до значений k=O(n).
В математике вероятность определяется как нормированная мера на сигма-алгебре множеств, в этом контексте событие определяется как измеримое множество. Поэтому явное перечисление множеств (событий) и задание меры на них является фундемантальным и математически корректным способом ввести вероятность.
Спасибо, интересно. Я всегда считал, что естественное обобщение - произведение n-1 вектора в n-менром пространстве как вектор длиной площадь n-1-мерного параллелограмма и перпендикулярный им, и его можно посчитать как определитель матрицы, в которой строки - координаты векторов и базис. Но, согласно википедии, существует много вариантов обобщений, в зависимости от того, какие свойства векторного произведения мы хотим сохранить.
А точно есть такие правила? В Википедии (особенно в Computer Science) много ссылок на форумы и даже личные страницы, когда, например, нет или мало научных статей на эту тему - часто встречается, когда люди делают исследования и не считают нужным их публиковать в авторитетных источниках. Например, в этой статье первые четыре ссылки ведут на форумы и личные страницы (хотя, насколько я знаю, основные результаты по этой теме опубликованы)
Это стандартная задача на поиск в глубину, таких много на литкоде. Самый простой (и медленный) вариант на питоне:
from sys import setrecursionlimit
from textwrap import wrap
setrecursionlimit(100000)
words = open('words.txt').read().split()
def no_repeats(word): return len(set(word)) == len(word)
words = [word for word in words if len(word) == 5 and no_repeats(word)]
def dfs(result, index):
if len(result) >= 25:
print(wrap(result, 5))
return
if index >= len(words):
return
if no_repeats(result+words[index]):
dfs(result+words[index], index+1)
dfs(result, index+1)
dfs("", 0)
ну это почти определение предела в хаусдорфовом топологическом пространстве (если окрестность заменить на замкнутое множество). Для евклидовых пространств - одно из нескольких десятков эквивалентных, далеко не самое мощное. Собственно, такое количество эквивалентных определений и удобно, что для доказательства можно выбрать наиболее подходящее.
Я очень сомневаюсь, что оно может упростить ряд доказательств, потому что для него даже метрики не нужно, только наличие свойства отделимости (я тут, конечно, говорю о строгих доказательствах)
ну это же просто неверно в общем случае. Возьмите последовательность 0, sinx, 0, sin2x, 0, sin3x, ... в пространстве непрерывных функций на отрезке от 0 до 2π (с практически любой метрикой, например, L2). У нее единственная точка сгущения - 0, но предела нет.
вместо sin(nx) можно взять базис в любом бесконечномерном пространстве с метрикой.
Для полноты картины хочу оставить ссылку на статью 2003 года, которая обобщает задачу на произвольные фигуры, и вводит понятие partridge number как минимальное n, для которого задача имеет решение (то есть, partridge number квадрата равен 8)
Так, partridge number равностороннего треугольника равен 9; а есть ли невыпуклые фигуры, для которых задача имеет решение - вроде как до сих пор неизвестно (возможно, потому что никто ей всерьез не занимался)
C# всегда был одним из моих основных языков программирования, и, пожалуй, самым любимым, еще до его официального релиза в 2002 году, когда к нам на мат-мех СПБГУ приходили ребята из Микрософт показать новый крутой язык. Я хорошо помню, как они на наших глазах открыли Visual Studio, написали "Console.", вызвали контекстную подсказку, и ноутбук завис намертво! Его перезагрузили, и со второго раза все получилось!
Потом я много лет на нем работал (вместе с Java и C++), но где-то после шестой версии он начал терять популярность и уступать яве и Go (хотя вы можете возразить, что Ява всегда была популярнее?). И такое впечатление, на самом высоком уровне в Микрософт было принято решение экстенсивного развития языка. Я помню, я читал тикет про nullable types (известное изменение в семантике языка, делающее все классы по умоллчанию non-nullable), еще до его официального принятия. Там один человек спросил: "Теперь выражение default(T) больше не имеет тип T - вам не кажется, что это не консистентно?" На что представилель Микрософта прямо ответил: "на данном этапе развития языка создание сообщества вокруг него для нас важнее его внутренней непротиворечивости."
Тем не менее, я признаю, что это было, наверно, правильное решение. Сейчас c# мультипарадигменный, я на нем писал и суровый энтерпрайз с абстрактными фабриками, и супербыстрые числодробилки с System.Runtime.Intrinsics и вычислениями на видеокарте с ILGPU.net, и ad-hoc скрипты как в питоне. Если кто увлекается программистскими задачками, и решает Advent of Code каждый год, знает, что подавляющее большинство их делают на питоне. Я решал их на c# два последних года, и даже пару раз попал на глобальный leaderboard (что лично для меня огромное достижение, так как приходится соревноваться и с competitive programmers, соревнующихся с детства, так и с LLMs, решающих простые задачи за секунды)! Я описал свой опыт использования c# вместо питона на реддите в этой статье.
Лично мое мнение - современный C# очень недооценен: он по удобству тулинга сопоставим с Ява, по скорости разработки - с Питоном, по скорости компиляции - с Go, по скорости работы - с C++. То ли Микрософт не вполне справились с продвижением языка, то ли это не было для них приоритетом...
Ну, вроде бы автор блога признает ваше авторство, в блоге есть ссылка на последовательность OEIS (или он это добавил после вашего комментария?). А автор видео, скорее всего, больше фокусировался на развлекательной составляющей, чем на научной.
Спасибо, интересно! Я бы никогда не узнал, что формулу Кардано придумал совсем не Кардано, если бы тут не прочитал. Что заставляет задуматься, сколько есть еще известных вещей, изобретение которых приписывают совсем не тем людям?
Возможно оффтопик, но тема интересная, и хочу поделиться своими эмоциями из курса тфкп:
формула Эйлера для функции Римана обнаруживает связь между тфкп и простыми числами. Кстати, эта формула элементарно доказывается, доказательство доступно не математикам.
Вы упомянули основную теорему алгебры, самое тут крутое, что она доказывает, что комплексные числа являются алгебраическим замыканием действительных чисел. Известно, что любое поле имеет алгебраическое замыкание, и это доказывается с помощью аксиомы выбора! Это показывает связь тфкп с алгеброй и теорией множеств.
Голоморфные функции очень тесно связаны с гармоническими функциями (это почти одно и то же в каком-то смысле), что показывает тесную связь между тфкп и дифурами! Про это вообще редко говорят, но лично мне это кажется какой-то мистикой, что абстрактное алгебраическое расширение действительных чисел корнем квадратного уравнения можно наделить метрикой, кривизной и прочими векторными расслоениями (что, конечно же, показывает тесную связь между тфкп и геометрией/топологией)
Матановские техники, разработанные для тфкп (типа теоремы Коши) неожиданно позволяют решать разные задачи, напрямую никак не связанные с комплексными числами (например, посчитать сумму обратных квадратов натуральных чисел через вычеты). В каком-то смысле, это показывает связь тфкп с реальной жизнью (если для вас, как и для меня, решение интересных задачек является важной частью жизни!)
Здесь: https://habr.com/ru/articles/945486/comments/#comment_28829868
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.
кажется, это не всегда работает. Например, для n=15 оптимальная упаковка не найдется
я не физик и могу ошибаться, но насколько я понимаю, теорема как раз и доказывает, что удерживать плазму с помощью сферического поля в принципе невозможно. Сфера не является менее практичной, она физически невозможна.
Так что если какой-то стартап и пытается это сделать, это не отличается от изобретения вечного двигателя.
С другой стороны, я и не утверждаю, что изобретатели токомака явно пользовалсь этой теоремой - согласен, что они исходили из практических соображений.
о, отличная задача, по таким можно отдельный обзор писать. Навскидку еще приходит в голову задача о разборчивой невесте
Ага, правда, иногда случайности не случайны. Известна история, когда два студента Принстона обнаружили, что комбинация их фамилий звучит по-английски очень неприлично, и решили, что должны обязательно написать совместную статью. Теперь в математике есть машина Кокса-Цукера (Cox-Zucker Machine)
Это, конечно, баловство, но я уместил решение в восемь строчек на питоне! Тут смысла не очень много, это просто формальное преобразование ранее полученных формул с целью уменьшения количества кода.
Спасибо, интересно было вспомнить (хотя у мы только симплекс-метод проходили, когда-то вручную его программировал, без всяких библиотек).
это вот этот курс? оставлю ссылку, может, кто-то захочет посмотреть (а вдруг?!!)
Спасибо, интересная задача!
для всех 
, будем называть такие числа достижимыми (из нуля).
- количество достижимых чисел в отрезке ![[0, b^k]](https://habrastorage.org/getpro/habr/formulas/0/00/004/004304a805b694745c153506aacadd11.svg)
и 
, равная единице, если сумма цифр последнего числа в отрезке ![[0, b^k]](https://habrastorage.org/getpro/habr/formulas/0/00/004/004304a805b694745c153506aacadd11.svg)
не превосходит n, иначе нулю. То есть, она говорит, можем ли мы продолжать смотреть следующие отрезки, или надо остановиться.
Я немного подумал над ней, но в комментариях хабра мало места, чтобы подробно написать. Примерно так получилось (рассуждения, в принципе, повторяют ваши, но только в более привычных обозначениях):
Во-первых, возьмем основание системы счисления произвольное b вместо 10, мне так формулы легче воспринимаются. Для положительных x обозначим сумму цифр
Теперь сначала рассмотрим одномерный случай: посчитаем количество таких x, что
Для этого введем две функции:
Тогда f и q можно выразить такими формулами:
Теперь точно так же рассмотрим двумерный случай. Удивительно, что условие на то, надо ли нам рассматривать следующий квадрат или нет, сводится к той же самой функции q (не зависящей от размерности!). Я строго не смог доказать это, но там должны быть примерно ваши рассуждения. Для двумерной f формула почти такая же:
Или можно ее сократить до одной суммы, если взять diag(t) равной количеству пар x, y в квадрате bxb, в сумме не превосходящих t:
Теперь, имея одномерную и двумерную функции, можно получить ответ по принципу inclusion-exclusion.
Что касается кода, то проверить правильность результата можно обычным поиском (в глубину или ширину, неважно): код на питоне
Вычислить сразу все решения до заданного n можно по этой рекуррентной формуле: код на питоне, вроде бы результаты совпадают с вашими c b=10, N=900.
Сложность алгоритма O(n^2 * b), так как надо итерировать f до значений k=O(n).
упс, хотел написать длинный комментарий, но случайно опубликовал его. Напишу его заново и опубликую
В математике вероятность определяется как нормированная мера на сигма-алгебре множеств, в этом контексте событие определяется как измеримое множество.
Поэтому явное перечисление множеств (событий) и задание меры на них является фундемантальным и математически корректным способом ввести вероятность.
Спасибо, интересно. Я всегда считал, что естественное обобщение - произведение n-1 вектора в n-менром пространстве как вектор длиной площадь n-1-мерного параллелограмма и перпендикулярный им, и его можно посчитать как определитель матрицы, в которой строки - координаты векторов и базис.
Но, согласно википедии, существует много вариантов обобщений, в зависимости от того, какие свойства векторного произведения мы хотим сохранить.
А точно есть такие правила? В Википедии (особенно в Computer Science) много ссылок на форумы и даже личные страницы, когда, например, нет или мало научных статей на эту тему - часто встречается, когда люди делают исследования и не считают нужным их публиковать в авторитетных источниках.
Например, в этой статье первые четыре ссылки ведут на форумы и личные страницы (хотя, насколько я знаю, основные результаты по этой теме опубликованы)
Это стандартная задача на поиск в глубину, таких много на литкоде. Самый простой (и медленный) вариант на питоне: