Мини-QR-викторина✅

Билет на киносеанс, афиша, меню в ресторане, а некогда даже пропуск на улицу, — QR-коды давно стали частью нашей реальности. И развитие этой технологии тоже не обошлось без математики.

Внутри простых «узоров из квадратиков» скрыт целый мир чисел. Предлагаем проверить, насколько хорошо вы в нём разбираетесь.

Проходите мини-опрос, а завтра мы расскажем, какая математика прячется в чёрно-белых узорах ⤵️

Как устроены QR-коды❓

Спасибо всем, кто вчера прошёл нашу мини-викторину! Было приятно видеть много правильных ответов. Теперь рассказываем подробнее, какая математика скрывается в чёрно-белых квадратиках.

🟢Двумерное кодирование

QR-код устроен как матрица из чёрных и белых модулей. Чтобы сканер не запутался, где верх и низ, в углах есть большие маркеры, а внутри — синхронизирующие линии. Каждый квадрат модуля кодирует 0 или 1. Такая система координат позволяет «поставить сетку» и правильно считать биты информации.

🟢От битов к многочленам

Чтобы хранить текст или ссылку, одних нулей и единиц мало — нужны способы защитить данные от ошибок. И здесь в дело вступает высшая математика. Информация в QR-коде представляется как последовательность чисел, а они, в свою очередь, — как коэффициенты многочлена. Приведём пример:

Сообщение «HELLO» можно легко превратить в многочлен: M(x) = 72x⁴ + 69x³ + 76x² + 76x + 79. Коэффициенты здесь — это ASCII-коды букв.

Текст «ABC» тоже может стать многочленом: 65 + 66x + 67x², в котором ASCII-коды A, B, C — 65, 66 и 67, соответственно.

В реальных QR-кодах преобразование текста выполняется не так прямолинейно. Но идея кодирования именно та. И появилась она, потому что с многочленами удобно работать в рамках конечных полей.

🟢Конечное поле

Его ещё называют полем Галуа, по имени Эвариста Галуа. Это система чисел, в которой сложение, умножение и деление замкнуты внутри ограниченного набора элементов. Например, поле из 256 элементов — GF(256) — выбирают
для работы с байтами.

В QR-кодах вычисления тоже происходят в GF(256). Из этого поля берут коэффициенты многочленов, и арифметика становится очень эффективной. Числа складываются и умножаются «по модулю», так что даже при ошибках восстанавливается строгая структура.

🟢«Страховочные» коэффициенты

Или, по-другому, контрольные символы. Их добавляют к исходному многочлену M(x), чтобы QR-код был устойчив к повреждениям. Это делают с помощью кодов Рида–Соломона:

Если у вас есть многочлен степени k–1, то для его однозначного восстановления достаточно знать его значения в k точках. А если вы знаете его значения в большем числе точек, то даже при потере части из них многочлен можно восстановить.

В QR-коде данные «записываются» в виде значений многочлена в разных точках конечного поля. А дальше сканер решает обратную задачу: восстанавливает многочлен по частично повреждённым данным.

Этот процесс напоминает интерполяцию: как если бы вы знали несколько точек на параболе и могли восстановить всю кривую. Современные QR-коды можно восстановить при повреждении до 30% площади!

🟢Комбинаторика масштабов

Даже небольшой QR-код на 21×21 модуль содержит миллиарды комбинаций. А более крупные версии уходят в масштабы чисел, сопоставимых с количеством атомов во Вселенной.

Так что каждый раз, когда ваш телефон безошибочно считывает QR-код с потрёпанной временем и погодой афиши, он фактически решает задачу алгебраической интерполяции в конечном поле.

Правда, иногда технология может оказаться избыточной. Яркий пример — QR-часы: вместо времени они показывают код, который нужно отсканировать, чтобы узнать, который час. Полезно разве что в мире без смартфонов.

По ссылке вы найдёте крутую англоязычную настолку. В ней нужно восстановить QR-коды и решить головоломку. Правила можно прочитать здесь, а скачать листы с заданиями тут.

#как_устроено

Где прячется центр круга❓

Задача сегодня будет простая, но интересная: у вас есть лист бумаги. На нём нарисована окружность. Нужно найти её центр, используя только сгибы бумаги.

❎Линейку и циркуль использовать нельзя — в вашем распоряжении только бумага, руки и смекалка.

Пробуйте и показывайте результаты в комментариях под спойлером.

🟢А если справились, здесь лежит ещё одна задача с бумагой. Решайте!

#задача