?

Log in

No account? Create an account
LiveJournal for RElf.

Live Journal User Rating Рейтинг блогов


View:User Info.
View:Friends.
View:Calendar.
View:Memories.
You're looking at the latest 20 entries. Missed some entries? Then simply jump back 20 entries.

Sunday, July 20th, 2003

Subject:мой лейб-мотив
Time:6:45 pm.
Mood: ностальгирую.
Не так давно В 2002-м году Олег Хлебников (SmokerMan) по моей просьбе исполнил "Песню о программистской молодости" на слова Юрия Нестеренко.

Когда мало кто знал, что значит Ctrl-Alt-Del,
Когда не каждый ребенок калькулятор имел,
А под словом "Паскаль" понимался обычно философ,
Еще не все перфораторы пустили на слом,
Но мы пришли в этот мир, и мы пошли напролом,
И не знали покоя от новых идей и вопросов.
...Collapse )
Слушаем prog.mp3 и дружно рыдаем... или не рыдаем:



UPDATE: To же в другой аранжировке и 192kBps:

Comments: Read 21 orAdd Your Own.

Monday, July 13th, 2020

Subject:задачки для досуга
Time:9:18 pm.
Скопилось некоторое количество задач (вполне приподъемных на мой взгляд), над которыми хотелось бы подумать на досуге. К своему несчастью досуг выпадает нечасто, а задачи со временем я забываю.

Это будет что-то типа памяткиCollapse )

UPD. Prove or Disprove. 100 Conjectures from the OEIS (current status)

UPD. 1031 Generating Functions and Conjectures by S. Plouffe
Comments: Read 12 orAdd Your Own.

Tuesday, July 2nd, 2019

Subject:sensitivity
Time:11:41 pm.
Originally posted by rus4. Reposted by relf at 2019-07-02 23:41:00.

Если в единичном кубе {0,1}n взять половину всех вершин, то среди них может не быть пар соседних. Но если взять больше половины, то среди них уже есть вершина, имеющая хотя бы n1/2 соседних взятых. Это доказал умный Хао Хуанг по-умному.

https://fedyapetrov.wordpress.com/2019/07/03/low-level-variant-of-huangs-argument-for-sensitivity-conjecture/
Comments: Read 6 orAdd Your Own.

Wednesday, May 1st, 2019

Subject:мальчик, девочка и пес
Time:5:04 am.
Originally posted by avva. Reposted by relf at 2019-05-01 05:04:00.

Мальчик, девочка и пес отправляются в прогулку по маршруту длиной 10 миль. Мальчик и девочка идут со скоростью 2 мили в час, пес бежит со скоростью 4 мили в час. У них есть велосипед, на котором может ехать лишь один из них в данный момент времени (включая пса). Дети едут со скоростью 12 м/ч, а пес со скоростью 16 м/ч. За какое кратчайшее время они все смогут добраться до конца маршрута?

Эта задачка с красивым решением тяжелее, чем кажется. Комментарии скринятся на сутки.

P.S. Спрашивается время от начала пути, после которого они все пересекли финишную черту. Т.е. не складывать время каждого, а найти время последнего (наилучший вариант).

Update. Много правильных решений, даже очень много, и даже неправильные в основном ошиблись в подсчетах, но нашли главную идею. Вы все очень умные :) Раскрываю все комментарии, не заглядывайте больше туда, если боитесь спойлеров.
Comments: Read 151 orAdd Your Own.

Friday, March 15th, 2019

Subject:Еще немного о двоичных последовательностях.
Time:8:52 am.
Originally posted by xcontcom. Reposted by relf at 2019-03-15 08:52:00.



Read more...Collapse )

Comments: Read 50 orAdd Your Own.

Monday, February 4th, 2019

Subject:Суровый канадский лесоруб
Time:12:14 am.
Originally posted by xaxam. Reposted by relf at 2019-02-04 00:14:00.

Вдали от столичной суеты

Возьмём квадратную матрицу размера n x n и заполним её случайным образом плюс-минус единицами. Определитель такой матрицы - целое число между -n! и +n!. С какой вероятностью он окажется нулём? Ответ зависит от n: при n=1 ответ - нуль, при n=2 эта вероятность равна 1/2, если n=3, то посчитайте сами ;-)

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

Задачу начали ковырять больше полувека назад, - первым (нетривиальным!) результатом было то, что вероятность убывает до нуля с ростом n. После этого почти тридцать лет было потрачено на то, чтобы понять, с какой скоростью она убывает: прорывной результат был получен в 1995-м и утверждал, что вероятность убывает быстрее, чем некоторая убывающая геометрическая прогрессия. Но какая прогрессия! Было доказано, что ответ стремится к нулю не медленнее, чем (0.999+...)n. Константу 0.999 удалось затем уменьшить, сначала до 0.75, потом до корня из двух пополам, 0.7071...

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

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

Знакомьтесь: Константин Тихомиров, assistant professor (ассистент? скорее старший преподаватель по российским понятиям, короче, под-доцент) в Georgia Tech, Грузинский Политех. Примечательно, как Костя туда попал:
  • Диплом - 2008, Самарский (б. Куйбышевский) университет, прикладная математика и информатика;
  • к.ф.-м.н., 2011, Самарский ГУ (что означает, что он защищался в Воронеже, - я не понимаю, Воронеж - тоже заметное место на математической карте России).
  • Ph. D., 2016, University of Alberta, Canada. Я затрудняюсь подобрать соответствующий российский эквивалент. Омский универ? Томский? Красноярский?
  • Постдок в Принстоне (2016-2018), визитёр-постдок в Беркли (4 месяца).
Ни мехматов, ни вышек, ни гарвардов в анамнезе. Дерзайте, девушки и юноши!

♣ Когда вы не сможете прочесть эту надпись здесь, вы сможете всегда её прочесть тут. Комментируйте где хотите, на Дриме уже comment count unavailable таких осторожных комментаторов набралось.

А Оккам... да хрен с ним, с Оккамом!

Comments: Read 103 orAdd Your Own.

Thursday, December 27th, 2018

Subject:задачка о треугольнике паскаля
Time:10:56 am.
Originally posted by avva. Reposted by relf at 2018-12-27 10:56:00.

Организаторы IMO - международной олимпиады по математике - за 2019 год запостили в Фейсбуке красивую задачку в виде новогоднего подарка. Вот ее условие в переводе на русский, предлагаю попробовать. Сразу скажу, что задача решается без сложных выкладок и компьютерных программ, и не такая тяжелая, как задачи на международной олимпиаде :), но и не тривиальная.

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

==================
Предположим, у нас есть строка из нулей и единиц, например, "0 0 1 1 0 1". Построим на ней "треугольник Паскаля", в котором каждое число - сумма двух лежащих над ним, только все суммы делаются по модулю 2, так что во всем треугольнике только нули и единицы. Иными словами, каждое число равно 0, если два лежащих над ним числа равны, и 1 если они неравны:

0 0 1 1 0 1
 0 1 0 1 1
  1 1 1 0
   0 0 1
    0 1
     1

В треугольнике, что у нас получился, посмотрим на две строки: верхняя строчка слева направо, это то, с чего мы начали: 0 0 1 1 0 1, а также диагональ от низа по правому краю: 1 1 1 0 1 1 (внимание, именно в этом направлении: ОТ нижнего числа К самому крайнему справа сверху). Эти две строчки не одинаковые в нашем примере. Если для какой-то начальной строки они окажутся одинаковые, назовем такую строку "красивой".

Представьте, что вы берете все 2^n возможных строк из 0 и 1 длиной n, и каждую проверяете, красивая она или нет, построив такой треугольник. Сколько всего будет красивых строк длиной n?

Сложные вычисления не нужны для решения задачи. Используйте только красивые идеи.
==================

Update: вы все охренительно умные. В комментариях есть много, пока скрытых, правильных решений. Первым(ой) предложил(а) полное решение с док-вом юзер dodderbranch. К полудню по Москве есть также верные решения от andronic, Migmit, darth_mozg, "Я Я", utnapishti, akho. Еще несколько человек дали правильный ответ, но без полного доказательства. Завтра раскрою все комментарии.

Update: раскрыл все комментарии.
Comments: Read 42 orAdd Your Own.

Wednesday, December 26th, 2018

Subject:задача дня -- 10
Time:2:54 pm.
Originally posted by falcao. Reposted by relf at 2018-12-26 14:54:00.

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

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

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

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

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

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

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

Всем спасибо за участие, и с наступившим Новым годом!
Comments: Read 9 orAdd Your Own.

Thursday, September 27th, 2018

Subject:О безумной старушке
Time:10:25 pm.

Кто-то решил монетизировать обобщить задачу о безумной старушке:

Absent-minded passengers

Comments: Read 4 orAdd Your Own.

Monday, September 10th, 2018

Subject:Математическая цензура
Time:7:54 pm.


scinquisitor рассказывает, как математика перестает быть беспристрастной.

Comments: Add Your Own.

Wednesday, August 15th, 2018

Subject:пара умозрительных задачек с монетками
Time:10:25 am.
Глядя, как народ развлекается решением логических задачек, припомнил пару оных для решения в уме:

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

2. На прямоугольном столе лежит 25 одинаковых монет без перекрытий, причём нельзя добавить еще одну монету так, чтобы она не перекрывалась с уже лежащими. Докажите, что весь стол можно покрыть 101 монетой с перекрытиями так, чтобы каждая точка стола была покрыта по крайней мере одной монетой.

Комментарии скринятся.
Comments: Read 17 orAdd Your Own.

Wednesday, July 11th, 2018

Subject:неведомая уйня
Time:9:00 pm.


(via dr_jamais)
Comments: Add Your Own.

Thursday, May 31st, 2018

Subject:вишнёвый блин (почти)
Time:12:23 pm.
В продолжение к вопросу об именах:

ACM elects Cherri Pancake as president
И это не шутка ;)
Comments: Add Your Own.

Saturday, March 3rd, 2018

Subject:Я худею с ваших БАДов
Time:2:21 pm.


Злой критик: Я худею с ваших БАДов

Сразу вспомнилось про собственные экспериментына этом поприще.

Comments: Add Your Own.

Saturday, January 27th, 2018

Subject:Здорово и вечно
Time:5:12 pm.
Comments: Add Your Own.

Friday, January 12th, 2018

Subject:ошибка переводчиков Стенли
Time:8:17 am.
Слушая доклад Ira Gessel на JMM 2018, вспомнил об одной забавной ошибке в русском издании Стенли "Перечислительная комбинаторика". Цитата:



Все бы ничего, но Гессель не Ира, а Айра, и к тому же мужчина. И ошибка не единичная, а систематическая - везде, где его имя упоминается, переводчик предполагает женский род.
Comments: Read 5 orAdd Your Own.

Subject:кайф плавания
Time:12:01 am.
Плавание всегда давалось мне с трудом. И я немного завидовал тем, кто мог технически безупречно и автоматически плыть и плыть и плыть. Для меня всегда где-то маячила цель другого берега и установка: давай-же, давай, ещё чуть чуть, осталось несколько метров... В результате к цели я приплывал уставший, и требовалось некоторое время, чтобы прийти в себя и собраться с силами плыть в обратную сторону.
И вдруг во время очередного купания меня осенило!

Секрет оказался прост: цель доплыть вторична! Во время плавания нужно прислушиваться к своему организму и только, и вообще лучше плыть с закрытыми глазами. Это же так приятно, когда мышцы рук преодолевают сопротивление воды снова и снова, а тело нежно обволакивает вода. Усталость есть, но она ничему не мешает, можно плыть и плыть, и чувствовать только воду вокруг и работу собственных мышц. Скорость неважна, цель неважна - важен сам процесс. Как только я это понял, я без передышки смог проплыть больше, чем когда-либо прежде.

В общем, плавание становится моим любимым видом спорта. Чего и вам желаю.
Comments: Read 3 orAdd Your Own.

Thursday, July 27th, 2017

Subject:Трамп начинает и выигрывает
Time:10:47 am.
Если 9 избирателей разбиты на три группы по три избирателя так, что в двух группах есть по два сторонника Мирафлореса, то победят сторонники Мирафлореса, хотя их — 4 из 9. Значит, на многоступенчатых выборах может победить кандидат, за которого проголосовало меньшинство.
Нетрудно сообразить, что при двуступенчатых выборах с бо́льшим числом избирателей процент голосов, необходимый для победы, может быть ещё меньше, но всё-таки заведомо больше 25%. При трёхступенчатой системе этот процент можно сделать ещё ниже.


Первая задача из Кванта, между прочим. 1970 год.
Comments: Read 10 orAdd Your Own.

Friday, May 26th, 2017

Subject:без бабушек и дедушек
Time:12:06 pm.
Им показалось подозрительным, что молодые туристы плавают на комфортабельных кораблях без своих бабушек и дедушек.
Comments: Add Your Own.

Wednesday, April 26th, 2017

Subject:пропаганда суицида
Time:11:36 pm.
Пришло письмо от нашего РОНО:
...concerns from both educators and parents about a recent Netflix series “13 Reasons Why,” which has become popular among our students. This fictional series, rated for mature audiences only (TV-MA), details the story of a 17-year-old girl who leaves behind 13 audiotapes prior to her suicide. The tapes reveal how her relationships with others led to her suicide. The episodes include graphic content involving sexual assaults and the act of suicide. Mental health professionals have raised concerns about the potential risks that exist for some teenagers because of the sensationalized treatment of suicide. There are no messages of help and support included with “13 Reasons Why.” The decision to allow your children to watch this series is, of course, a personal choice. However, given the abundance of concern from professional organizations and mental health professionals, we wanted to make you aware of its potential effect.

А в Фейсбуке тем временем пишут, что у кого-то знакомый тинейджер реально покончил с собой после просмотра.
Вот такая реклама фильму. Надо будет посмотреть вместе со старшим отпрыском...
Comments: Read 1 orAdd Your Own.

LiveJournal for RElf.

Live Journal User Rating Рейтинг блогов


View:User Info.
View:Friends.
View:Calendar.
View:Memories.
You're looking at the latest 20 entries. Missed some entries? Then simply jump back 20 entries.