2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 10:01 
Аватара пользователя


01/12/11

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

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

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

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 11:31 
Заслуженный участник
Аватара пользователя


13/08/08
14430
$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 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:11 
Аватара пользователя


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

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:14 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:43 


21/05/16
4292
Аделаида
gris в сообщении #1300812 писал(а):
Сейчас попробую на компьютере посчитать.

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

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:44 
Аватара пользователя


01/12/11

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

Что упущено?

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 14:46 


21/05/16
4292
Аделаида
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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: По кругу расставлены 111 различных натуральных чисел...
Сообщение01.04.2018, 15:26 
Аватара пользователя


07/01/16
1426
Аязьма
Можно еще так, по тем же рельсам, но меньше приходя в сознание: пусть $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