moose, transparent

шестая задача олимпиады

Шестая задача Международной математической олимпиады тоже оказалось в этом году одной из сложных - ее целиком решили 37 участников (самую легкую, четвертую задачу целиком решили 309 участников).



У меня интересно вышло с этой задачей. Я долго над ней думал на прошлых выходных и в начале недели. Немного с ручкой и бумагой, но в основном в уме, просто пялился в пространство и думал. Мне казалось, что у меня есть правильный подход и надо только довести его до конца. Там в условии написано, что числа необязательно положительные; так вот, если они обязательно положительные, то я довольно быстро нашел решение, но отрицательные числа его "ломают", и мне все казалось, что можно этот ущерб как-то ограничить и нейтрализовать, и все никак не получалось. Наверное, часов восемь или десять в общей сложности думал над этой задачей, и ничего.

А сейчас, вот полчаса назад, я читал запись в блоге американского профессора Кала Ньюпорта. Он вообще-то профессор информатики, но известен своими книгами о продуктивности умственной работы, и особенно тезисом о важности "глубокой работы" - способности думать о чем-то долго, не отвлекаясь на мессенджеры и соц. сети, грубо говоря (сразу скажу, что не читал его книг, и не имею собственного мнения об этом пока). Так вот, у себя в блоге он цитирует другого ученого, который толкает следующую простую мысль: мы любим читать истории про "Эврика!", про озарение, про внезапно приходящую идею, но обычно такой момент случается после того, как много часов или дней бьешься над задачей, и ничего не получается.

Я это прочитал и подумал, ну вот я над шестой задачей столько думал и безрезультатно; может, я уже достаточно натренировал свой мозг на нее, чтобы теперь ниоткуда появилось бы решение, вот было бы здорово! Стал опять праздно думать над задачей и... через три минуты ниоткуда появилось решение. Честное слово, я не преувеличиваю. Это случилось полчаса назад.

После этого долгого введения предлагаю свое решение. Если хотите решать сами, не читайте дальше.
[Spoiler (click to open)]

В задаче дано, что с помощью элементов A мы можем составить суммы m, m^2, m^3.. и так далее до m^m. Если мы запишем эти числа наглядности ради в m-ричной системе счисления, они будут выглядеть так: 10, 100, 1000. Например, если m=10, то это собственно и будут числа десять, сто, тысяча итд., а если m=2, надо смотреть на 10, 100 итд. как на двоичные числа.

Теперь ясно, что с помощью этих сумм, равных 10, 100, 1000 итд. до 10000..0 (m+1 нулей), мы можем, складывая их вместе много раз, получить любое число из m m-ричных цифр (и 0 в конце). Например, возьмем m=10: если мы хотим получить 45670, нам нужно взять сумму, которая дает 10000 4 раза, сумму 1000 5 раз, итд. Таким образом, складывая эти суммы вместе, мы получим любое из m^m чисел от 0 до XXXXXXXX...X0, где X "цифра" m-1 в m-ричной системе записи. Таких разных чисел ровно m^m, потому что каждая из m "цифр" может быть чем угодно от 0 до m-1.

При этом в каждой такой мега-сумме каждый элемент исходного множества A присутствует не более m^2-1 раз. Действительно, мы берем сумму вида 1000 для каждого разряда не больше m-1 раз, и всего таких разрядов m. Значит, все m^m чисел могут быть получены как суммы чисел из A, причем каждое число берется не больше (m-1)m = m^2-m раз, и нам достаточно даже будет сказать, что не больше m^2-1 раз.

Но сколько есть вообще разных способов составить такую сумму из A? Если бы в A было ровно m/2 чисел, и для коэффициента при каждом из них m^2 возможностей (от 0 раз до m^2-1 раз берется это число), то всего разных сумм (m^2)^(m/2) = m^m. Если же в A меньше, чем m/2 элементов, то разных сумм точно меньше m^m, так что получить m^m разных чисел невозможно. Выходит, что в A не меньше m/2 элементов, что и требовалось доказать.
moose, transparent

еще раз о расизме и неграх

Поймал себя на неожиданной эмоциональной реакции. Читаю, скажем, внутрикорпоративную дискуссию о том, как надо или не надо себя вести в отношениях между людьми. Ну типа, друзья, давайте вести себя корректно и уважительно, не хамить и не быковать, вот например я тут кому-то делал code review, ему что-то не понравилось, и он такое устроил... И другие примеры в том же духе.

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

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

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

Нету больше. Задолбали реально с этими белыми мужчинами. Вот реально задолбали.
moose, transparent

про войну

Я тут читал дискуссию на реддите (англ.) о том, стоило ли Америке и Британии входить в союз с СССР против Гитлера (автор считает, что не стоило, потому что в итоге Сталин получил контроль над всей Восточной Европой, и это слишком дорогая цена итд.). Я, честно говоря, не очень заинтересован в этом конкретном вопросе - стоило-не-стоило, но он заставил меня осознать, что я не очень понимаю, зачем собственно они это сделали.

Реально очень наивный вопрос, я понимаю, но все же расскажите мне. Вот Гитлер открыл второй фронт и напал на СССР. Зачем Америке и Британии заключать союз и действовать вместе? Посылать ленд-лиз в огромных количествах итд.? Почему просто не дать событиям на восточном фронте развиваться так, как они развиваются, в любом случае он оттягивает огромную часть сил вермахта, СССР страна огромная, даже если Германия будет побеждать, всю ее не поглотить.

В альтернативной истории, в которой западные силы не заключают союз с СССР - что дальше происходит? Как развиваются события? Наверное об этом что-то писали историки или придумывали альтернативщики, или думали стратеги? Просто интересно.
moose, transparent

о грамотном отношении к статистике

Вот например такое выступление на Твиттере (перевод ниже):



"Примерно две трети людей, погибших в автокатастрофах в Британии, были пристегнуты, несмотря на то, что вообще-то ремнями безопасности пользуются почти 99%.
Это не значит, что ремни безопасности не работают.
Можно вот как это объяснить.
Один процент не-пристегивающихся отвечает за непропорционально огромные 33% жертв.
#ремниработают"

Это написал некий английский биолог-математик и автор популярных книг о математике.

Если вы подумали, что это не совсем о ремнях безопасности, то вы конечно правы. Это аналогия, которая должна объяснить, почему вакцины от ковид-19 работают, несмотря на то, что вакцинированные тоже заболевают и умирают. Если большинство населения (а среди группы риска - подавляющее большинство населения) привиты, и есть смерти в том числе среди привитых, но их процент намного меньше, чем процент привитых - это как 66% смертей пристегнуты, хотя 99% пристегиваются. В Англии сейчас действительно вроде выглядит так, и во многих местах в Америке (а вот в Израиле данные в последние месяц-полтора далеко не так однозначны, но не будем сейчас об этом, сложный вопрос).

Так вот что я хочу сказать. Когда я читаю этот твит, процитированный выше -- я не знаю, что вы думаете, когда его читаете, но могу сказать, что думаю я -- моя первая и немедленная мысль это "но как насчет искажающих факторов"? Под этим я имею в виду ту простую, казалось бы, мысль, что мы не знаем, насколько презрение к ремням коррелирует с склонностью к авариям, и насколько этот искажающий фактор влияет на статистику. Если предположить, что пристегивающиеся водители едут очень осторожно, а непристегивающиеся наоборот потрясающе безобразно, то вполне можно получить такие проценты, даже если ремни вообще ничего не делают. Мы не можем судить о том, что "#ремниработают" на основании этих цифр. Я не говорю, что они не работают - есть другие аргументы, например крэш-тесты с манекенами итд. Я понимаю, что запустить слепой рандомизированный эксперимент с ремнями на живых людях не очень практичная идея, но тем не менее манекены помогают нам это изучать. Но сказать "1% непристегнутых отвечают за 33% жертв и это показывает, что ремни работают", это элементарная неграмотность в работе с данными.

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

Это меня огорчает.

P.S. В применении к вакцинам - основой нашей уверенности в том, что вакцины работают, должны быть рандомизированные испытания (RCT), в которых их проверяли, и которые снимают (почти) все вопросы про искажающие факторы. Без этого одни только проценты того, сколько вакцинированных среди умерших в сравнении с долей в населении - все равно подлежит тем же сомнениям, что и в случае с ремнями: есть ли связь между отказом от вакцины и более рискованным поведением? есть ли связь между отказом от вакцины и состоянием здоровья, которое коррелирует с плохим прогнозом тяжелого ковид-19? Итд. итп. Опыт учит нас тому, что если есть шанс на то, чтобы искажающие факторы дали нам ложную картину мира, в какой-то степени они это неизбежно делают, и в какой - очень трудно оценить априори, и даже экспертные оценки часто оказываются неверными.
moose, transparent

первый том щербакова

Издали первый том песен Щербакова, песни за 1981-1987 (с полной нотной записью, не только словами).



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

(если честно, я искренне не понимаю, почему Щербаков не известен и не знаменит примерно в сто раз больше, чем он на самом деле)

Официальный издатель продает здесь: https://paltbook.ru/catalog/knigi/1052/

Но можно и на Озоне, и в других местах наверняка. Я купил на Озоне.
moose, transparent

cats n wires

Случайно попалась замечательная пиксельная игрушка: Cats n Wires by Kulisti



(на телефоне или таблете в нее не поиграешь, извините. Нужен странный инструмент под названием "компьютер")

Нужно прийти человечком к кошке, пользуясь тем, что проводом можно управлять с обеих концов (но всегда включать в розетку оба конца) и человечек может на проводе стоять. В дальнейших уровнях еще несколько забавных механизмов. 20 уровней и вполне можно пройти за час, при этом ностальгический пиксемализм доставляет удовольствие и вообще милота. Игра написана за 48 часов, между прочим, не хухры-мухры.
moose, transparent

немного компьютерной истории



До флеш-карт, до DVD-дисков, до компакт-дисков, задолго до всего этого люди пользовались, для хранения данных, дискетами. Те из нас, кто помнят это древнее время, скорее всего пользовались маленькими дискетами на 3,5 дюйма, в которых данные записывались на магнитный диск. И почти никто уже не помнит, как работали большие гибкие пятидюймовые дискеты. В них, как видно, если присмотреться к этой фотографии, данные считывались с хранящейся внутри дискеты перфокарты.

Фотографии из твиттера Даны Сиберы https://twitter.com/NanoRaptor/, у которой есть еще много интереснейших артефактов компьютерной истории, горячо рекомендую.
moose, transparent

r.i.p. steven weinberg (1933-2021)



Стивен Вайнберг, один из величайших физиков уходящей эпохи. Когда-то запомнился мне интереснейшей книжкой "Первые три минуты" о зарождении Вселенной. R.I.P.
moose, transparent

вторая задача олимпиады

Вторая задача Международной математической олимпиады в этом году оказалась одной из самых сложных - ее полностью решили всего 16 участников.



Мне кажется, что я ее решил, но мог проглядеть какую-то дырку в доказательстве - помогите мне и объясните, если так.

Само неравенство выглядит очень "естественным" и первая мысль - это что оно как-то легко должно сводиться к неравенству Коши-Шварца (Коши-Буняковского в русской традиции). Но ничего такого я не нашел. Вторая мысль - это что надо доказывать индукцией по числу переменных, рассматривая лишь "добавок", который вносит в обе суммы добавление x_n. Это очень заманчиво, но после разбора нескольких простых примеров становится ясным, что для "добавка" неравенство просто неверно иногда. То есть, если мы изолируем только слагаемые, в которых участвует x_n, может случиться, что сумма слева больше суммы справа - просто расстояние между значениями слева и справа для первых n-1 переменных между собой - еще больше, и "пересиливает".

Если есть доказательство, выводящее это неравенство из чего-то фундаментального, я это очень хочу знать. Но сам такого не нашел.

Дальше следует мое решение, если хотите решать сами, не читайте.
[Spoiler (click to open)]
Идея 1. Если одно из чисел равно 0, его можно выбросить, и расстояние между левой и правой частью неравенства не изменится. Таким образом мы сведем задачу к меньшему числу переменных.

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

Решение. Представим себе, что мы плавно двигаем все числа x_i одновременно, сдвигая их влево или вправо на одинаковое расстояние, т.е. прибавляя к ним всем одно и то же число x, положительное или отрицательное. Можно представить, как все числа x_i нанесены на бумагу и мы двигаем бумагу по числовой прямой. Что при этом происходит с неравенством? Левая часть вообще не меняется, потому что все x_i-x_j остаются теми же. Правая часть меняется. Если мы двигаем достаточно влево, все x_i+x_j становятся отрицательными и правая часть стремится к плюс бесконечности; если вправо, все x_i+x_j становятся положительными и опять стремится к плюс бесконечности. В середине же правая часть в каком-то месте получает наименьшее значение. Если мы докажем неравенство для этого места, то и в общем случае, понятно, оно будет верно, потому что левая часть не изменится, а правая только вырастет.

Представим, как мы двигаем числа слева направо от минус бесконечности. Поначалу все суммы x_i+x_j отрицательны, и наше движение вправо уменьшает правую часть. В какой-то момент какое-то x_i+x_j пересекает барьер 0, и после этого модуль заставляет нас брать квадратный корень не из -x_i-x_j, как до сих пор, а от x_i+x_j. В любой данный момент есть "отрицательные" пары, с x_i+x_j меньше нуля, и "положительные". Движение вправо уменьшает вклад от отрицательных пар (по модулю они уменьшаются) и увеличивает - от положительных. Плюс на "барьерах" отрицательные проходят через 0 и становятся положительными. Рано или поздно значение функции начинает расти, а не уменьшаться. Для наглядности мы можем заменить каждый x_i+x_j на константу a_ij, и рассматривать правую часть как фукнцию от переменной x, которую мы добавляем к каждой a_ij: сумма по всем i,j от sqrt(|x + a_ij|). По мере роста x "отрицательные" слагаемые x+a_ij превращаются в "положительные".

Возьмем тот x, для которого вся сумма получает наименьшее возможное значение. Я утверждаю, что это происходит на "барьере", в тот момент, когда одно из слагаемых равно 0. Это логично, потому что именно на барьерах слагаемые превращаются из уменьшающихся при росте x в увеличивающиеся. Предположим на секунду, что это действительно так - что из этого следует? Если мы опять вернемся к исходным числам x_i,x_j, и посмотрим, как они выглядят после сдвига, то "барьер" как раз означает, что x_i+x_j=0. При этом если i=j, то это случай, когда одно из чисел 0, а если это два разных числа, то они противоположны. В обоих случаях мы можем свести задачу к меньшему числу переменных, выбросив эти одно или два числа, и значит индукцией по числу переменных мы завершили доказательство.

Осталось строго доказать, что наименьшее значение функция принимает именно на "барьере". Почему это обязано быть так? Рассмотрим ситуацию между барьерами. По мере увеличения x у нас некоторые слагаемые - "отрицательные" - равны sqrt(-x-a_ij) и убывают, некоторые - "положительные" - равны sqrt(x+a_ij) и возрастают. Может, именно тут в какой-то момент возрастающие слагаемые "превозмогают" убывающие, и общая сумма теперь будет только расти? Я думаю, что нет, и мой аргумент основан на том, что функция sqrt(x+epsilon)-sqrt(x) монотонно убывает для фиксированного epsilon (проверяется вычислением ее производной по x). Если при каком-то x функция получила минимум, то на x+epsilon возрастающие слагаемые в сумме выросли больше, чем убывающие уменьшились. Но тогда при движении от x-epsilon к x возрастающие слагаемые должны были увеличиться еще чуть больше, а убывающие уменьшиться еще чуть меньше. Выходит, что на x-epsilon значение функции должно быть еще меньше, и это противоречие. Поэтому минимум должен достигаться в одной из точек перелома - "барьере".
moose, transparent

открытая запись

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

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