Перейти к содержанию

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


E.K.

Рекомендуемые сообщения

Непонятно, зачем нужно оперировать такими большими величинами?

"Во-первых, это красиво" (с) старый анекдот.

Во-вторых, некоторым очень нравится разминать свой мозг.

В-третьих, есть такая штука "криптография", которая очень любит большие и странные числа.

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

Итак, текущая задачка звучит так: Решить в натуральных числах уравнение (1 + na)b = 1 + nc

 

Для разминки попробуем поиграться с 'b'... и сразу отсекаем "b=1", поскольку получается тривиальное равенство с бесконечным количеством решений.

 

Пусть b=2. Тогда условие звучит так: (1 + na)2 = 1 + nc

Разворачиваем скобки..

 

(1 + na)2 = 1 + 2*na + n2a = 1 + nc

2*na + n2a = nc

 

Делим на na и получается..

 

2 + na = n(c-a)

 

или:

 

na * (n(c-2a) - 1)  = 2 = 2*1 (или 1*2, но тогда n=1 и второй множитель = 0).

 

Отсюда сразу: n=2, a=1, b=2, c=3 - первое решение.

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

Лучший (по мне) способ искать правильный метод решения подобных задачек - потренироваться "на кошечках". С квадратом решили. Посмотрим что с кубом и четвёртой степенью.

 

Куб. b=3  =>

 

(1 + na)3 = 1 + nc

1 + 3na  + 3n2a + n3a = 1 + nc

na * (3 + 3na + n2a ) = nc

3 + 3na + n2a = n(c-a)

3 = na * (n(c-2a) - na - 3)

 

3=3*1. Получаем n=3, a=1, всё на этом. Правая часть произведения никак не может быть единицей (3 в степени никак не станет семёркой, чтобы внутри скобок получилась единица). Не сходится, решений нет.

 

Далее. b=4  =>

 

(1 + na)4 = 1 + nc

1 + 4na + 6n2a + 4n3a + n4a  = 1 + nc

4 = na * (n(c-2a) - 6 - 4na – n2a)

 

4=4*1 => n=4, a=1, но тогда внутри скобок должна получиться единица. Но там же всё чётное. Нет, не работает.

4=2*2 => n=2, a=1, (n(c-2a) - 6 - 4na – n2a) = (2(c-2) - 6 - 4*2 – 22) = 2(c-2) - 6 - 8 - 4 = 2(c-2) - 18 = 2, то есть, 2(c-2) = 20. Быть такого не может.

 

Для 4 решений тоже нет.

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

А если на нашу штуку (1 + na)b = 1 + nc посмотреть вот таким образом:

 

(1 + na)b - 1 = nc

 

Пусть b чётное, то есть b=2d. Тогда:

 

(1 + na)2d - 1 = nc

 

Так оно на множители раскладывается:

 

((1 + na)d – 1) * ((1 + na)d + 1) = nc

 

Хммм, пусть (1 + na)d - 1 = x. Тогда

 

x*(x+2) = nc

 

Вот смотрю я на эти красивые формулы.. Что-то замечательное в них просто явно скрывается. Но что-то я пока не вижу... Помогайте.

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

Хорошо, можно тупо в лоб бахнуть Биномом Ньютона и биномиальными коэффициэнтами ->

 

(1 + na)b = 1 + nc

 

плюс-единицы сразу сокращаю, чтобы глаз не мозолили..

 

b*na + C2*n2a + C3*n3a + … + b*n(b-1)a + nba = nc ;

 

Где Cx - это биномиальные коэффициэнты по b (если кто забыл Бином Ньютона - тыкайте на Википедию по ссылкам выше).

И тут видно, что оно всё делится на na , можно сократить...
 

b + C2*na + C3*n2a + … + b*n(b-2)a + n(b-1)a = nc-a ;

 

Но тогда что получается. Степень (c-a) больше (b-1)*a , то есть, оно всё снова делится на na , то есть и b тоже делится на na , о как!

 

Ну, пусть тогда b=B1*na , какой профит из этого можно выцепить? А вот какой. Заменяем b на B1*na и сокращаем na ->

 

B1*na + C2*na + C3*n2a + … + b*n(b-2)a + n(b-1)a = nc-a ;

B1 + C2 + C3*na + … + b*n(b-3)a + n(b-2)a = nc-2a ;

 

Далее аналогично B1 + C2 = B2*na , пока не доползём до самого края:

 

B(b-1) + na = nc-ba ;

 

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

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

Не, а что на покой-то? Копать глубже! С нами же смелость, отвага и Бином Ньютона!

 

B(b-1) + na = nc-ba ;

 

А вам не кажется, это самое B-c-хвостиком делится на n ? При чём неоднократно.. Пусть B = q*n , тогда получаем:

 

q*n + na = nc-ba

 

Если разделить на n , то есть два варианта:

 

q + na-1 = nc-ba-1

q + na-1 = 1  (то есть, c-ba=1)

 

Ой, мы же работаем в натуральных числах, то есть, целых больше нуля. Второго варианта быть никак не может! То есть, этот q тоже делится на n ... до тех пор, пока не получится вот такая краказябра:

 

q + n = nz  (z - уже неважно что).

 

То есть, два варианта: 1) q=n или 2) q=n*(p-1) , тогда:

 

1:       2n = nz, что даёт n=2, z=2 и решение, которое было получено в самом начале.

 

2:       n*(p-1) + n = nz , отсюда два варианта сокращения на n ->

 

2.1:    (p-1) + 1 = 1 , но такого в нашем множестве натуральных чисел быть не может никак.

2.2:    (p-1) + 1 = nz-1

 

То есть, p = nz-1  ... и что?

 

А пока ничего. Это значит, что это Чёрное море ещё не до конца докопано. Я пошёл думать спать...

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

Можно попробовать такой подход:

 

для удобства заменю n на x

 

Требуется найти натуральные решения уравнения

 

(1 + xa)= 1 + xc

 

Для начала рассмотрим простые случаи, чтобы внести какие-то ограничения для x, a, b, c

 

1) пусть b = 1, тогда

 

x - любое натуральное число, a = c - любое натуральное число

 

поэтому в будущем будем рассматривать случаи, когда b > 1

 

2) пусть x = 1, тогда

 

(1 + 1a)= 1 + 1c

2b=2

b=1

 

т.е. x = 1, a - любое натуральное число, b = 1, c - любое натуральное число

 

поэтому в будущем будем рассматривать случаи, когда x > 1

 

3) пусть x > 1, b > 1 и разберем этот случай

 

Для начала применим формулу бинома Ньютона к левой части уравнения: sum(b!/[(b-k)!k!]*(xa)k, k=0..B)

 

и вынесем некоторые коэффициенты за скобки, получим:

 

1 + bxa(1 + z) + (xa)b = 1 + xc

 

где

 

z = sum((b-1)!/[(b-k)!k!]*(xa)k-1, k=2..b-1) = (xa) * g(x)

 

член разложения, который нам пока не понадобится

 

Упрощаем исходное уравнение и получаем:

 

b * (1 + (xa) * g(x)) = xab-a * (xc-ab - 1)

 

Видно, что (1 + (xa) * g) не делится на x (будет всегда остаток 1), а это значит, что b делится на x и даже больше - b делится на xab-a.

 

Разложим теперь (xc-ab - 1) на множители и получим известную формулу

 

(xc-ab - 1) = (x - 1)(1 + x + x2 + ... + xc-ab-1)

 

b * (1 + (xa) * g) = (x - 1)(1 + x + x2 + ... + xc-ab-1)

 

Если вспомнить чему равно (1 + (xa) * g) - то это многочлен с (xa) в разных степенях и что важно (!!!) с положительными коэффициентами, т.е. 

 

1 + (xa) * g = 1 + p1xa + p2x2a + ... + pnxa(b-2)

 

где коэффициенты pi - натуральные числа (старшие факториалы делить на младшие факториалы)

 

А поэтому (1 + (xa) * g) НЕ ДЕЛИТСЯ на (x - 1)

 

Значит b длится на (x - 1)

 

Т.е. b можно записать как 

 

b = xab-a(x - 1) * r

 

где r - это член разложения (1 + x + x2 + ... + xc-ab-1) (если оно конечно раскладывается :) )

 

Рассмотрим минимально возможный вариант:

 

(1 + x + x2 + ... + xc-ab-1) не раскладывается на множители

 

Значит

 

b = xab-a * (x - 1) 

 

(1 + (xa) * g) = (1 + x + x2 + ... + xc-ab-1)

 

И надо решить эту систему из двух уравнений.

 

Помогает то, что x^b расчёт значительно быстрее b и поэтому найти коэффициенты (для натуральных чисел) можно обычным перебором, например:

 

пусть x = 2, тогда

 

b = 2a(b-1)

 

даже если a будет минимальным (a = 1), то b = 2 и все, дальше слишком быстрый рост 2a(b-1) обгонит линейный рост b и других коэффициентов не будет

 

в результате получаем решение x = 2, a = 1, b = 2, c = 3

 

пусть x = 3, тогда

 

b = 2 * 3a(b - 1)

 

и уже ни при каких значениях b мы не сможем решить это уравнение, тоже касается тем более и для более высоких x

 

Описанный выше минимальный случай можно рассмотреть решая и второе уравнение:

 

(1 + (xa) * g) = (1 + x + x2 + ... + xc-ab-1)

 

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

 

 

Рассмотрим теперь случай, когда (1 + x + x2 + ... + xc-ab-1) все таки раскладывается на произведение многочленов, тогда получится

 

b = xab-a * (x - 1) * f(x)

 

где

 

f(x) - многочлен некоторой степени x

 

И опять все "портит" xab-a - он слишком быстро расчет в отличии от b, и никаких других вариантов, чем те, что мы рассмотрели выше мы не получим

 

-------------------------

 

Немного дополнений:

 

Пусть

 

w = b / xab-a 

 

Тогда приведённое выше уравнение можно переписать в виде

 

w * (1 + (xa) * g) = xc-ab - 1

 

или перекинув члены направо и налево

 

w + w * (xa) * g) = xc-ab - 1

w + 1 = xa * (xc-ab-a - w * g)

 

откуда видно, что (w + 1) делится на x

 

Но получается, что 

 

w + 1 = b / xab-a + 1 

 

делится на x, а это возможно только когда b имеет следующий вид

 

b = xab-a * (p1x + p2x+ ... + pnxn - 1) 

 

И в описанном случае минимально было n = 1, p1=1

  • Спасибо (+1) 1
Ссылка на комментарий
Поделиться на другие сайты

0. Приношу извинения за личные тормоза. График жизни как-то опять был беспросветно-непрерывный.

 

1. Решение вроде верное. Я тоже шёл по этой дороге (разложение, биномиалы и b "улетает в космос"), но когда "обдумывание свежим мозгом" случается только импульсами по 10-15-20 минут, то решение подобных задачек может занять месяц-два..

 

2. Крайняя запись в моих измышлениях такая:

 

C1*( 1 + na(b-2) ) + C2*na *( 1 + na(b-4) ) + C3*n2a * ( 1 + na(b-5) ) + … + C[b/2]*na ??? (b-2) = nc-a - na(b-1)

 

То есть, я лишь чуть-чуть не дотянул до решения.. Увы.

 

3. Давайте решать задачки попроще. А то такие зубодробилки не всем доставляют удовольствие..

Ссылка на комментарий
Поделиться на другие сайты

Вижу, что притомил я вас тяжёлыми задачками. Постараюсь исправиться. Вот, например, простенькая, но красивая. Решается за 15 минут в качестве утренней разминки для ума.

 

Есть некоторая сумма факториалов 1! + 2! + 3! + ... + n!.

Доказать, что найдется такое n, что эта сумма будет иметь простой делитель, больше 20192019.

 

Пробуйте. Биномиалов и функций Эйлера не потребуется, обещаю!

 

UPD: Ой, что-то я погорячился.. Не 15 это минут. Просто утренний ум перепутал какая левая-правая часть равенства на какие простые делится..

Ссылка на комментарий
Поделиться на другие сайты

Что-то я опять пообещал простую задачку и опять всех обманул. Что-то пока не очень получается...

 

Кстати, однажды мы уже решали задачку про сумму факториалов, помните? Вот здесь она: https://forum.kasperskyclub.ru/index.php?showtopic=54210&p=839847

 

Новая задачка про факториалы значительно интереснее. Что-то не получается у меня сквозь неё пробиться. Вдруг у кого идеи возникнут?

 

Итак, есть некая сумма S(n) = 1! + 2! + 3! + ... + n!

Что мы про неё знаем?

 

1. S(n) всегда нечётна.

2. S(n) почти сразу делится на 3, а потом и на 9.

3. Можно раскрутить её на несколько шагов и увидеть, что один из простых делителей почти моментально улетает "в космос" в бесконечность:

 

n   n!        S(n)

1   1         = 1

2   2         = 3

3   6         = 9

4   33        = 3*11

5   153       = 9*17

6   873       = 9*97

7   5913      = 9*9*73

8   46233     = 9*11*467

9   409113    = 9*131*347

10  4037913   = 9*11*40787

 

Какая-то вот такая картинка. Сразу понятно откуда возникла задачка. Глядя на крайний правый делитель у настоящих криптографов сразу возникает желание максимально дёшево получать максимально большие простые числа :) Ведь S(n) считается "бесплатно": за два действия (умножение и сложение) получаем очередное значение последовательности. Это просто кладезь простых чисел!! .. Но я отвлёкся.

 

Конда условие задачки звучит "доказать, что в этой формуле будет всегда то-то или вот такое-то" - это означает, что решать задачку надо от обратного.То есть ->

 

Предположим, что в разложении всех S(n) есть максимальное простое число. То есть, набор всех простых делителей S(n) конечен. Пусть их будет... пять. Какая разница? :)  Это {p1,p2,p3,p4,p5}. Соответственно, количество комбинаций разложения S(n) на простые множители (без учёта их степеней) тоже конечно.

 

Последовательность S(n) - бесконечна. Соответственно, существуют S(n) и S(n+k) из одного набора простых делителей (но с разными степенями). Причём количество вариантов {n,k} бесконечно для каждого набора простых делителей. То есть,

 

S(n+k) - S(n) = (n+1)! + (n+2)! + ... + (n+k)! = P*( a-b )

 

где P=наибольший общий делитель (НОД) S(n+k) и S(n), а ( a-b ) остатки от деления на НОД.

 

Попробуем сумму факториалов разложить на множители:

 

(n+1)! * ( 1 + (n+2) + ... + ((n+2)*...*(n+k)) )   = P*( a-b )

 

А вот далее я заткнулся. Логика дальнейшего доказательства мне кажется такой:

- левая часть очень быстро "улетает в космос".

- правая же ограничена конечным набором простых чисел, "уносить" правую часть "в космос" можно только их степенями.

 

 

Но как показать это математически... я пока теряюсь. Помощи от зала уже не жду, что-то опять запредельной сложности задачку мне подкинули..

Ссылка на комментарий
Поделиться на другие сайты

Что в решениях очень не хватает, так это математического редактора, чтобы можно было писать что нибудь типа [math]x^2 - y_1 = \frac{1}{2}[/math], а то смайлики побеждают.

 

Помощи от зала уже не жду

 

 

 

действительно, задачу удобно доказывать от противного и очень пригодятся делители для разных S(n)

 

и пригодится приведённый выше факт то, что числа S(n) и S(k) могут делиться не просто на какое-то простое число p, а на простое число, но с разными степенями (pa и pb)

 

 

Для удобства можно ввести функцию fp(n) определения степени такого простого делителя p для числа S(n)

у этой функции fp есть очевидное свойство, что  fp(n+k) = min(fp(n), fp(k))

 

Для доказательство пригодится одна лемма (даже леммка, но из-за таких леммок доказательства и становятся большими и некрасивыми  :cry2:)

 

Лемма:

 

Если fp(Sn) < fp((n+1)!) при некотором n, тогда fp(Sn) =  fp(Sk) при всех k >= n.

 

Доказательство: 

 

Для удобства обозначим a = fp(Sn), b = fp((n+1)!). Из условия следует, что b >= a + 1.

В сумме SkSn + (n + 1)! + ... + k! все слагаемые кроме первого делятся на pa+1, а вот первое по условию леммы делится только на pa.

А значит и Sk делится только на pa, но никак не на pa+1.

 

Доказано.

 

А дальше можно рассматривать простые множители меньше искомого 20192019 , как верхней границы для некоторого числа Sn, и приходить к противоречию в рассуждениях.

Или если зайти с другого боку можно показать, что fp(Sn) = fp(n!) для любого n кратного p, предположить обратное и придти опять к противоречию.

Изменено пользователем Fireman
Ссылка на комментарий
Поделиться на другие сайты

Очень простая задачка! Честное слово! Я решил за несколько минут.

Найти все целые решения уравнения y^2 = x^3 + 1

 

Ой-ой, что-то я опять погорячился.. Не такая и тривиальная оказалась эта задачка в общем случае. Короче, дело на первый взгляд вот такое несложное:

 

y^2 = x^3 + 1

y^2 - 1 = x^3

(y + 1)*(y - 1) = x^3

 

=>

х=0, y={-1,1}

x!=0, то два варианта: { y+1=x2 ; y-1=x } , { y+1=x ; y-1=x2 }

 

Вычитаем второе из первого (в обоих вариантах) и помним, что работаем в целых числах, то есть, 2=1*2 или 2=(-1*-2) =>

 

1) 2 = x2 - x = x*(x-1)  =>  {x=2, x-1=1} или {x=-2, x-1=-1 не сходится, быть не может такого} или {x=1, x-1=2 тоже мимо} или {x=-1, x-1=-2}

2) 2 = x - x2 = x*(1-x)  =>  {x=2, 1-x=1 мимо} или {x=-2, 1-x=1 мимо} или {x=1, 1-x=2 мимо} или {x=-1, 1-x=2}

 

Итого, элементарные решения: {0, +-1}, {2,+-3}, {-1,0}

 

Вроде бы всё, но... есть нюанс... А кто сказал, что разложение на множители внутри скобок (y + 1)*(y - 1) = x^3 однозначно проецируется на (x^2)*(x) или на (x)*(x^2) ? А вдруг (y+1) и (y-1) раскладываются на хитрую комбинацию множителей, которые в результате дают куб какого-то другого целого числа?

 

Ага, сиё есть засада, доказательство которой есть не самая сложная, но и не самая тривиальная задачка.

 

Итак, надо доказать, что приведённые выше решения уравнения являются единственными. Для этого будем решать задачку немного другим способом.

  • Спасибо (+1) 1
  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
×
×
  • Создать...