Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 16
Разбиение ряда на группы - прикольная тема. Я вот что вспомнил: как разбить весь натуральный ряд (все целые больше 0) на 6 групп, так чтобы для любого k, числа k, 2k, 3k, 4k, 5k и 6k попадали в разные группы. Там тоже простое изящное решение в духе статьи.
Спасибо, посижу подумаю
Для числа k, выделим все степени 7: k = 7^m*b, b % 7 != 1. Положим число в группу b % 7 (от 1 до 6).
При умножении на 1-6 максимальная степень 7 в числе останется m. Поэтому x*k (1 <= x <= 6) пойдет в группу (x*b)%7. при чем b%7 != 0, x%7 != 0. Все 6 чисел будут разными, потому что таблица умножения ненулевых чисел по модулю 7 имеет перестановки в каждой строке или столбце. Это потому что умножение по модулю 7 обратимо, ведь 7 - простое число.
Это можно заметить, если руками распихать первые 6 чисел и ими порожденные числа. Там почти однозначно числа распределяются по модулю 7. И тогда остается вопрос, что делать с числами, делящимеся на 7.
И тогда остается вопрос, что делать с числами, делящимеся на 7
Да, этот момент всё портит) Пока не уверен, что здесь можно пофиксить.
Моё решение немного другое
Нет, понятно же. Поделить на 7, пока делится. Я тут имел ввиду, что я не знаю, как я до этого додумался.
А, понял. Да, согласен, решение рабочее. Можно ли его обобщить на N групп (по которым распределяются числа k, 2k, ..., N*k)?
Мой вариант для 6 групп: определяем в числе степени множителей 2, 3 и 5, пусть это будут a, b, c. Тогда число попадает в группу (a + 3b + 5c) % 6. Для N групп надо рассматривать степени всех простых множителей меньше N, но не совсем понятно, как подобрать коэффициенты для суммы..
Можно ли его обобщить на N групп (по которым распределяются числа k, 2k, ..., N*k)?
Если N+1 простое - мой метод работает как есть.
Для непростых N+1 - уже нет. Но не факт что такие разбиения вообще всегда существуют. Хотя я контрпримеров пока не нашел.
определяем в числе степени множителей 2, 3 и 5,
Вообще, логично. Все множители 1..N только меняют степени у этих чисел, поэтому числа с разными другими простыми множителями никогда и никак не получатся вместе, а значит у нас бесконечно идентичных компонент связности в графе конфликтов. Если мы как-то расположим только числа с этими простыми делителями. мы можем скопировать это решение на все оставшиеся компоненты. Кстати, это еще показывает, что решений бесконечно много, если они есть, даже без учета перестановок N групп. Можно брать разную перестановку в каждой отдельной компоненте связности.
(1,2),(3,4),(5,6)… ?
Я нашел нестандартный способ решения задачи.
Искусство мысли учит нас, что некоторые задачи имеют много решений, одно из которых - лучшее. Обычно «лучшее» обозначает «самое простое по конструкции».
Решенная вами задача объективно примитивна. Любой матшкольник с минимальным опытом теории чисел с легкостью придумает десятки конструкций типа вашей. Во всех них в каждой группе будет по одному четному числу, а нечетные могут быть разложены по разнообразным принципам, потому что число степеней свободы разложить эти числа по группам очень велико комбинаторно. Я думаю, что если вы будете раскладывать случайно, после чего возьмете неподходящие и переложите их и так будете повторять несколько итераций, то все равно быстро подберете подходящую конфигурацию.
Ваша задача имеет околонулевную сложность решения.
В таких обстоятельствах следует найти самое простое по конструкции решение. Я считаю, что это решение: разложить по парам, последовательно. Правда, оно показывает тривиальность вашей задачи и ее недостойность статьи, но это уже другой вопрос.
Хотите настоящий вызов? Представьте, что на условие наложено дополнительное требование: числа в группе должны быть не только взаимопростыми, но еще и иметь минимальную попарную разность по модулю не меньше чем d. Вопрос: при каком максимальном d существует решение при такой постановке?
Вопрос: при каком максимальном d существует решение при такой постановке?
Любопытный апгрейд. Разбивку 2n чисел можно сделать, если d равен наибольшему нечетному простому числу, которое меньше чем n. Тогда каждому четному можно подобрать пару в виде нечетного. Причем если вышло так, что d = n-1, то больше точно нельзя (тривиально доказывается). Но вот всегда ли это максимум, не совсем понятно...
Это лажовый способ по двум причинам. Во-первых, в нём нет ничего интересного, кроме синдрома NIH. Во-вторых, что более важно, он не обобщается на произвольное n. Например, всё ломается при n=1000. Простых чисел меньше тысячи всего 168. Второе число может быть только в группах с номерами не больше 250. Итого всего по группам распределяется не более 500 + 250 + 168 чисел, что, очевидно, меньше 1000.
Интерес автора к математике достоин уважения, но менторский тон статьи при откровенно слабом содержании смешон.
Я вот сейчас понял, что в одной колонке может быть и два нечетных составных числа, т.к 
может давать одинаковый результат для нескольких чисел: например 
. В таком случае никакого ограничения на 250 чисел нет.
Да, признаю, что это надо было уточнить изначально в тексте, однако сам алгоритм справляется с такими случаями. Жду дальнейшую критику
А теперь скажите, есть ли смысл делить нечётные числа на простые и составные?
Я кажется понял на что вы намекаете: можно было убрать первую группу с простыми и добавлять их по такому-же правилу, что и с составными нечетными. Я просто изначально отделил простые, хотя это можно было и не делать
Да, в том числе на это. Но вообще тут много вариантов. Простые числа можно, например, закидывать в любую группу, где максимальное число не более чем в два раза больше этого простого. Можно менять местами числа вида 2n и 4n. Можно производить много всякой суеты. Но всё это не демонстрирует никаких глубинных идей. Это просто раскладывание математического пасьянса. А раскладывание пасьянса интересно только раскладывающему.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Интересный способ сгруппировать натуральный ряд