🔴🔵Задача «никакие три точки не лежат на одной прямой» — одна из задач комбинаторной геометрии, состоящая в нахождении количества точек, которые можно расположить на решётке n×n так, чтобы никакие три точки не находились на одной прямой.

Брасс, Мозер и Пах назвали задачу «одним из самых старых и интенсивно изучаемых геометрических вопросов, касающихся точек решётки»

#математика #math #геометрия #графика #наука #дискретная_математика #графы #задачи

💡 Physics.Math.Code // @physics_lib

#️⃣ Обычный поиск VS Квантовый поиск

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

Поисковые алгоритмы, основанные на квантовых прогулках, могут найти применение в различных областях, включая оптимизацию, машинное обучение, криптографию и сетевой анализ. Эффективность и вероятность успеха квантового поиска сильно зависят от структуры пространства поиска. В целом, алгоритмы квантового поиска обеспечивают асимптотическое квадратичное ускорение, аналогичное алгоритму Гровера. Одна из первых работ по применению квантового блуждания к задачам поиска была предложена Нилом Шенви, Джулией Кемпе и К. Биргиттой Уэйли. #математика #math #геометрия #графика #наука #алгоритмы #дискретная_математика #графы #задачи #программирование

💡 Physics.Math.Code // @physics_lib

🌐 Математическая загадка: сфера и 5 точек на поверхности

Если на поверхности сферы есть 5 точек, то существует замкнутая полусфера, содержащая по крайней мере 4 из них.

Задача: На сфере отмечено пять точек, никакие три из которых не лежат на большой окружности (большая окружность – это окружность, по которой пересекаются сфера и плоскость, проходящая через её центр). Две большие окружности, не проходящие через отмеченные точки, называются эквивалентными, если одну из них с помощью непрерывнвого перемещения по сфере можно перевести в другую так, что в процессе перемещения окружность не проходит через отмеченные точки.
а) Сколько можно нарисовать окружностей, не проходящих через отмеченные точки и не эквивалентных друг другу?
б) Та же задача для n отмеченных точек.

Решение:
а) Перейдём к двойственным объектам: каждой окружности соответствует такая пара противоположных точек сферы, что соединяющий их диаметр перпендикулярен этой окружности; наоборот, каждой точке соответствует большая окружность. Тогда задача сводится к двойственной: точки считаются эквивалентными, если можно одну перевести в другую, не задевая пяти данных больших окружностей (никакие три из которых не пересекаются в одной точке). Очевидно, точку можно перемещать в пределах области, на которые большие окружности делят сферу. Таким образом, число классов эквивалентности в два раза меньше числа частей, на которые большие окружности делят сферу (противоположным частям соответствует один класс, так как исходной большой окружности в двойственной задаче соответствуют две диаметрально противоположные точки).
Учтем, что n наших больших окружностей делят сферу на n² – n + 2 части. В частности, пять окружностей разобьют сферу на 22 части. А ответ, как показано выше, в два раза меньше.
б) см. а)

#геометрия #видеоуроки #олимпиады #problems #задачи #опыты #эксперименты #math

💡 Physics.Math.Code // @physics_lib