Математическое и загадочное

[Рогожников Евгений 22]

10.05.2020 в 21:42, E.K. сказал:

Могут ли все натуральные числа от 2 до 100 быть членами 13 геометрических прогрессий?

 

Ответ: не могут.

 

Лемма 1. Членами геометрической прогрессии не могут быть три взаимнопростых числа.
доказательство: пусть a*x^n есть геометрическая прогрессия. и пусть p < q < r три принадлежащих ей взаимнопростых числа.
Тогда  p = a*x^(n-k); q = a*x^n; r = a*x^(n+m), где  n, k, m - некоторые натуральные числа.

Но тогда выполнено соотношение q^(k+m) = p^m*r^k.  Получили противоречие.

 

Лемма 2. Членами геометрической прогрессии не могут быть два взаимнопростых числа и их произведение.
доказательство: пусть a*x^n есть геометрическая прогрессия. и пусть p < q два принадлежащих ей взаимнопростых числа.
Тогда  p = a*x^m; q = a*x^n;
т.к. p*q также есть член прогрессии, то  p*q = a*x^(n+k). И тогда p = x^k.
Аналогично q = x^l. Но тогда p^l = q^k.  Получили противоречие.

 

Лемма 3. Членами геометрической прогрессии не могут быть два взаимнопростых числа и квадрат одного из них.
доказательство: пусть a*x^n есть геометрическая прогрессия. и пусть p < q два принадлежащих ей взаимнопростых числа.
Тогда  p = a*x^m; q = a*x^n;
т.к. p^2 также есть член прогрессии, то p = x^k.
Но тогда p*q = a*x^(n+k) также есть член прогрессии, чего по лемме 2 быть не может.

 

 

Вернемся теперь к нашей задаче. Выпишем простые числа от 2 до 100:
2, 3, 5, 7, 11
13, 17, 19, 23, 29
31, 37, 41, 43, 47
53, 59, 61, 67, 71
73, 79, 83, 89, 97

Как видно, их 25 штук.

Выпишем квадраты простых чисел от 2 до 100:
4, 9, 25, 49

Их 4 штуки.

Всего 29 чисел. Никакие 3 из них не могут быть членами одной прогрессии по леммам 1 и 3.
Таким образом, потребуется минимум 15 прогрессий.

Думая полученная тут оценка довольно грубая и потребуется гораздо больше прогрессий.
Однако, задача получения точной оценки намного сложнее

[Fireman 41]

2 часа назад, Рогожников Евгений сказал:

Таким образом, потребуется минимум 15 прогрессий.

 

Допущение 1: Будем рассматривать только возрастающие геометрические прогрессии, т.е. у которых k > 1

 

потому что убывающая геометрическая прогрессия c k' = 1/k включает те же самые числа, что и возрастающая прогрессии с k, 
 

 

Утверждение 1. Целое число можно получить ТОЛЬКО умножением его на рациональное число, поэтому k in Q
 

вытекает из определения рациональных чисел

хотя k может быть иррациональным, но отношения между двумя соседними целыми числами в геометрической прогрессии будет все равно рациональным - pow(k, x) in Q

 

 

Утверждение 2: Для того, чтобы при умножении некоторого целого числа x на k получалось целое число необходимо, чтобы оно содержало в себе знаменатель возведённый в некоторую целую степень (t in N): x = y * b^t

 

Поскольку k – рациональное число, то его можно представить согласно основной теореме арифметики в виде несократимой дроби k = a/b = (p1^m1 * p2^m2 * … *  pr^mr) / (q1^n1 * q2^n2 * … * qs^ns), где pi и qi – простые числа

 

 

Утверждение 3:  Из Утверждения 2 вытекает, что каждый следующий натуральный член геометрической последовательности будет содержать в себе знаменатель k в меньшей степени
 

 

Утверждение 4: Из утверждения 3 вытекает, что геометрическая последовательность не может содержать больше [log_2(99)] чисел от 2 до 100, т.е. не может содержать более 6 натуральных чисел

 

 

Таким образом , потребуется минимум 17 прогрессий

[E.K. 11 237]

3 часа назад, Рогожников Евгений сказал:

 

Ответ: не могут.

 

Лемма 1. Членами геометрической прогрессии не могут быть три взаимнопростых числа.
доказательство: пусть a*x^n есть геометрическая прогрессия. и пусть p < q < r три принадлежащих ей взаимнопростых числа.
Тогда  p = a*x^(n-k); q = a*x^n; r = a*x^(n+m), где  n, k, m - некоторые натуральные числа.

Но тогда выполнено соотношение q^(k+m) = p^m*r^k.  Получили противоречие.

 

Лемма 2. Членами геометрической прогрессии не могут быть два взаимнопростых числа и их произведение.

Сложновато..

 

Лемма1 - необходима. Затем так: 12 последовательностей нужно чтобы отсеять 24 из 25 простых чисел (от 2 до 100). То есть, чтобы было 13 необходимо чтобы одно простое и все непростые были членами одной прогрессии. Там также как и в Лемме1 основной теоремой арифметики трах-бах! - и готово.

 

Но вот остаётся любопытный вопрос: сколько же минимально геом-последовательностей требуется для покрытия всех чисел 2-100?

[Рогожников Евгений 22]

1 час назад, Fireman сказал:

Утверждение 4: Из утверждения 3 вытекает, что геометрическая последовательность не может содержать больше [log_2(99)] чисел от 2 до 100, т.е. не может содержать более 6 натуральных чисел

Можно поподробнее объяснить этот момент?

[Fireman 41]

Прогнал перебор по целым и рациональным коэффициентам, получается, что нужно 37 последовательностей

 

[2, 4, 8, 16, 32, 64]
[3, 6, 12, 24, 48, 96]
[5, 10, 20, 40, 80]
[7, 14, 28, 56]
[9, 18, 36, 72]
[11, 22, 44, 88]
[13, 26, 52]
[15, 30, 60]
[17, 34, 68]
[19, 38, 76]
[21, 42, 84]
[23, 46, 92]
[25, 50, 100]
[27, 45, 75]
[29, 58]
[31, 62]
[33, 66]
[35, 70]
[37, 74]
[39, 78]
[41, 82]
[43, 86]
[47, 94]
[49, 98]
[51, 85]
[53, 54]
[55, 77]
[57, 95]
[59, 63]
[61, 65]
[67, 69]
[71, 73]
[79, 81]
[83, 87]
[89, 90]
[91, 93]
[97, 99]

[Fireman 41]

16 минут назад, Рогожников Евгений сказал:

Можно поподробнее объяснить этот момент?

 

если k - целое, то a0 * k^n <= 100, максимальное n в этом случае при a0 = 2, k = 2, n =6. 

 

если k=a/b - рациональное, то максимальное кол-во членов последовательности при b = 2, но в этом случае a0 должно быть вида a0 = x * b^n, например

 

k = 3/2, a0 = 6 => a1 = 9, больше целых чисел нет (последовательность из 2 чисел)

k = 3/2, a0 = 16 => a1 = 24, a2 = 36, a3 = 54, a4 = 81, больше целых числе нет (последовательность из 5 чисел)

 

можно показать, что максимальная последовательность будет только при целом k = 2 и она равна 6

всего чисел 99 (от 2 до 100), значит требуется минимум 17 последовательностей

[Рогожников Евгений 22]

ага. спасибо. Это я ступил. Там уже все очевидно. Просто я когда решал совсем не в ту степь пошел. Надо было сразу подумать о возможной длине цепочки.И тогда сразу понятно, что обязательно в дроби k должна быть двойка или тройка,иначе длина сразу не более 2. Оценка в 13 цепочек настолько слабая, что решение бы моментально получилось. Ну а с двойкой и тройкой можно было заморочиться и перебрать варианты и дойти до точного решения.

 

Красивая задачка.

[Fireman 41]

1 час назад, Рогожников Евгений сказал:

Оценка в 13

 

ну да, я когда решал как раз зашел с длины последовательности

 

Утверждение 1: Если из чисел от 2 до 100 составили 13 геометрических прогрессий, то хотя бы одна прогрессия должна содержать не менее [99/13] = 8 чисел, при k = 2 такая прогрессия 2, 4, 8, 16, 32, 64 содержит только 6 чисел, значит k < 2

 

Утверждение 2: (тут я сжато сейчас) - максимальная последовательность с рациональным k не может превышать максимальную последовательность с целым k

 

хотя... вроде доказательство должно быть такое:

 

Пусть k - знаменатель геометрической прогрессии

 

Очевидно, что k - является алгебраическим числом (не трансцендентным), поэтому может быть представлено как k = (i)√(p/q), где p, q, i in Z (натуральные числа), а p и q - взаимнопростые (иначе дробь сведем к несократимой)

 

Любой натуральный член геометрической прогрессии aj может быть представлен тогда как a0 * (p/q)^rj, где a0 - первый натуральный член геометрической прогрессии

 

Таким образом искомая геометрическая прогрессия будет содержать последовательные натуральные члены (между которыми могут быть как рациональные, так и иррациональные члены):

 

a0, a1, a2, ... an = a0, a0 * (p/q)^r1, a0 * (p/q)^r2, ..., a0 * (p/q)^rn

 

Поскольку геометрическая прогрессия возрастающая, то 

 

1 < r1 < r2 < ... < rn

 

Отсюда следует, что a0 должна иметь в качестве множителя q^rn

 

для 8 членов минимальной геометрической прогрессии это будет a0 * 2^7 = 127 * a0, что не укладывается в диапазон [2, 100]

 

P.S.

 

Есть вопросы,

 

1) а может ли последовательность быть не монотонно возрастающей (или убывающей), а такой: 50, 51,49,52,48 и т.п.

Но вроде нет, поскольку такую геометрическую прогрессию можно разложить на 2 - одна убывающая, другая возрастающая и опять будут те же проблемы, что и описаны выше

 

2) обязательно ли k должно быть алгебраическим

Наверное тоже да, для этого достаточно геометрическую прогрессию свести к многочлену с натуральными коэффициентами

Изменено 12 мая, 2020 пользователем Fireman

[Рогожников Евгений 22]

55 минут назад, Fireman сказал:

Есть вопросы,

 

1) а может ли последовательность быть не монотонно возрастающей (или убывающей), а такой: 50, 51,49,52,48 и т.п.

Но вроде нет, поскольку такую геометрическую прогрессию можно разложить на 2 - одна убывающая, другая возрастающая и опять будут те же проблемы, что и описаны выше

 

2) обязательно ли k должно быть алгебраическим

Наверное тоже да, для этого достаточно геометрическую прогрессию свести к многочлену с натуральными коэффициентами

 

 

Ты же в самом первом посте все описал. Повторю в упрощенном виде.  Мы рассматриваем прогрессии вида A*k^n.  При этом можно считать, что k>1, т.к иначе достаточно рассмотреть аналогичную прогрессию с коэффициентом 1/k.

Ясно, что в этом случае прогрессия монотонно растет. Это ответ на 1-й вопрос

Далее  можно считать,  что A - целое. В самом деле - мы ищем не просто прогрессии, а те, которые имеют числа в нашем диапазоне 2-100. Значит, в качестве A можно взять минимальное число из диапазона 2-100.

 

Далее - если у нас в диапазон 2-100 попадают члены прогрессии с номерами N_1,  ..., N_m, то можно считать, что НОД(N_1,  ..., N_m)= 1.

В противном случае, если он равен d, то можно рассмотреть другую прогрессию с коэффициентом k^d.

А раз НОД равен 1, то некая линейная комбинация чисел N_1,  ..., N_m равна 1. Но тогда эта же комбинация даст нам уравнение из которого число k  выражается как произведение целых чисел  в целых степенях.

Иными словами, такое k у нас заведомо будет рациональным. Это ответ на 2-й вопрос

[E.K. 11 237]

25.02.2019 в 01:34, E.K. сказал:

Есть три окружности неравных радиусов. Ко всем ним проведены касательные линии. Доказать, что пересечения этих линий лежат на одной прямой.

Давным-давно (вон там) была эта задачка. Тут в ЖЖ предложили её нестандартное решение через трёхмерное пространство. Не посмотрите - верное решение?  ->

 

"Задача про окружности решается из трехмерных соображений. Если не знаешь вряд ли догадаешься. Вместо окружностей строим сферы с теми же центрами и радиусами. проводим три плоскости - через центры и с двух сторон внешние касательные к сферам. Каждую пару сфер вписываем в конусы. Все три плоскости пересекаются по одной прямой. На этой прямой находятся вершины конусов. Рисунок к задаче это то что получается при пересечении плоскости проходящей через с центры с остальными поверхностями"

 

А всё верно! Красивое решение.

[Рогожников Евгений 22]

2 часа назад, E.K. сказал:

нестандартное решение через трёхмерное пространство.

 

2 часа назад, E.K. сказал:

А всё верно! Красивое решение.

 

 

Решение, в самом деле, красивое. Мне вспомнилась еще одна относительно сложная  "плоская" задача, которая достаточно просто решается через трёхмерное пространство.

Даны 3 параллельные прямые и 3 точки как на рисунке. Относительно положения точек важно только то, что  они  расположены между двумя крайними прямыми, но не все они в одной полосе.

Построить треугольник, такой что его вершины лежат на прямых, а на каждой из сторон расположено по точке

 

[Fireman 41]

2 часа назад, Рогожников Евгений сказал:

Мне вспомнилась еще одна относительно сложная  "плоская" задача

 

я правильно понимаю, что черные линии - это ребра треугольной призмы, точки лежать на 3х гранях и надо просто через 3 точки провести плоскость, а искомый треугольник будет сечением призмы данной плоскостью?

[Рогожников Евгений 22]

11 часов назад, Fireman сказал:

я правильно понимаю, что черные линии - это ребра треугольной призмы, точки лежать на 3х гранях и надо просто через 3 точки провести плоскость, а искомый треугольник будет сечением призмы данной плоскостью?

 

Именно так. Как только данная идея приходит в голову, то дальнейшее построение сечения, которое хоть и не очень простое,  но   есть дело техники. 

[E.K. 11 237]

Субботнее. У меня что-то не получилось..

 

Вне окружности поставлена точка. Провести только с помощью линейки проходящую через эту точку касательную к окружности. Центр окружности неизвестен. Линейка умеет только проводить прямые линии через две точки, расстояния измерять линейка не умеет.

 

Циркуля нет, ничего более тоже нет. Только окружность, точка и линейка, всё.

[Fireman 41]

53 минуты назад, E.K. сказал:

Циркуля нет, ничего более тоже нет. Только окружность, точка и линейка, всё.

 

как маленькая подсказочка ? - ведь неважно, где находится точка, алгоритм построения должен быть одинаковым

Изменено 16 мая, 2020 пользователем Fireman