понедельник, 20 августа 2012 г.

Без одинаковых углов

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

В общем случае, требуется раскрасить квадратную сетку NxN в С цветов так, чтобы ни у одного прямоугольника с вершинами в ячейках сетки и сторонами, параллельным её линиям, не оказалось четырёх одноцветных углов. Участники конкурса для данного С ищут максимально возможные N и соответствующие раскраски.

Например, самым большим квадратом, который можно раскрасить в два цвета требуемым образом, будет квадрат 4 на 4:



Для трёх цветов наибольшим квадратом будет 10x10 (автор Tom Sirgedas).


Но уже для пяти цветов появляется открытая проблема. Известно решение для квадрата 25 на 25. Известно, что нет решения для квадрата 28 на 28. А вот для промежуточных значений - ведётся поиск. Если раскраска пятью красками квадрата со стороной 27 существует, один из цветов должен располагаться так:


Может быть, у вас получится найти расположение остальных?

Кроме всеобщего признания, участие в конкурсе приносит и эстетическое наслаждение. Взгляните только, какой изумительный ковёр получила Наталия для 11 цветов и N = 121
Страница конкурса
Обсуждение конкурса на русскоязычном математическом форуме

суббота, 18 августа 2012 г.

Синус половинного угла

Синус двойного угла равен удвоенному произведению синуса и косинуса угла:
sin2a = 2 sina cosa

Попробуем теперь получить формулу синуса половинного угла. Для этого используем тригонометрическую единицу:
1 = sin2a + cos2a

И косинус двойного угла:
cos2a = cos2a - sin2a

Вычтем почленно эти выражения:
1 - cos2a = 2 sin2a

Отсюда:
синус половинного угла

Так как слева угол вдвое меньший, чем справа, то формулу можно переписать и как:
синус половинного угла

Аналогично косинус половинного угла выражается так:
косинус половинного угла

А теперь начинается самое интересное. С помощью этих формул покажем, как из бесконечного корня из предыдущего поста вылезает пи.

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

А теперь возьмём угол альфа, равным
  доказательство

 Тогда его синус будет равен: доказательство

С ростом n этот угол будет стремиться к нулю. А, согласно первому замечательному пределу, синус малых углов равен самому углу в радианах, т.е. для стремящегося к бесконечности n, получим:

доказательство

Отсюда и выходит предыдущий удивительный результат.

четверг, 16 августа 2012 г.

Неожиданное пи

Возьмём двойку. Извлечем из неё корень. К результату прибавим двойку, и снова извлечём корень. И ещё раз, и ещё. Если продолжать данный процесс до бесконечности, в пределе получим также двойку:

последовательность корней стремится к двойке


Ну, это достаточно известный факт. А про следующее неожиданное свойство я, например, не знал. Продолжим преобразования:
  предел равен 0
предел равен 0

Пока ничего замечательного. Но стоит подпредельный корень умножить на 2n+1, как получим:
  предел равен пи
Неожиданно, правда?!

среда, 15 августа 2012 г.

Лемма Карно

Для доказательства перпендикулярности отрезков AB и CD на плоскости иногда удобно воспользоваться тем, что в таком случае будет выполняться равенство:
AC2-AD2=DC2-BD2

Доказывается лемма Карно методом координат.

понедельник, 13 августа 2012 г.

Числа Серпинского

Число 78557 интересно тем, что среди чисел вида 78557*2n+1 не будет ни одного простого. Числа, формирующие таким образом последовательности составных, называются числами Серпинского.

Для числа 78557 неизвестно, является ли оно наименьшим из подобных чисел. Другие кандидаты на то, чтобы быть наименьшим числом Серпинского, это: 10223, 21181, 22699, 24737, 55459 и 67607.

воскресенье, 12 августа 2012 г.

Незаконные числа

Оказывается, есть и такие! Суть вот в чём. Любое число, записанное текстом, можно прочитать как последовательность байтов, в которой каждый байт соответствует коду цифры или разделяющего символа в ASCII-формате.

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

Согласно законам США, распространять такие программы незаконно в любом виде. Поэтому Фил Кармоди, автор одного из первых подобных чисел, нашёл остроумное решение, позволяющее публикацию. Дело в том, что из-за особенностей работы архиватора gzip, архив, описываемый числом k, и описываемый числом вида  k*256n+b (n>b) дадут при разархивации одинаковые результаты.

Если подобрать n и b такими, чтобы в итоге получилось достаточно большое простое число, его можно будет вполне законно опубликовать, например, на сайте Prime Pages как интересный научный результат ( а то, что после некоторых операций из числа можно получить программу для копирования лицензионных дисков - дело десятое).

Первое полученное незаконное простое число, 1401-значное, оказалось слишком маленьким, чтобы попасть в список самых длинных. Вот оно:
4 85650 78965 73978 29309 84189 46942 86137 70744 20873 51357 92401 96520 73668 69851 34010 47237 44696 87974 39926 11751 09737 77701 02744 75280 49058 83138 40375 49709 98790 96539 55227 01171 21570 25974 66699 32402 26834 59661 96060 34851 74249 77358 46851 88556 74570 25712 54749 99648 21941 84655 71008 41190 86259 71694 79707 99152 00486 67099 75923 59606 13207 25973 79799 36188 60631 69144 73588 30024 53369 72781 81391 47979 55513 39994 93948 82899 84691 78361 00182 59789 01031 60196 18350 34344 89568 70538 45208 53804 58424 15654 82488 93338 04747 58711 28339 59896 85223 25446 08408 97111 97712 76941 20795 86244 05471 61321 00500 64598 20176 96177 18094 78113 62200 27234 48272 24932 32595 47234 68800 29277 76497 90614 81298 40428 34572 01463 48968 54716 90823 54737 83566 19721 86224 96943 16227 16663 93905 54302 41564 73292 48552 48991 22573 94665 48627 14048 21171 38124 38821 77176 02984 12552 44647 44505 58346 28144 88335 63190 27253 19590 43928 38737 64073 91689 12579 24055 01562 08897 87163 37599 91078 87084 90815 90975 48019 28576 84519 88596 30532 38234 90558 09203 29996 03234 47114 07760 19847 16353 11617 13078 57608 48622 36370 28357 01049 61259 56818 46785 96533 31007 70179 91614 67447 25492 72833 48691 60006 47585 91746 27812 12690 07351 83092 41530 10630 28932 95665 84366 20008 00476 77896 79843 82090 79761 98594 93646 30938 05863 36721 46969 59750 27968 77120 57249 96666 98056 14533 82074 12031 59337 70309 94915 27469 18356 59376 21022 20068 12679 82734 45760 93802 03044 79122 77498 09179 55938 38712 10005 88766 68925 84487 00470 77255 24970 60444 65212 71304 04321 18261 01035 91186 47666 29638 58495 08744 84973 73476 86142 08805 29443.

А опубликовать удалось чуть позднее 1905-ти значное простое число. Эта публикация, кроме всего прочего, позволила Филу избежать ответственности за собственно создание незаконной программы.

Wikipedia

Популярные сообщения

Темы

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