Введение
В мае далёкого 2015 года я заканчивал бакалавриат факультета общей и прикладной физики МФТИ. В основном я занимаюсь квантовой теорией поля, но в тот момент я решил, что хотелось бы больше вникнуть в современный мир компьютерных наук, что можно попробовать совместить МФТИ с ШАД Yandex (две магистратуры). ШАД тогда уже был у всех на слуху, вокруг только и твердили, какой там жёсткий курс алгоритмов, мне понравился сайт (лол), тематика курсов, и я решился поступать.
В этом посте я хотел бы рассказать о том, как происходило моё поступление в ШАД, рассказать своё решение экзаменационного варианта (разборов ШАДовских заданий на просторах рунета не очень-то много) и поговорить о том, что понравилось / не понравилось в этом замечательном заведении.
Онлайн-отбор дался без особого труда, в 2015 году давали 12 задач на месяц, из которых больше половины были комбинаторикой с ответом в виде числа, и только ленивый бы не написал на каждую задачу скриптик, чтобы проверить ответ (одну задачу я вообще решил только так). Нынче, насколько мне известно, дают какое-то ограниченное время, в пределах нескольких часов.
После онлайн-этапа меня пригласили на экзамен. К экзамену я готовился около недели, и сам по себе он доставил мне большое удовольствие. За 4 часа необходимо было решить 7 задач по математике и составить один алгоритм (всего 8 заданий). Метематика требуется самая разнообразная: линейная алгебра, мат. анализ (чуть ли не
![$\epsilon-\delta$](https://habrastorage.org/getpro/habr/post_images/f17/1cc/a4f/f171cca4fa62afad715be1eb91735d7e.svg)
формализм), комбинаторика и теор. вер., графы, преобразование Фурье и т.д. Мне кажется, это очень правильно от поступающих требовать именно знания математики, а не каких-нибудь там языков или скиллов (вообще в дальнейшем оказалось, что ШАД ориентирован именно на знание по сути, а не на технические детали).
Этот пост я хотел бы посвятить разбору варианта, который достался мне на экзамене. Закинувшись тремя чашками эспрессо и настойкой элеутерококка, я смог чистенько решить семь задач из восьми, и на восьмую я даже не успел посмотреть.
Мой экзамен
Задача 1
Квадратная матрица
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
такова, что
![$\mbox{tr} AX = 0$](https://habrastorage.org/getpro/habr/post_images/f63/6e8/df6/f636e8df624fd9c610501ae922f0f20a.svg)
для любой бесследовой
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
. Докажите, что матрица
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
скалярная.
Решение
Эта задача сразу напомнила мне другую, немного более сложную задачу с физтеховского экзамена по линейной алгебре в первом семестре, где нужно было доказать, что коммутирует со всеми матрицами только скалярная матрица. Как и там, здесь нужно воспользоваться тем, что матрица
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
любая, а значит, рассматривая матрицы
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
различного вида, мы можем наложить ограничения на марицу
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
.
Сперва рассмотрим матрицу
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
вида
![$X_{i j} = \delta_{ik} \delta_{j l}$](https://habrastorage.org/getpro/habr/post_images/d8b/da4/be0/d8bda4be016117a2a5984dc61f61d1b2.svg)
, то есть матрицу, у которой все элементы 0 кроме единички, стоящей в
![$k$](https://habrastorage.org/getpro/habr/post_images/839/452/3d1/8394523d1f4bab66a8544cd365388d87.svg)
-той строке на
![$l$](https://habrastorage.org/getpro/habr/post_images/ce3/8a8/387/ce38a83878bf16954ea60627fc7c66eb.svg)
-той позиции. Так как мы помним, что
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
— бесследовая матрица,
![$l \neq k$](https://habrastorage.org/getpro/habr/post_images/659/5dc/588/6595dc5887b3cfd900caf0797b6bcaed.svg)
. Тогда уравнение из условия переписывается в виде (если в формуле индекс повторяется дважды, по нему подразумевается
суммирование)
![$ \mbox{tr}AX = A_{ij} X_{ji} = A_{ij} \delta_{ik} \delta_{jl} = A_{kl} = 0\;(k \neq l).$](https://habrastorage.org/getpro/habr/post_images/4af/aed/ca7/4afaedca76f5dce638284bcecf57065a.svg)
То есть, лёгким движением руки мы доказали, что в матрице
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
вне диагонали стоят только ноли. Если отбросить индексы, то мы всего лишь умножили матрицу
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
на матрицу специального вида и получили некое ограничение.
Теперь мы знаем, что матрица
![$A = \mbox{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$](https://habrastorage.org/getpro/habr/post_images/f39/b90/503/f39b90503ad29853fdf658d3eba6b060.svg)
— диагональная. Как доказать, что все её собственные числа равны? Для этого рассмотрим теперь матрицы
![$X = \delta_{i l} \delta_{j l} - \delta_{i k} \delta_{j k}$](https://habrastorage.org/getpro/habr/post_images/4ae/2ac/83b/4ae2ac83b4f2e5751ac776b14332c907.svg)
, то есть матрицы, у которых на
![$l$](https://habrastorage.org/getpro/habr/post_images/ce3/8a8/387/ce38a83878bf16954ea60627fc7c66eb.svg)
-том элементе диагонали стоит
![$+1$](https://habrastorage.org/getpro/habr/post_images/32c/9bd/89d/32c9bd89d8ce46a1b0f690c0ff13efac.svg)
, а на
![$k$](https://habrastorage.org/getpro/habr/post_images/839/452/3d1/8394523d1f4bab66a8544cd365388d87.svg)
-том —
![$-1$](https://habrastorage.org/getpro/habr/post_images/aac/b16/e63/aacb16e63a8798f1407244dd2e99b0f1.svg)
. Аналогично умножив матрицы и взяв след, мы получаем
![$\lambda_l - \lambda_k = 0$](https://habrastorage.org/getpro/habr/post_images/890/2a1/070/8902a1070a30537992bcbfd1c671d2e1.svg)
(след оказался равен всего лишь разности пары собственных чисел). По условию для любых
![$k,\;l$](https://habrastorage.org/getpro/habr/post_images/a87/d46/cd0/a87d46cd0fac4df3709dfacb002391e0.svg)
это равенство должно выполняться, откуда следует, что все собственные числа равны, задача решена.
Задача 2
Придя на письменный экзамен в ШАД, студенты поняли, что среди любых четырёх человек хотя бы один уже знаком с тремя оставшимися. Докажите, что тогда среди любых четырёх человек хотя бы один уже знаком со всеми остальными студентами.
Решение
Эта задача меня чуть не убила, на экзамене я придумал ужасно сложное и убогое решение. Вот оно. Рекомендую в процессе чтения рисовать различные варианты в виде графов, тогда становится даже не так ужасно!
Рассмотрим произвольную четвёрку студентов
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
,
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
,
![$C$](https://habrastorage.org/getpro/habr/post_images/daf/e83/7b2/dafe837b2eb473c8c3a2240b85e4ca80.svg)
,
![$D$](https://habrastorage.org/getpro/habr/post_images/918/0fa/eba/9180faebaa9da51bca81b7ef85e3750f.svg)
. Пусть, от противного, из них никто не знаком со всеми остальными студентами. Но по условию один из студентов (пусть это будет
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
) знает всех оставшихся троих. От противного мы заключили, что есть некий другой студент
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
, которого
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
не знает.
В этом месте сделаем финт ушами и рассмотрим четвёрку
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
,
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
,
![$C$](https://habrastorage.org/getpro/habr/post_images/daf/e83/7b2/dafe837b2eb473c8c3a2240b85e4ca80.svg)
,
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
. В этой четвёрке должен быть студент, который знает всех троих. Это не может быть
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
или
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
, так как они не знакомы, поэтому пусть
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
знает всех троих (не важно, это может быть и
![$C$](https://habrastorage.org/getpro/habr/post_images/daf/e83/7b2/dafe837b2eb473c8c3a2240b85e4ca80.svg)
, пока симметрия между ними не нарушена).
Так как мы работаем от противного, то каждый студент в четвёрке
![$ABCD$](https://habrastorage.org/getpro/habr/post_images/7fb/d6b/d25/7fbd6bd259dc52682d5e1eaf1adc5b7a.svg)
не знает кого-либо. Если в случае с
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
мы были вынуждены взять незнакомца со стороны, то в случае с
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
возможны два случая. Если
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
не знает кого-то изнутри четвёрки
![$ABCD$](https://habrastorage.org/getpro/habr/post_images/7fb/d6b/d25/7fbd6bd259dc52682d5e1eaf1adc5b7a.svg)
, то это может быть только
![$D$](https://habrastorage.org/getpro/habr/post_images/918/0fa/eba/9180faebaa9da51bca81b7ef85e3750f.svg)
, так как
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
и
![$C$](https://habrastorage.org/getpro/habr/post_images/daf/e83/7b2/dafe837b2eb473c8c3a2240b85e4ca80.svg)
он уже знает. Но в этом случае рассмотрим четвёрку
![$AXBD$](https://habrastorage.org/getpro/habr/post_images/ff4/94e/51d/ff494e51defc9dee2c782302dd18b75d.svg)
. С учётом того, что
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
не знает
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
и
![$D$](https://habrastorage.org/getpro/habr/post_images/918/0fa/eba/9180faebaa9da51bca81b7ef85e3750f.svg)
не знает
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
, мы не можем удовлетворить условию о том, чтобы хотя бы один студент в четвёрке знал всех остальных троих.
Таким образом,
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
и
![$D$](https://habrastorage.org/getpro/habr/post_images/918/0fa/eba/9180faebaa9da51bca81b7ef85e3750f.svg)
должны быть знакомы, а у
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
должен быть незнакомый студент со стороны
![$Z$](https://habrastorage.org/getpro/habr/post_images/497/b22/8b6/497b228b649733ffc85046e6ea18cf2f.svg)
. Но тут и наступает конец. Рассмотрим четвёрку
![$ABXZ$](https://habrastorage.org/getpro/habr/post_images/903/27d/413/90327d413de00c9bc814117e9cf42bd1.svg)
. В ней невозможно устроить так, чтобы кто-то знал троих остальных студентов так как незнакомы
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
и
![$X$](https://habrastorage.org/getpro/habr/post_images/6bf/a5b/297/6bfa5b2972cf556a719dca37a543fd04.svg)
,
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
и
![$Z$](https://habrastorage.org/getpro/habr/post_images/497/b22/8b6/497b228b649733ffc85046e6ea18cf2f.svg)
, задача решена.
Задача 3
На окружности выбираются две случайные точки
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
,
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
, найди матожидание площади наименьшего из сегментов, на которые хорда
![$AB$](https://habrastorage.org/getpro/habr/post_images/7d1/9a8/419/7d19a841953f853d1e345322cc51734b.svg)
разбивает круг.
Решение
Как говорилось в одном анекдоте про прапорщика, «а что тут думать? трясти надо!». Зафиксируем точку
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
, а точку
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
параметризуем углом
![$\varphi$](https://habrastorage.org/getpro/habr/post_images/8b1/9d2/72b/8b19d272b7f6d0406846481642a4bc5b.svg)
между радиус-векторами
![$OA$](https://habrastorage.org/getpro/habr/post_images/638/809/8f2/6388098f241e35b10c94d0bdabb9ef3d.svg)
и
![$OB$](https://habrastorage.org/getpro/habr/post_images/677/de6/3f2/677de63f21355abb0e593ce91ddf59f4.svg)
. Рассмотрим углы
![$\varphi \in [0, \pi]$](https://habrastorage.org/getpro/habr/post_images/1ec/a26/c66/1eca26c668bd58ca6e6604de247df7a8.svg)
. Площадь меньшего сегмента тогда будет равна
![$S(\varphi) = \varphi R^2 / 2 - (1/2) R^2 \sin \varphi $](https://habrastorage.org/getpro/habr/post_images/72a/4e3/4e7/72a4e34e768e425638fc64619165abdf.svg)
, тогда
![$\bar{S(\varphi)} = \frac{1}{\pi}\int\limits_{0}^{\pi} d\varphi S(\varphi) = (R^2 / 2 \pi) \int\limits_{0}^{\pi} d\varphi (\varphi - \sin \varphi) = \frac{R^2}{2 \pi} \left(\frac{\pi^2}{2} - 2 \right) = \pi R^2 / 4 - R^2 / \pi.$](https://habrastorage.org/getpro/habr/post_images/af1/998/988/af199898851613c28fc2f0c023ca0cdc.svg)
Задача 4
Дан массив из
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
натуральных чисел. Предложите способ сортировки его по остатку от деления на 5 за линейное время и константную память.
Решение
В этом месте руки похолодели, я-ж не программист! Но спокойно, я же говорил, это экзамен по математике.
Сортировку нужно делать in-place, так как дополнительно можно затратить только константу памяти. Зафиксируем некий текущий остаток
![$r$](https://habrastorage.org/getpro/habr/post_images/6cb/322/9d6/6cb3229d6f195e9a9e27404fa18612c1.svg)
(сначала
![$r = 0$](https://habrastorage.org/getpro/habr/post_images/13b/faa/610/13bfaa610f2ff75b899508784e60ec2b.svg)
, в конце
![$r = 4$](https://habrastorage.org/getpro/habr/post_images/e48/8c0/4e8/e488c04e87d4b0f6102f9361f45ecc30.svg)
) и пойдём по массиву от начала до конца указателем
![$j$](https://habrastorage.org/getpro/habr/post_images/2f5/692/1a2/2f56921a22f6ac2c668ade6c566c68b1.svg)
. Также заведём так называемый индекс вставки
![$i$](https://habrastorage.org/getpro/habr/post_images/721/95b/0db/72195b0dbc8d5e1fbd3b06fd91ae2dba.svg)
, который изначально указывает на начало массива и затем только увеличивается.
Если элемент массива
![$A[j]$](https://habrastorage.org/getpro/habr/post_images/417/f6c/23e/417f6c23e97ea3077eb4add6482d2447.svg)
имеет остаток
![$r$](https://habrastorage.org/getpro/habr/post_images/6cb/322/9d6/6cb3229d6f195e9a9e27404fa18612c1.svg)
, мы должны поменять его местами с
![$A[i]$](https://habrastorage.org/getpro/habr/post_images/2cb/019/2dd/2cb0192dddfdf3dff0650dfa93608ccc.svg)
. После этого индекс
![$i$](https://habrastorage.org/getpro/habr/post_images/721/95b/0db/72195b0dbc8d5e1fbd3b06fd91ae2dba.svg)
мы увеличиваем до тех пор, пока
![$A[i] = r (\mbox{mod}) 5$](https://habrastorage.org/getpro/habr/post_images/a84/2b2/fca/a842b2fca50f7a1a6d5f2ee247d42ae5.svg)
и останавливаем в тот момент, когда это равенство нарушается. Затем снова растим индекс
![$j$](https://habrastorage.org/getpro/habr/post_images/2f5/692/1a2/2f56921a22f6ac2c668ade6c566c68b1.svg)
, пока снова не найдём
![$A[j] = r (\mbox{mod} 5)$](https://habrastorage.org/getpro/habr/post_images/25e/516/6e3/25e5166e3f9fe66a8dd2e752e1449bf9.svg)
, чтобы его перекинуть на позицию
![$i$](https://habrastorage.org/getpro/habr/post_images/721/95b/0db/72195b0dbc8d5e1fbd3b06fd91ae2dba.svg)
.
В данном алгоритме есть некий инвариант, а именно, позади индекса
![$i$](https://habrastorage.org/getpro/habr/post_images/721/95b/0db/72195b0dbc8d5e1fbd3b06fd91ae2dba.svg)
все числа уже расставлены правильно (отсортированы по остатку). При одном проходе
![$j$](https://habrastorage.org/getpro/habr/post_images/2f5/692/1a2/2f56921a22f6ac2c668ade6c566c68b1.svg)
по всему массиву, позади
![$i$](https://habrastorage.org/getpro/habr/post_images/721/95b/0db/72195b0dbc8d5e1fbd3b06fd91ae2dba.svg)
будут лежать все элементы, которые при делении на
![$5$](https://habrastorage.org/getpro/habr/post_images/3e3/d5a/af8/3e3d5aaf81e457b9f29ee0fcb153c3ba.svg)
дают в остатке
![$0$](https://habrastorage.org/getpro/habr/post_images/0fc/031/d00/0fc031d0014dcf57b36106bd16b8e71b.svg)
. При очередном проходе та же участь постигнет тех, кто делится с остатком
![$1$](https://habrastorage.org/getpro/habr/post_images/072/ceb/bbc/072cebbbc068c9c66ce5e423466d257c.svg)
и так далее. Всего потребуется 4 прохода (пятый будет уже не нужен).
Задача 5
Исследуйте на сходимость и абсолютную сходимость ряд
![$\sum\limits_{n = 0}^{+\infty} \sin \pi \sqrt{n^2 + 1}. $](https://habrastorage.org/getpro/habr/post_images/552/fff/631/552fff631d4818d60401374debfa51ab.svg)
Решение
ШАД, ты серьёзно? Ну это-то зачем? Ладно…
Запишем
![$ \sin \pi \sqrt{n^2 + 1} =\sin \pi n \sqrt{1 + 1/n^2} = \sin \left(\pi n + \frac{\pi}{2 n} + \mathcal{o}(n^{-2})\right) = (-1)^n \sin \left( \frac{\pi}{2 n} + \mathcal{o}(n^{-2})\right) = \\ = (-1)^n \left(\frac{\pi}{2 n} + \mathcal{o}(n^{-2}) \right).$](https://habrastorage.org/getpro/habr/post_images/be8/c07/317/be8c073172036e4e7cddc330094ec964.svg)
Видно, что ряд сходится условно. Слагаемое
![$\mathcal{o(n^{-2})}$](https://habrastorage.org/getpro/habr/post_images/ed8/ed7/b29/ed8ed7b29f7f2b537c6c8e4caedea146.svg)
сходится по интегральному признаку, а слагаемое
![$(-1)^n / n $](https://habrastorage.org/getpro/habr/post_images/47e/9d1/082/47e9d1082f6d8002d4c2c616615ee25b.svg)
сходится по признаку Дирихле. Если же рассмотреть абсолютную сходимость, надо вспомнить свойство
![$|a + b| \geqslant |a| - |b|$](https://habrastorage.org/getpro/habr/post_images/41c/804/08d/41c80408d5cee4331676ff4b1a1c448f.svg)
. Слагаемое
![$b = \mathcal{o(n^{-2})}$](https://habrastorage.org/getpro/habr/post_images/95f/f98/933/95ff98933310ef5ae7a07102942b0c00.svg)
всё ещё сходится по тому же интегральному признаку, а вот слагаемое
![$ a \sim 1/n $](https://habrastorage.org/getpro/habr/post_images/cbb/747/c55/cbb747c55cf6367697ad32ac75868522.svg)
расходится как сумма гармонического ряда, и потому весь ряд не сходится.
Задача 6
У вас имеется неограниченное количество костей в виде всех возможных правильных многогранников. Можно ли, однократно просив некоторый набор таких костей, симулировать бросок (а) правильной 7-гранной кости, (б) правильной 15-гранной кости?
Решение
Эту задачу на самом экзамене я не успел даже прочесть, так что это было вроде домашней работы. Всего правильных многогранников пять: пирамида (4), куб (6), октаэдр (8), додекаэдр (12), икосаэдр (20).
Заметим, что мы можем симулировать бросок
![$5$](https://habrastorage.org/getpro/habr/post_images/3e3/d5a/af8/3e3d5aaf81e457b9f29ee0fcb153c3ba.svg)
-гранной кости, беря остаток от деления на пять того, что выпало на икосаэдре. Аналогично, мы можем симулировать бросок трёхгранной кости, деля остаток от деления на
![$3$](https://habrastorage.org/getpro/habr/post_images/865/891/656/8658916560196dd654e1796e33930b49.svg)
от всего, что падает на пирамиде. Тогда, если
![$d_3$](https://habrastorage.org/getpro/habr/post_images/f87/570/94a/f8757094af71bd820a55bc242456a6be.svg)
и
![$d_5$](https://habrastorage.org/getpro/habr/post_images/f30/3e2/cc4/f303e2cc4cc0988bdd18757f64cab8f2.svg)
— результаты бросков таких костей, то результат броска
![$15$](https://habrastorage.org/getpro/habr/post_images/b94/31d/4e5/b9431d4e5e619c243bc6f95afc203587.svg)
-гранной кости мы будем пересчитывать как
![$d_{15} = 5 (d_3 - 1) + d_5.$](https://habrastorage.org/getpro/habr/post_images/f96/f28/94f/f96f2894ffab71c32afa61e2cf4b4882.svg)
Заметим, что здесь все исходы равновероятны, то есть это действительно правильная кость.
Тем не менее, бросок
![$7$](https://habrastorage.org/getpro/habr/post_images/d0f/3e5/2d3/d0f3e52d3e1c7da48cdacb2efe7d790f.svg)
-гранной кости симулировать нельзя. К данному моменту стало ясно, что если у нас честный кубик
![$d_i$](https://habrastorage.org/getpro/habr/post_images/72e/da0/951/72eda0951aaebfc31c3c417f692d1500.svg)
, то мы можем симулировать любые делители
![$i$](https://habrastorage.org/getpro/habr/post_images/721/95b/0db/72195b0dbc8d5e1fbd3b06fd91ae2dba.svg)
, а также, если у нас есть два честных кубика
![$d_i$](https://habrastorage.org/getpro/habr/post_images/72e/da0/951/72eda0951aaebfc31c3c417f692d1500.svg)
и
![$d_j$](https://habrastorage.org/getpro/habr/post_images/87d/e57/902/87de579028ac5ce1052c13e7ab7e2a55.svg)
, мы можем симулировать произведение
![$d_{ij}$](https://habrastorage.org/getpro/habr/post_images/b92/eb5/d6b/b92eb5d6bdb9fedd850f5dc3fe171c03.svg)
. Именно поэтому мы можем просимулировать любое число, раскладывающееся на простые множители
![$2$](https://habrastorage.org/getpro/habr/post_images/443/d68/c67/443d68c67691f683f82fd1247d4c15b7.svg)
,
![$3$](https://habrastorage.org/getpro/habr/post_images/865/891/656/8658916560196dd654e1796e33930b49.svg)
и
![$5$](https://habrastorage.org/getpro/habr/post_images/3e3/d5a/af8/3e3d5aaf81e457b9f29ee0fcb153c3ba.svg)
(других среди платоновых тел нет).
Предположим, что мы хотим просимулировать число, которое не раскладывается на произведение таких простых множителей. Кинем для этого
![$N$](https://habrastorage.org/getpro/habr/post_images/644/86c/eab/64486ceabd5fd2c0d8f3df3093ef55bc.svg)
костей
![$d_{i_1},\;d_{i_2},\;\ldots,\;d_{i_N}$](https://habrastorage.org/getpro/habr/post_images/67f/d1a/4a6/67fd1a4a61f20a9b5d10b7ff68390e5b.svg)
, и числа, выпавшие на всех
![$N$](https://habrastorage.org/getpro/habr/post_images/644/86c/eab/64486ceabd5fd2c0d8f3df3093ef55bc.svg)
костях, запишем в один вектор, описывающий точку в гиперкубе размером
![$i_1\times i_2 \times \ldots \times i_N$](https://habrastorage.org/getpro/habr/post_images/82e/ee3/992/82eee39920eeaddc221c5341c06b99a7.svg)
. Если мы хотим симулировать
![$7$](https://habrastorage.org/getpro/habr/post_images/d0f/3e5/2d3/d0f3e52d3e1c7da48cdacb2efe7d790f.svg)
-гранную кость, мы должны точки в этом пространстве поделить на
![$7$](https://habrastorage.org/getpro/habr/post_images/d0f/3e5/2d3/d0f3e52d3e1c7da48cdacb2efe7d790f.svg)
групп равного размера, что сделать нельзя, ведь иначе произведение
![$i_1\times i_2 \times \ldots \times i_N$](https://habrastorage.org/getpro/habr/post_images/82e/ee3/992/82eee39920eeaddc221c5341c06b99a7.svg)
должно будет делиться на
![$7$](https://habrastorage.org/getpro/habr/post_images/d0f/3e5/2d3/d0f3e52d3e1c7da48cdacb2efe7d790f.svg)
, а такого мы ещё не получили.
Задача 7
Пусть
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
,
![$B$](https://habrastorage.org/getpro/habr/post_images/9e8/a3f/eee/9e8a3feeef98454766ed27af3effec45.svg)
— квадратные вещественные матрицы. Доказать, что
Решение
Здесь мне очень помогла формула, которую ужасно любят в теор. физике, и я сильно рекомендую её взять на вооружение тем, кто пойдёт на экзамен. Для любой матрицы
![$A$](https://habrastorage.org/getpro/habr/post_images/3ce/765/ddd/3ce765dddc59fdb7834b8831b784f9d9.svg)
, у которой все собственные значения положительны, справедливо
Как же здесь применить нашу формулу? Я скажу сразу, мы будем раскладывать логарифм в ряд. Под логарифмом у нас будет стоять выражение вида
![$E - AB$](https://habrastorage.org/getpro/habr/post_images/a2a/41f/348/a2a41f3485c37b242b7a6f67b3d7838e.svg)
, которое можно раскладывать в ряд, только если
![$|AB|_2 < 1$](https://habrastorage.org/getpro/habr/post_images/19b/2c9/f54/19b2c9f54a25463a893c1d8f92617b08.svg)
. Это совершенно полностью соответствует радиусу сходимости логарифма, но только во многомерном пространстве.
Для начале давайте переформулируем задание и докажем, что
![$ \mbox{det}\left(E - \lambda AB\right) = \mbox{det}\left(E - \lambda BA\right) $](https://habrastorage.org/getpro/habr/post_images/b7b/4d2/0bd/b7b4d20bdf746a6df0995f377320abb2.svg)
для любого вещественного числа
![$\lambda$](https://habrastorage.org/getpro/habr/post_images/d1d/2ad/058/d1d2ad058a6e91cc85fd05d7403b9837.svg)
, и дальше просто возьмём
![$\lambda = 1.$](https://habrastorage.org/getpro/habr/post_images/018/115/d35/018115d35f6cd6b4aa4c0c3f4ef3ade5.svg)
Зачем это нужно? Это нужно для того, чтоб сделать норму матриц
![$|AB|_2$](https://habrastorage.org/getpro/habr/post_images/cd5/0cf/790/cd50cf7904e0c7478f0424e6c2212cdf.svg)
меньше
![$1$](https://habrastorage.org/getpro/habr/post_images/072/ceb/bbc/072cebbbc068c9c66ce5e423466d257c.svg)
. Когда рассмотрено очень маленькое
![$\lambda$](https://habrastorage.org/getpro/habr/post_images/d1d/2ad/058/d1d2ad058a6e91cc85fd05d7403b9837.svg)
, можно смело написать такую цепочку (под следом матрицы можно передвигать по циклу):
![$\mbox{det}\left(E - \lambda AB\right) = \exp \mbox{tr} \log(E - \lambda AB) = \exp \mbox{tr}\left(-\lambda AB - \frac{\lambda^2 (AB)^2}{2} - \frac{\lambda^3 (AB)^3}{3} - \ldots\right) = \\ = \exp \mbox{tr}\left(-\lambda BA - \frac{\lambda^2 (BA)^2}{2} - \frac{\lambda^3 (BA)^3}{3} - \ldots\right) = \mbox{det}(E - \lambda BA).$](https://habrastorage.org/getpro/habr/post_images/d83/378/790/d83378790e0df4de025e03459c798cf5.svg)
Здесь мы нагло использовали свойство
Хорошо, мы доказали эту формулу для некоторого отрезка
![$\lambda$](https://habrastorage.org/getpro/habr/post_images/d1d/2ad/058/d1d2ad058a6e91cc85fd05d7403b9837.svg)
вблизи ноля. Как же теперь распространить её на все
![$\lambda$](https://habrastorage.org/getpro/habr/post_images/d1d/2ad/058/d1d2ad058a6e91cc85fd05d7403b9837.svg)
, в частности
![$\lambda = 1$](https://habrastorage.org/getpro/habr/post_images/78d/b8c/4ce/78db8c4ceae670b2fb49a4c449810784.svg)
? Заметим, что в левой и правой части доказанной формулы стоят многочлены по
![$\lambda$](https://habrastorage.org/getpro/habr/post_images/d1d/2ad/058/d1d2ad058a6e91cc85fd05d7403b9837.svg)
(ведь в определитель входят только произведения)! То есть, мы доказали, что два многогочлена совпадают на отрезке, но отсюда сразу следует, что они совпадают всюду на числовой прямой.
Задача 8
За столом сидят
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
старателей, перед каждым из которых лежит кучка золотого песка. Каждую минуту все старатели берут половину песка из левой кучки и половину из правой кучки и кладут себе. Опишите асимптотическое поведение количества песка в кучках для произвольного
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
.
Решение
По сути, нам предлагается найти асимптотику решения вот такой разностной схемы (для любых начальных условий):
![$a(x, t + 1) = \frac{a(x - 1, t) + a(x + 1, t)}{2},$](https://habrastorage.org/getpro/habr/post_images/c1c/075/619/c1c07561973c45f397aace659f333eb9.svg)
где
![$a(x, t)$](https://habrastorage.org/getpro/habr/post_images/d73/3f4/628/d733f4628c715cdafd6b4869f1439b6e.svg)
— количество золота у старателя, сидящего в позиции
![$x$](https://habrastorage.org/getpro/habr/post_images/baa/dee/944/baadee9444d136cdabc2792cdd7d0b6b.svg)
во время
![$t$](https://habrastorage.org/getpro/habr/post_images/9b6/547/e8d/9b6547e8d3f9c2d6f92fbc781ac55660.svg)
. Координата
![$x$](https://habrastorage.org/getpro/habr/post_images/baa/dee/944/baadee9444d136cdabc2792cdd7d0b6b.svg)
замкнута в окружность,
![$x = 0, 1, \ldots, n - 1$](https://habrastorage.org/getpro/habr/post_images/1fd/c73/db7/1fdc73db76d8b637e737100c63dc260e.svg)
.
Такие вещи решаются множеством способов, но самый естественный — дискретное преобразование Фурье. Мы имеем дело с функцией, периодической по
![$x$](https://habrastorage.org/getpro/habr/post_images/baa/dee/944/baadee9444d136cdabc2792cdd7d0b6b.svg)
, и её можно и нужно разложить в конечную сумму Фурье по
![$x$](https://habrastorage.org/getpro/habr/post_images/baa/dee/944/baadee9444d136cdabc2792cdd7d0b6b.svg)
:
![$a(x, t) = \frac{1}{N} \sum\limits_{k = 0}^{n - 1} \sum\limits_{\omega = 0}^{T - 1} \tilde{a}(k, t) e^{2 \pi i k x / n} .$](https://habrastorage.org/getpro/habr/post_images/717/060/b1b/717060b1b4c903c82ba38a5f073defce.svg)
Это хозяйство должно удовлетворять нашему разностному уравнению, поэтому подставим эту сумму в уравнение явно и потребуем, чтоб коэффициенты при всех экспонентах слева и справа совпадали. По сути, мы просто сделали замену базиса (перешли к плоским волнам) и требуем, чтобы и в новом базисе у нас коэффициенты перед базисными векторами совпадали. Это приводит к уравнению
![$ \tilde{a}(k, t + 1) = \frac{e^{2 \pi i k / n}\tilde{a}(k, t) + e^{-2 \pi i k / n}\tilde{a}(k, t)}{2} = \cos(2 \pi k /n)\tilde{a}(k, t).$](https://habrastorage.org/getpro/habr/post_images/d29/6fb/5ba/d296fb5badc0d267909541e250c60c66.svg)
Для фиксированного
![$k$](https://habrastorage.org/getpro/habr/post_images/839/452/3d1/8394523d1f4bab66a8544cd365388d87.svg)
это само по себе уравнение, которое аналогично решается ещё одним преобразованием Фурье. Будем обозначать преобразование Фурье по координате тильдой, а по координате + времени — крышечкой. Записав
![$\tilde{a}(k, t) = \frac{1}{T}\sum\limits_{\omega = 0}^{T - 1} \hat{a}(k, \omega)e^{2 \pi i \omega t / T},$](https://habrastorage.org/getpro/habr/post_images/1ce/245/b93/1ce245b936945f284a3478119e2c828d.svg)
подставив это в последнее уравнение и снова уравняв экспоненты, мы получаем
![$e^{2 \pi i \omega} = \cos (2 \pi i k).$](https://habrastorage.org/getpro/habr/post_images/0aa/218/162/0aa2181626bf545a566c7cb4925fad77.svg)
Мы получили так называемое дисперсионное соотношение. То есть, плоские волны здесь могут быть не с произвольными
![$k,\;\omega$](https://habrastorage.org/getpro/habr/post_images/3a5/5cf/917/3a55cf917ccf34dba67aa3b502db5c12.svg)
, а только с теми, которые подчиняются этой формуле. Это дисперсионное соотношение — переформулировка исходного уравнения в новом базисе. Пусть мы зафиксировали какой-то импульс
![$k$](https://habrastorage.org/getpro/habr/post_images/839/452/3d1/8394523d1f4bab66a8544cd365388d87.svg)
и пытаемся найти соответствующую частоту
![$\omega$](https://habrastorage.org/getpro/habr/post_images/cba/754/e4b/cba754e4ba9b0c652fb65151779dbf4d.svg)
, которая может существовать в такой системе.
Если косинус справа по модулю будет меньше единицы, то в комплексную экспоненту придётся подставлять комплексную частоту
![$\omega = \omega' + i \omega''$](https://habrastorage.org/getpro/habr/post_images/e40/395/784/e4039578439d5899db9e40b1064f7575.svg)
(у которой будет мнимая часть). Как легко видеть, мнимая часть этой экспоненты тогда будет положительной (
![$\omega'' > 0$](https://habrastorage.org/getpro/habr/post_images/e38/023/5f5/e380235f58f128ce4f8d92e1faa9497a.svg)
), тогда в экспоненту она войдёт как
![$-2 \pi \omega'' / T$](https://habrastorage.org/getpro/habr/formulas/33b/523/9d5/33b5239d583f9a88ab062c6d9161d3f2.svg)
и уменьшит её модуль вслед за косинусом. Но, к счастью, такие частоты быстро отправятся на покой. Действительно, если мы посмотрим, какой вклад будут давать моды с такими частотами, мы увидим, что они будут по времени экспоненциально затухать. Такие моды в асимптотику давать вклада не будут.
Поэтому у нас остаётся два случая. Если
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
— нечётное, то косинус бывает равным
![$1$](https://habrastorage.org/getpro/habr/post_images/072/ceb/bbc/072cebbbc068c9c66ce5e423466d257c.svg)
по модулю лишь однажды, когда
![$k = 0$](https://habrastorage.org/getpro/habr/post_images/6b3/ca9/6e8/6b3ca96e8e4ff1e8c2e700d32f299576.svg)
. В этом случае
![$\omega = 0$](https://habrastorage.org/getpro/habr/post_images/f29/310/9d5/f293109d569f9a42f79022c44976631e.svg)
. Эта плоская волна — всего лишь среднее. Получается, при нечётных
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
никакой антересной динамики в бесконечности нет: богатство старателей сходится к среднему от того, что было изначально:
![$ a(x, t) \to \frac{1}{N} \sum\limits_{b = 0}^{n - 1} a(b, 0).$](https://habrastorage.org/getpro/habr/post_images/bcb/1c4/925/bcb1c4925b3219cfe4bfecc47f751107.svg)
Если же
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
нечётное, то косинус ещё может быть равен
![$-1$](https://habrastorage.org/getpro/habr/post_images/aac/b16/e63/aacb16e63a8798f1407244dd2e99b0f1.svg)
, если
![$k = n / 2$](https://habrastorage.org/getpro/habr/post_images/eaf/58e/d6e/eaf58ed6e85533d50150d611b14e5422.svg)
, а тогда возможно дополнительное решение
![$\omega = T / 2,\; \tilde{a}(k, t) = \hat{a}(k, T / 2) (-1)^t/ T$](https://habrastorage.org/getpro/habr/post_images/7a1/60b/c13/7a160bc1304d2a57d7138ab52d7b9d6c.svg)
(в сумме выживает только слагаемое, в котором вещественная
![$ \omega $](https://habrastorage.org/getpro/habr/post_images/cba/754/e4b/cba754e4ba9b0c652fb65151779dbf4d.svg)
, его мы и записали). В этом случае
![$a(x, t) = \frac{1}{N} a(n / 2, t) = \frac{1}{NT} (-1)^x (-1)^t \hat{a}(n / 2, T / 2).$](https://habrastorage.org/getpro/habr/post_images/046/f9a/abc/046f9aabc4fe8434f19c719f2bf5437f.svg)
Аналогично остаётся всего одно слагаемое, его и пишем. Теперь про решение нам почти всё известно. Это некая вот такая конструкция, которая меняет знак как при шаге по времени, так и при шаге по пространству. Заметьте, что если бы здесь
![$n$](https://habrastorage.org/getpro/habr/post_images/17e/d16/be1/17ed16be17023e4cd19584781c333593.svg)
не было чётным, это бы нарушило цикличность по окружности. Осталось только найти значение коэффициента.
Взглянем на обратное преобразование Фурье:
![$\hat{a}(n / 2, T / 2) (-1)^t / T= \tilde{a}(n / 2, t) = \sum\limits_{x = 0}^{n - 1} a(x, t) e^{-2 \pi i (n / 2) x / n}.$](https://habrastorage.org/getpro/habr/post_images/0dc/dd1/634/0dcdd16348c3c3fb78721ffe1bcd800b.svg)
При
![$t = 0$](https://habrastorage.org/getpro/habr/post_images/74b/79b/71d/74b79b71d92f301e4740542223d40cb0.svg)
слева стоит
![$\hat{a}(k, \omega) / T$](https://habrastorage.org/getpro/habr/post_images/755/05b/e51/75505be51f7ea37b9b38950d54f500fb.svg)
, а справа стоит просто
![$\sum\limits_{x = 0}^{n - 1} a(x, 0) (-1)^x$](https://habrastorage.org/getpro/habr/post_images/406/40b/8dd/40640b8ddd99ff2a9799705ed2e1af9a.svg)
, то есть альтернированная сумма богатств в исходный момент времени. Таким образом, мы получаем
![$ a(x, t) \to \frac{(-1)^x (-1)^t}{N}\sum\limits_{b = 0}^{n - 1} a(b, 0) (-1)^b + \frac{1}{N} \sum\limits_{b = 0}^{n - 1} a(b, 0).$](https://habrastorage.org/getpro/habr/post_images/b02/ff6/420/b02ff642023f7b6a0c5768684e8816fe.svg)
Послесловие
За контрольную дали семь очков из восьми. Я не написал про трюк с
![$\lambda$](https://habrastorage.org/getpro/habr/post_images/d1d/2ad/058/d1d2ad058a6e91cc85fd05d7403b9837.svg)
в задаче про матрицы, а просто раскладывал — этого не заметили. Затем было собеседование. Меня ничего не спросили про экзамен, просто поговорили за жизнь, зачем я хочу поступать в ШАД (подготовьте ответ на этот вопрос!). Ребят, у кого было поменьше задач, просили решать что-то на месте, так тчо лучше придти в боевом расположени духа. Также будет возможность отапеллировать недоставленных за контрольную очков.
Обучение в ШАД мне сильно-сильно понравилось. Здесь всё время толкают какую-то теорию, читают по самым свежим статьям, а не по 50-летним книгам, и, самое главное, теория всегда подкреплена очень подходящей и логичной практикой.
Плюсы:
- Очень крутые курсы, разбегаются глаза: есть на любой вкус, от очень практических до очень теоретических, почти все современные отрасли компьютерных наук по свежим статьям.
- Преподаватели в основной массе огонь, не лень было после лабы вечером ехать на другой конец Москвы послушать.
- Классная подача материала, всё записывается на видео, можно не ходить. Сдавать можно удалённо, но ходить всё равно хочется.
- Здоровские однокурсники!
Как таковых, минусов я даже и не заметил. Кураторы ко всем относятся по-доброму, не торопятся отчислять. В Яндексе (помещениях Мамонтова) очень приятная атмосфера, кондиционеры, вкусняшки, удобные кресла, человеческая обстановка! И, главное, довольно большая свобода в выборе курсов и своего профиля даже в рамках выбранной специальности.
Поступайте в ШАД! И, да, забыл, разберитесь обязательно с формулой полного разложения определителя
![$ \mbox{det} A = \epsilon^{i_1 i_2 i_3\ldots i_N} a_{1 i_1} a_{2 i_2} \ldots a_{N i_N}.$](https://habrastorage.org/getpro/habr/post_images/ad3/04b/740/ad304b740b41ab04fe9281f2b6b4e883.svg)