задача дня -- 7

Aug 09, 2016 06:47

Вот неплохая, на мой взгляд, задача ( Read more... )

задача-дня, математика

Leave a comment

Comments 36

hookmoon August 9 2016, 06:01:23 UTC
в арифметичесокй последовательности как минимум каждый второй член четный, то есть взаимно просты могут быть всего два элемента.

Reply

ykreimer August 9 2016, 06:06:35 UTC
a1 = 1, d =2, ни одного четного члена.

Reply

hookmoon August 9 2016, 06:26:56 UTC
соответственно чтобы каждый третий член прогрессии не делился на три, d должен быть кратным трем. чтобы не было пяти, то кратен пятерке. 2*3*5 =30, слишком большой шаг, быстро вылетаем за сотню.

2*3 дает последовательность
1, 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, 73, 79, 85.
число которое делится на 5 тут ровно посередине, но попадаются 7 и 49.

а1=31, d=6, получается 9 элементов.

Reply

hookmoon August 9 2016, 06:29:56 UTC
ну и рассуждая аналогично 2*3*5*7 даст 210 что слишком много, для N=1000
2*3*5 =30, максимальная длина будет 13 элементов, главное подгадать, чтобы внутри не было делений на 11.

Reply


rasterjasha August 9 2016, 07:31:39 UTC
а) длина 8, например: 7, 19, 31, 43, 55, 67, 79, 91
б) длина 11, например: 11, 101, 191, 281, 371, 461, 551, 641, 731, 821, 911

Reply

rasterjasha August 9 2016, 07:41:17 UTC
хотя, если можно ограничить сверху или снизу, то по пункту б) можно и длину 13: 263, 323, 383, 443, 503, 563, 623, 683, 743, 803, 863, 923, 983

Reply

roman_rogalyov August 9 2016, 08:59:55 UTC
И больше 13 членов в пределах тысячи получить не удастся, ибо разность прогрессии должна делиться на 30 - чтобы избежать частого повторения кратных 2,3 и 5 среди членов прогрессии, а среди 14 последовательных членов прогрессии с разностью 30 или 60 обязательно встретятся два кратных 7.

Длину 13 я получил след. способом: берём 1001=7*11*13 - число чуть больше 1000, и начинаем вычитать из него 30: 971, 941, 911, 881, 851=23*37, 821, 791=113*7, 761, 731=17*43, 701, 671=61*11, 641, 611=13*47

В пределах сотни максимальная длина прогрессии равна девяти - разность должна быть 6, а среди десяти последовательных чисел с такой разностью обязательно встретятся два кратных 5.

11, 17, 23, 29, 35, 41, 47, 53, 59

Reply

falcao August 9 2016, 17:06:11 UTC
Хорошие примеры! Было бы хорошо дополнить их доказательством оптимальности.

Reply


rasterjasha August 9 2016, 07:42:43 UTC
выше уже заметили, что их или меньше 10 или разность прогрессии делится на 30. Или их меньше 14 или разность делится на 2*3*5*7=210

Reply

falcao August 9 2016, 17:06:54 UTC
Да, это верные соображения!

Reply


oopk August 9 2016, 23:46:34 UTC
Интересная задача, особенно без калькулятора и пр. Для произвольного N она всё-таки не на программирование, наверное.

1. Если разность не делится на p, то, чтобы не было двух членов, делящихся на p, длина последовательности не более 2p-1.
2. Беспокоиться надо о делимости каких-нибудь двух членов на простые числа, которые меньше длины последовательности.

Это соображение даёт не более 3-х и 5-и членов из-за p=2, 3. Для p=5 длина не более 9-и ( ... )

Reply

falcao August 10 2016, 04:05:56 UTC
Я думаю, у Вас почти до конца всё проанализировано, в смысле высказанных соображений.

Утверждение из предпоследнего абзаца надо будет проверить -- это сам по себе интересный вопрос с ясной формулировкой.

Reply

oopk August 10 2016, 11:50:18 UTC
N=49, видимо.

Reply


kola111 August 10 2016, 05:05:19 UTC
интересная задача в плане методологического подхода.
Например, питерский математик из известного сайта при решении некоторых нетривиальных задач просто ссылается на классическую формулу, и ответ в кармане. В этом же случае задача решается тривиальным программым кодом в доли секунды. Можно ли здесь на него сослаться?

Reply

falcao August 10 2016, 08:00:17 UTC
Приводить программный код точно не нужно (это для меня примерно как читать по-китайски :)), но можно дать краткое словесное описание алгоритма, если есть желание. А также сообщить результаты (какие именно примеры построила программа).

Reply

kola111 August 10 2016, 08:08:01 UTC
Вы уходите от сути коммента.
Можно ли ссылаться на программнынй код,,как на классическую формулу?

Reply

falcao August 10 2016, 08:28:27 UTC
Под классической формулой понимается такая, которая где-то уже изложена, и считается известной. Ясно, что программные коды к этой категории не относятся.

Reply


Leave a comment

Up