2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 13:46 
Аватара пользователя
gris
Большое спасибо!
А не проще сперва доказать, что все числа должны дарамдаш одинаковые остатки при делении на 5?

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:11 
Аватара пользователя
Чуть было не улучшил результат gris до $551$, но вовремя одумался не хватило машинной мощности для строгого (огого!) доказательства :-)

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:14 
Аватара пользователя
Ktina, А вот отнюдь Вам в парадное хедер. Это чтож за одинаковые остатки? Один или два?

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:43 
gris в сообщении #1300812 писал(а):
Сейчас попробую на компьютере посчитать.

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

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

Что упущено?

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:46 
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())
 

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 15:06 
Аватара пользователя
Ktina, норм. Просто Вы сказали, что все числа должны иметь одинаковые остатки, но не сказали какой. А это ноль, да.

 
 
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 15:26 
Аватара пользователя
Можно еще так, по тем же рельсам, но меньше приходя в сознание: пусть $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$ :oops:

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group