По кругу расставлены 111 различных натуральных чисел...

[Ktina]

По кругу расставлены 111 различных натуральных чисел, не превосходящих $n$. Оказалось, что для каждого из этих чисел его последняя цифра совпадает с последней цифрой суммы всех остальных чисел.

Найдите наименьшее возможное значение $n$ и докажите, что оно действительно наименьшее.

(в условии данной задачи слово "различных" означает "попарно различных")

[gris]

$555$
Я делал так: Рассматриваю множество $K_n:\{k\in N:1\leqslant k \leqslant n\}$. Запускаю цикл по $n$ от $111$ до бесконечности. Запускаю подцикл по всем выборкам $111$-ти элементов из $K_n$. В каждом подцикле обнуляю счётчик удач. Суммирую все элементы выборки. Запускаю подподцикл по элементам выборки. Если элемент и разность суммы и элемента равны по модулю $10$, то увеличиваю счётчик удач на $1$. Если на выходе их подподцикла счётчик удач равен $111$, то объявляю $n$ решением задачи.
Вот получилось $555$. Сейчас попробую на компьютере посчитать. Вдруг какую выборку пропустил? Невнимательным стал

[Ktina]

gris
Большое спасибо!
А не проще сперва доказать, что все числа должны дарамдаш одинаковые остатки при делении на 5?

[waxtep]

Чуть было не улучшил результат gris до $551$, но вовремя одумался не хватило машинной мощности для строгого (огого!) доказательства

[gris]

Ktina, А вот отнюдь Вам в парадное хедер. Это чтож за одинаковые остатки? Один или два?

[kotenok gav]

gris в сообщении #1300812 писал(а):

Сейчас попробую на компьютере посчитать.

Запустил программу, ожидайте результатов годика через два.

[Ktina]

gris
Все числа дают одинаковые остатки при делении на 5, в этом легко убедиться, задавшись вопросом, на какую цифру оканчивается сумма всех 111 чисел. Кроме того, этим остатком может быть только остаток, так как сумма 110 одинаковых остатков, равная 111-му остатку, будет 0. Ну а пример приводится легко - первые 111 натуральных чисел, кратных 5.

Что упущено?

[kotenok gav]

kotenok gav в сообщении #1300838 писал(а):

gris в сообщении #1300812 писал(а):

Сейчас попробую на компьютере посчитать.

Запустил программу, ожидайте результатов годика через два.

Программа выдала ошибку, связаную с размером массива (слишком большой вышел).

-- 01 апр 2018, 21:20 --

Может кто сумеет оптимизировать:

Используется синтаксис Python

def choose(k1, l):
    if l==1:
        r=[]
        for i in k1:
            r.append([i])
        return r
    else:
        r1=choose(k1, l-1)
        r=[]
        for i in r1:
            for j in k1:
                if not(j in i):
                    r2=i.copy()
                    r2.append(j)
                    r.append(r2)
        return r
def main():
    n=111
    while n>=111:
        k=range(1, n+1)
        for i in choose(k, 111):
            m=0
            j=i.sum()
            for g in i:
                if (g%10)==((j-g)%10):
                    m=m+1
            if m==111:
                return n
        n=n+1
print(main())
 

[gris]

Ktina, норм. Просто Вы сказали, что все числа должны иметь одинаковые остатки, но не сказали какой. А это ноль, да.

[waxtep]

Можно еще так, по тем же рельсам, но меньше приходя в сознание: пусть $x$ - любое из $111$ чисел, а $S$ - сумма их всех. Тогда, по модулю $10$: $x=S-x\Rightarrow2x=S\Rightarrow2S=111S\Rightarrow2x=S=0$

-- 01.04.2018, 15:42 --

(почесав репу) перенос $x$ налево - лишний шаг, конечно

-- 01.04.2018, 15:58 --

Нет, все таки вот так автоматичнее всего: $x=S-x\Rightarrow2x=S\Rightarrow2S=111S\Rightarrow2x=S=110S=0$