Pierwsza część zagadki wydaje się być do ogarnięcia za pomocą komputera, jednak próby napisania w Pythonie algorytmu podziału zbioru na podzbiory pochłonęły mi zaskakująco dużo czasu. W końcu poddałem się i wziąłem gotowca z tej strony, minimalnie tylko przerabiając go na potrzeby zagadki.

import copy

def podział(zbiór):

    def podział_rek(zbiór, indeks, ret):
        if indeks == len(zbiór):
            yield ret
            return

        for i in range(len(ret)):
            ret[i].append(zbiór[indeks])
            yield from podział_rek(zbiór, indeks + 1, ret)
            ret[i].pop()

        ret.append([zbiór[indeks]])
        yield from podział_rek(zbiór, indeks + 1, ret)
        ret.pop()

    ret = []
    yield from podział_rek(zbiór, 0, ret)

def znajdź_optymalne_podziały(N):
    zbiór = list(range(1, N+1))
    średnia_całości = sum(zbiór)/len(zbiór)
    maksymalne_odchylenie = 0
    optymalne_podziały = []

    for p in podział(zbiór):
        średnia_średnich = sum(sum(zbiór)/len(zbiór) for zbiór in p) / len(p)
        odchylenie = abs(średnia_średnich - średnia_całości)

        if odchylenie > maksymalne_odchylenie:
            maksymalne_odchylenie = odchylenie
            optymalne_podziały = [copy.deepcopy(p)]
        elif odchylenie == maksymalne_odchylenie:
            optymalne_podziały.append(copy.deepcopy(p))

    return optymalne_podziały, maksymalne_odchylenie

def main():
    N = 12
    optymalne_podziały, maksymalne_odchylenie = znajdź_optymalne_podziały(N)
    print("Optymalne podziały:")
    for podział in optymalne_podziały:
        print("  ", podział)
    print("Maksymalne odchylenie: ", maksymalne_odchylenie)

if __name__ == '__main__':
    main()

Wynik:

Optymalne podziały:
   [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11], [12]]
   [[1, 2, 3, 4, 5, 6, 7, 8, 9], [10], [11], [12]]
   [[1], [2], [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]]
   [[1], [2], [3], [4, 5, 6, 7, 8, 9, 10, 11, 12]]
Maksymalne odchylenie:  3.0

Jeżeli chodzi o drugą część zagadki, czyli rozwiązanie ogólne dla dowolnego N, to robi się ciekawie.

Trzeba najpierw zauważyć kilka spraw:

Po pierwsze, jeżeli z optymalnego rozwiązania weźmiemy dwa podzbiory, nazwijmy je S1 i S2, ze średnimi w każdym podzbiorze odpowiednio A1 i A2, takimi, że A1 < A2, to jest gwarantowane, że każda liczba w S1 jest mniejsza od każdej liczby w S2. Gdyby bowiem było inaczej, czyli gdyby w S1 była liczba X większa od liczby Y w S2, to dałoby się poprawić wynik zamieniając X i Y miejscami.

Po drugie zaś, jeżeli mamy dwa podzbiory S1 i S2 (w każdym co najmniej dwie liczby) ze średnimi A1