E.K. Опубликовано 7 марта, 2019 Автор Share Опубликовано 7 марта, 2019 Непонятно, зачем нужно оперировать такими большими величинами? "Во-первых, это красиво" (с) старый анекдот. Во-вторых, некоторым очень нравится разминать свой мозг. В-третьих, есть такая штука "криптография", которая очень любит большие и странные числа. 1 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 7 марта, 2019 Автор Share Опубликовано 7 марта, 2019 Итак, текущая задачка звучит так: Решить в натуральных числах уравнение (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 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 8 марта, 2019 Автор Share Опубликовано 8 марта, 2019 Лучший (по мне) способ искать правильный метод решения подобных задачек - потренироваться "на кошечках". С квадратом решили. Посмотрим что с кубом и четвёртой степенью. Куб. 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 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 8 марта, 2019 Автор Share Опубликовано 8 марта, 2019 А если на нашу штуку (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 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 8 марта, 2019 Автор Share Опубликовано 8 марта, 2019 Хорошо, можно тупо в лоб бахнуть Биномом Ньютона и биномиальными коэффициэнтами -> (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 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 8 марта, 2019 Автор Share Опубликовано 8 марта, 2019 Не, а что на покой-то? Копать глубже! С нами же смелость, отвага и Бином Ньютона! 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 Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 14 марта, 2019 Share Опубликовано 14 марта, 2019 Можно попробовать такой подход: для удобства заменю n на x Требуется найти натуральные решения уравнения (1 + xa)b = 1 + xc Для начала рассмотрим простые случаи, чтобы внести какие-то ограничения для x, a, b, c 1) пусть b = 1, тогда x - любое натуральное число, a = c - любое натуральное число поэтому в будущем будем рассматривать случаи, когда b > 1 2) пусть x = 1, тогда (1 + 1a)b = 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.. и вынесем некоторые коэффициенты за скобки, получим: 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 + p2x2 + ... + pnxn - 1) И в описанном случае минимально было n = 1, p1=1 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 20 марта, 2019 Автор Share Опубликовано 20 марта, 2019 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. Давайте решать задачки попроще. А то такие зубодробилки не всем доставляют удовольствие.. Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 21 марта, 2019 Автор Share Опубликовано 21 марта, 2019 Вижу, что притомил я вас тяжёлыми задачками. Постараюсь исправиться. Вот, например, простенькая, но красивая. Решается за 15 минут в качестве утренней разминки для ума. Есть некоторая сумма факториалов 1! + 2! + 3! + ... + n!. Доказать, что найдется такое n, что эта сумма будет иметь простой делитель, больше 20192019. Пробуйте. Биномиалов и функций Эйлера не потребуется, обещаю! UPD: Ой, что-то я погорячился.. Не 15 это минут. Просто утренний ум перепутал какая левая-правая часть равенства на какие простые делится.. Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 22 марта, 2019 Автор Share Опубликовано 22 марта, 2019 Что-то я опять пообещал простую задачку и опять всех обманул. Что-то пока не очень получается... Кстати, однажды мы уже решали задачку про сумму факториалов, помните? Вот здесь она: 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 ) А вот далее я заткнулся. Логика дальнейшего доказательства мне кажется такой: - левая часть очень быстро "улетает в космос". - правая же ограничена конечным набором простых чисел, "уносить" правую часть "в космос" можно только их степенями. Но как показать это математически... я пока теряюсь. Помощи от зала уже не жду, что-то опять запредельной сложности задачку мне подкинули.. Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 22 марта, 2019 Share Опубликовано 22 марта, 2019 (изменено) Что в решениях очень не хватает, так это математического редактора, чтобы можно было писать что нибудь типа [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)) Для доказательство пригодится одна лемма (даже леммка, но из-за таких леммок доказательства и становятся большими и некрасивыми ) Лемма: Если fp(Sn) < fp((n+1)!) при некотором n, тогда fp(Sn) = fp(Sk) при всех k >= n. Доказательство: Для удобства обозначим a = fp(Sn), b = fp((n+1)!). Из условия следует, что b >= a + 1. В сумме Sk = Sn + (n + 1)! + ... + k! все слагаемые кроме первого делятся на pa+1, а вот первое по условию леммы делится только на pa. А значит и Sk делится только на pa, но никак не на pa+1. Доказано. А дальше можно рассматривать простые множители меньше искомого 20192019 , как верхней границы для некоторого числа Sn, и приходить к противоречию в рассуждениях. Или если зайти с другого боку можно показать, что fp(Sn) = fp(n!) для любого n кратного p, предположить обратное и придти опять к противоречию. Изменено 22 марта, 2019 пользователем Fireman Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 22 марта, 2019 Автор Share Опубликовано 22 марта, 2019 Очень простая задачка! Честное слово! Я решил за несколько минут. Найти все целые решения уравнения y^2 = x^3 + 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
thyrex Опубликовано 23 марта, 2019 Share Опубликовано 23 марта, 2019 (изменено) x1 = -1, y1 = 0x2 = 0, y2 = -1x3 = 0, y3 = 1 + x4 = 2, y4 = -3x5 = 2, y5 = 3 Изменено 23 марта, 2019 пользователем thyrex коррекция 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 23 марта, 2019 Автор Share Опубликовано 23 марта, 2019 Выкладки тоже приветствуются! 1 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
E.K. Опубликовано 30 марта, 2019 Автор Share Опубликовано 30 марта, 2019 Очень простая задачка! Честное слово! Я решил за несколько минут. Найти все целые решения уравнения 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 Ссылка на комментарий Поделиться на другие сайты More sharing options...
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти