Как разбить числа от 1 до n на три множества так, чтобы сумма чисел в каждом была одинаковой?

Рейтинг: 4Ответов: 2Опубликовано: 20.01.2023

Вам дано число n. Разбейте все натуральные числа от 1 до n на три множества так, чтобы сумма чисел в каждом множестве была одинаковой. Не понимаю с какой стороны зайти

Я сделал, однако алгоритм не работает так как надо: Такой должен быть вывод при n = 5

2
1 4

2
2 3

1
5

Это мой код:

n = int(input())


def divide_numbers(n):
    if n * (n + 1) / 2 % 3 == 0:

        numbers = [i for i in range(1, n+1)]
        total_sum = sum(numbers)
        set_sum = total_sum // 3
        sets = [[], [], []]
        for num in numbers:
            if sum(sets[0]) + num <= set_sum and len(sets[0])<2:
                sets[0].append(num)
            elif sum(sets[1]) + num <= set_sum and len(sets[1])<2:
                sets[1].append(num)
            else:
                sets[2].append(num)
        return sets
    else:
        return -1

a = divide_numbers(n)
if a != -1:
    first = a[0]
    len_first = len(first)
    second = a[1]
    len_second = len(second)
    thired = a[2]
    len_thired = len(thired)
    print(len_first)
    print(*first)
    print(" ")
    print(len_second)
    print(*second)
    print(" ")
    print(len_thired)
    print(*thired)

else: print(a)

Для примера в своем коде я взял n = 5, ниже - вывод:

2
1 2
 
1
3
 
2
4 5

Я знаю, что где-то ошибся, не выполняется условие, что сумма множества должна быть одинаковой.


Я сделал, однако алгоритм не работает так как надо: Такой должен быть вывод при n = 5

2
1 4

2
2 3

1
5

Это мой код:

n = int(input())


def divide_numbers(n):
    if n * (n + 1) / 2 % 3 == 0:

        numbers = [i for i in range(1, n+1)]
        total_sum = sum(numbers)
        set_sum = total_sum // 3
        sets = [[], [], []]
        for num in numbers:
            if sum(sets[0]) + num <= set_sum and len(sets[0])<2:
                sets[0].append(num)
            elif sum(sets[1]) + num <= set_sum and len(sets[1])<2:
                sets[1].append(num)
            else:
                sets[2].append(num)
        return sets
    else:
        return -1

a = divide_numbers(n)
if a != -1:
    first = a[0]
    len_first = len(first)
    second = a[1]
    len_second = len(second)
    thired = a[2]
    len_thired = len(thired)
    print(len_first)
    print(*first)
    print(" ")
    print(len_second)
    print(*second)
    print(" ")
    print(len_thired)
    print(*thired)

else: print(a)

Для примера в своем коде я взял n = 5, ниже - вывод:

2
1 2
 
1
3
 
2
4 5

Я знаю, что где-то ошибся, не выполняется условие, что сумма множества должна быть одинаковой.

Ответы

▲ 6Принят

Ошибка в неправильном алгоритме. Самое неприятное место - условие and len(sets[0])<2. Оно запрещает помещать в первое множество больше двух чисел. Это точно не будет работать для больших n. Возможно, ваш алгоритм можно привести в порядок, но не понятно на какой логике он основан.

Дальше мой ответ повторяет соседний, но изложен по-другому.

Обозначим pn разбиение на группы для n чисел, если оно существует. Из pn строится pn+6 добавлением к подмножествами попарных сумм: (n + 1) + (n + 6) = (n + 2) + (n + 5) = (n + 3) + (n + 4).

Этот переход даёт основания для индукции по n с шагом 6. База индукции:

  • n = 0 => 0 = 0 = 0 - три пустых множества;

  • n = 1, 2, 3, 4 - решения нет, проверяется перебором;

  • n = 5 => 5 = 1 + 4 = 2 + 3;

  • n = 6 - решается сведением к случаю n = 0;

  • n = 7 - решения нет, сумма чисел n(n + 1)/2 = 28 не делится на 3;

  • n = 8 => 4 + 8 = 2 + 3 + 7 = 1 + 5 + 6;

  • n = 9 => 1 + 5 + 9 = 3 + 4 + 8 = 2 + 6 + 7.

Все решения по модулю шести:

  • n = 6k, k ≥ 0 - серия начинается с нуля;
  • n = 6k + 1 - решений нет, (6k + 1)(6k + 2)/2 не делится на три;
  • n = 6k + 2, k ≥ 1 - серия начинается с восьми;
  • n = 6k + 3, k ≥ 1 - серия начинается с девяти;
  • n = 6k + 4 - решений нет, (6k + 4)(6k + 5)/2 не делится на три;
  • n = 6k + 5, k ≥ 0 - серия начинается с пяти.

Код:

def split(n):
    # база индукции
    base = (
        (0, (set(), set(), set())),
        (None, (None, None, None)),
        (8, ({4, 8}, {2, 3, 7}, {1, 5, 6})),
        (9, ({1, 5, 9}, {3, 4, 8}, {2, 6, 7})),
        (None, (None, None, None)),
        (5, ({5}, {1, 4}, {2, 3}))
    )

    start, (s1, s2, s3) = base[n % 6]
    if start is None or n < start:
        return None

    # индукционный шаг
    for m in range(start, n, 6):
        s1.update((m + 1, m + 6))
        s2.update((m + 2, m + 5))
        s3.update((m + 3, m + 4))

    return s1, s2, s3


def show(sets):
    if sets is None:
        print('No partition')
    else:
        print(*('+'.join(map(str, sorted(s))) for s in sets), sep=' = ')


def self_test(m):
    for n in range(m):
        sets = split(n)
        if sets is not None:
            assert n % 3 != 1
            assert sets[0] & sets[1] == set()
            assert sets[0] & sets[2] == set()
            assert sets[1] & sets[2] == set()
            assert sets[0] | sets[1] | sets[2] == set(range(1, n + 1)), sets
            assert all(sum(s) == n * (n + 1) // 2 // 3 for s in sets)
            assert sum(map(len, sets)) == n
        print(n, ':', end=' ')
        show(sets)


# self_test(25)
show(split(int(input())))

Если раскомментировать self_test будет так:

0 :  =  = 
1 : No partition
2 : No partition
3 : No partition
4 : No partition
5 : 5 = 1+4 = 2+3
6 : 1+6 = 2+5 = 3+4
7 : No partition
8 : 4+8 = 2+3+7 = 1+5+6
9 : 1+5+9 = 3+4+8 = 2+6+7
10 : No partition
11 : 5+6+11 = 1+4+7+10 = 2+3+8+9
12 : 1+6+7+12 = 2+5+8+11 = 3+4+9+10
13 : No partition
14 : 4+8+9+14 = 2+3+7+10+13 = 1+5+6+11+12
15 : 1+5+9+10+15 = 3+4+8+11+14 = 2+6+7+12+13
16 : No partition
17 : 5+6+11+12+17 = 1+4+7+10+13+16 = 2+3+8+9+14+15
18 : 1+6+7+12+13+18 = 2+5+8+11+14+17 = 3+4+9+10+15+16
19 : No partition
20 : 4+8+9+14+15+20 = 2+3+7+10+13+16+19 = 1+5+6+11+12+17+18
21 : 1+5+9+10+15+16+21 = 3+4+8+11+14+17+20 = 2+6+7+12+13+18+19
22 : No partition
23 : 5+6+11+12+17+18+23 = 1+4+7+10+13+16+19+22 = 2+3+8+9+14+15+20+21
24 : 1+6+7+12+13+18+19+24 = 2+5+8+11+14+17+20+23 = 3+4+9+10+15+16+21+22

Всё тоже самое можно сделать в константной памяти. Алгоритм прежний, код изменился - вместо множеств генераторы, которые порождают множества:

def part(n):
    # база индукции
    base = (
        ((       ), (       ), (       )),
        None                             ,
        ((1, 5, 6), (2, 3, 7), (4, 8   )),
        ((1, 5, 9), (2, 6, 7), (3, 4, 8)),
        None                             ,
        ((1, 4   ), (2, 3   ), (5,     ))
    )

    # индукционный шаг
    step = (1, 6), (2, 5), (3, 4)

    bases = base[n % 6]
    if bases is None:
        return None
    start = sum(map(len, bases))
    assert start % 6 == n % 6
    if n < start:
        return None

    def gen(base, step):
        # база индукции
        yield from base
        for m in range(start, n, 6):
            # индукционный шаг
            yield from (m + s for s in step)

    return tuple(gen(b, s) for b, s in zip(bases, step))


def show(parts):
    if parts is None:
        print('No partition')
    else:
        print(*('+'.join(map(str, p)) for p in parts), sep=' = ')


def self_test(m):
    for n in range(m):
        partition = part(n)
        if partition is None:
            assert n % 3 == 1 or n in (2, 3)
            parts = None
        else:
            parts = tuple(map(tuple, partition))
            assert n % 3 != 1
            assert all(len(p) == len(set(p)) for p in parts)
            assert set(parts[0]) & set(parts[1]) == set()
            assert set(parts[0]) & set(parts[2]) == set()
            assert set(parts[1]) & set(parts[2]) == set()
            assert set(sum(parts, ())) == set(range(1, n + 1)), parts
            assert all(sum(s) == n * (n + 1) // 2 // 3 for s in parts)
            assert sum(map(len, parts)) == n
        print(n, ':', end=' ')
        show(parts)


# self_test(25)
show(part(int(input())))
▲ 8

Пункт 0. Очевидно, что при N < 5 ничего сделать нельзя.

Пункт 1. Если N(N+1) не делится на 3, то сделать это нельзя. Или, по-другому, N mod 3 != 1. Таким образом, либо N делится на 3, либо будет остаток 2. Не нарушая общности рассуждений, в случае остатка 2 добавим 0 к набору чисел (выводить его не надо).

Пункт 2. Делим N+1 на 3. Смотрим на число. Есть 2 варианта - оно чётное или нечётное.

Пункт 2.1 Если в пункте 2 нечётное. Рассмотрим блок

1 5 9 
2 6 7
3 4 8

(если в пункте 1 был остаток 2, то уменьшите все значения на 1 и не забудьте что не надо выводить 0).

Пункт 3. После выполнения пункта 2 мы получили, что нужно разложить по 3 массивам чётное число троек (или сразу было чётным, или мы разложили 3 тройки). Рассмотрим блок

a   a+5
a+1 a+4
a+2 a+3

Такими блоками заполним все числа.

Пример. Пусть мы хотим разложить 14 чисел. Пункт 0 - ок. Пункт 1 - остаток 2. Пусть 2 - частное 5 Пункт 2.1 делаем, в ответ пишем

(0) 4 8
 1  5 6
 2  3 7

Пункт 3. Первое число, которое не разложили это 9. Добавляем к ответу

(0) 4 8  | 9  14
 1  5 6  | 10 13 
 2  3 7  | 11 12

Думаю принцип понятен. Сложность чисто на вывод массивов, можно сразу выводить без использования доп памяти.