✓ Как хакнуть секретную информацию? | Ботай со мной
HTML-код
- Опубликовано: 25 ноя 2024
- #БотайСоМной #094
Как хакнуть секретную информацию?
Экшн-квеста по кибербезопасности "CyberFox 2021: Защита от взлома" от Фоксфорда и Лаборатории Касперского: clck.ru/UjJVQ
Книжка от Трушина: trushinbv.ru/book
Как поддержать канал: • Как помочь развитию ка...
Разовая помощь (Яндекс.Деньги): money.yandex.r...
Разовая помощь (PayPal): paypal.me/trus...
Разовая помощь (Donation Alerts): www.donational...
Регулярная помощь (RUclips): / @trushinbv
Регулярная помощь (Patreon): / trushinbv
Онлайн-курсы по математике с Борисом Трушиным:
10 класс. Подготовка к ЕГЭ: trushinbv.ru/ege10
11 класс. Подготовка к ЕГЭ (задания 13-19): trushinbv.ru/eg...
10-11 классы. Подготовка к Перечневым олимпиадам: trushinbv.ru/olymp
Кроме этого, можно купить мои прошлогодние курсы в записи:
Подготовка к ОГЭ: trushinbv.ru/oge9
Подготовка к ЕГЭ. Задания 1-12: trushinbv.ru/eg...
Подготовка к ЕГЭ. Задания 13 и 15: trushinbv.ru/eg...
Подготовка к ЕГЭ. Задание 14: trushinbv.ru/ege14
Подготовка к ЕГЭ. Задание 16: trushinbv.ru/ege16
Подготовка к ЕГЭ. Задание 17: trushinbv.ru/ege17
Подготовка к ЕГЭ. Задание 18: trushinbv.ru/ege18
Подготовка к ЕГЭ. Задание 19: trushinbv.ru/ege19
Другие курсы Фоксфорда: trushinbv.ru/co...
Репетиторы Фоксфорда: trushinbv.ru/coach
Личный сайт: TrushinBV.ru
Группа "Олимпиады, ЕГЭ и ОГЭ по математике": ege_tru...
Группа "TrushinBV.ru": trushin...
Личная страница: trushinbv
Группа "TrushinBV.ru": / trushinbv
Личная страница: / boris.trushin
Инстаграм: / trushinbv
TikTok: / trushinbv
Telegram: t.me/trushinbv
Twitter: / trushinbv
RUclips-канал: / trushinbv
#БотайСоМной #094
Как хакнуть секретную информацию?
Экшн-квеста по кибербезопасности "CyberFox 2021: Защита от взлома" от Фоксфорда и Лаборатории Касперского: clck.ru/UjJVQ
я хотел сказать , что в прошлом видео стояла такая цель : за какое наименьшее количество действий можно сломать шоколадку ; и я отвечу если создать шкалу допустимый действий , то можно на ней определить что самая максимальное количество действий в этом случае получается 59 , а минимальное 1 действие , и вот ответ: за одно действие , по тому что , куда ещё меньше ; здесь не спрашивают каким способом здесь спрашивают другое ; ещё вот интересный вопрос как это доказать это , на этот вопрос я не знаю как ответить ; и прошу извинения что ошибся потому что я тупой 12ти летний подросток
я тоже подумал что 1
Ещё интересная задача с олимпиады 10 класса 2008 года: Какое точное время будут показывать часы когда минутная и часовая стрелка пересекутся в области между 6 и 7 часами?
Наверное я тупой, но я не понял ничего, кроме тог7о что это была реклама. Что мы должны были получить? Что мы в итоге расшифровали? Что нам даст эта сумма??
@@ii_parody если наложатся друг на друг на друто то 6:32;5 если пересекутся то 6:30
Следующее видео: как скрыться от спецслужб
для начала отозвать разрешение геолокации для всех приложений в смартфоне и включить режим полёта (отключит сим-карту)
@@СергейКраснов-й4в начать пользоваться приложением Signal, у которого исключительно сквозное шифрование (E2E), так еще и опенсурсный
@@purplep3466 +
@@СергейКраснов-й4в некоторые телефоны даже когда выключены посылают сигналы, так что чтобы скрыться от спецслужб, в идеале нужно вообще не использовать технику с выходом в интернет или со связью и не жить в большом городе. И с людьми не контактировать. Такая вот грустная правда. Можно, конечно, попробовать, как Сноуден, пользоваться специальным софтом, но тут надо реально шарить.
@@Kokurorokuko Это какие такие телефоны посылают сигналы в выключенном состоянии?
Сразу до ответа не догадался, конечно, но когда Борис начал подсказывать и задавать наводящие вопросы, смог дойти до ответа.
я догадался, когда она сказал, представить, что это однозначные числа
Называется как избежать решение системы из 100 уравнений с 100 неизвестными
Просто сделать 2 шага
В сторону двери. 🗿
Топ контент крипта пошла
графия
гео
Пошел конвеер топ контента, спасибо)
0:04 аннигиляторная пушка
Придумал алгоритм сразу, как только вы сказали про однозначные числа)
Согласен, какая-то ничтожно простая задача, вряд-ли такое хоть в одну олимпиаду впихнут
@@ВладимирЧем любая сложная задача становится простой после решения ^_^
Есть опыт перевода чисел из одной системы счисления в другую, подозреваю.
Сразу пришло в голову преобразование по основанию.
И я, как сказали про однозначные, сразу решил мгновенно. Сначала таинственно, да
Спасибо вам Борис за ваше старание👏👏👏👏
Для того что бы доказать, что за один ход решить задачу нельзя достаточно предъявить для произвольной комбинации a1, a2, ... a100 два разных варианта секретной информации из которых получается один и тот же результат после применения к ним этой комбинации.
Например такие:
Для x1 = a1, x2 = a1, ... x100 = a1 вернётся результат a1*a1 + a2*a1 + ... + a100*a1 или по другому a1*(a1+a2+...+a100).
Но такой же результат вернётся и для секретной информации вида x1 = (a1+a2+...+a100), x2 = 0, ... x100 = 0. ЧТД
Да, как-то так, только нужно немного поправить, чтобы иксы были натуральными
@@trushinbv Что тут трудного: вместо х1,...,х100 нужно взять n1,...,n100.
@@mxMik , возможно, имелось ввиду, что "0" не принадлежит к натуральным числам согласно их определению в русских источниках)..
@@КириллСергеевич-м6д Это была шутка юмора. Типа, полковник проводит занятия по тактической подготовке. "Допустим у противника имеется M танков.... нет, M танков маловато, пусть будет N танков." В мое время целые числа обозначали буквами i,j,k,l,m,n, a вещественные х,у,z. Про мнимые боюсь и вспоминать, а кого-то даже еврейским алфавитом. А еще надо было помнить, что R это радиус, а v это скорость, иначе тебя построят буквой зю. В общем, прямой угол кипит при температуре 90 градусов.
Сергей Кусков - молодец! 🤝
🙋Без нулей (которые не являются натуральными числами) правильнее рассуждать так:
Последовательность {(x1+x100)/2;(x2+x99)/2;...;(x49+x52)/2;(x50+x51)/2;(x51+x50)/2;(x52+x49)/2;...;(x99+x2)/2;(x100+x1)/2} перемноженная попарно (поэлементно) с проверочной последовательностью {1;1;...;1} даст в результате такую же сумму как и последовательность (x1;x2;...;x100}. Уже из одного этого противоречия следует, что за один ход не получится достоверно узнать исходную последовательность. Вот такое вот у меня исключение 🤷
Бот, когда я ему задал первое число, которое обрабатывать 10000¹⁰⁰⁰⁰⁰⁰⁰ лет:🤓
*Конгениально!* Самостоятельно, увы, не додумался.
Классное видео! Отличная задача! Я не сразу понял, как решать)
ВАУ! Это действительно круто! Спасибо!
Мне пришло в голову немного другое, но похожее решение: также делаем оценку чисел, а вторым ходом задаем коэффициенты M/p1; M/p2; ...; M/p100, где p1, p2, ..., p100 - простые числа такие, что min{p} > max{x}; и M = p1*p2*...*p100. Пусть мы получим число A. Тогда xi = A % pi. Кому интересно, эти рассуждения крайне схожи с китайской теоремой об остатках.
спасибо)
Борис, у Вас вид фокусника, который вытаскивает кроликов из шляпы
Что-то похожее было на олимпиадке по информатике
Отличная задача.
Пока пуперы ищут годный сурс и пупят его, Борис TRUEшин пупит сам себя
Забавно, что при двух шагах компьютеру надо сделать 298 операций (99 сложений на первом шаге, 100 умножений и 99 сложений на втором шаге) не учитывая действий для извлечения из полученного числа какого-то числа последовательности. При наивном же способе в сто шагов нам понадобиться всего 100 умножений , ведь сложения нивелируются нулями в наших последовательностях. Поэтому способ в 2 шага сложнее способа в 100 шагов.
Красиво
Классная задача, решил за десять секунд
Пусть у нас существует такая последовательность a _i, что она определяет любую x_i за один ход.
1) Пусть НОД всех a_i =k, b_i =k/ a_i
Тогда рассмотрим такую секр. информацию x_i= 2b_i
Тогда наш ответ от компа равен 200k
Ну и легко придумать еще один пример с такой же суммой, например y_1 = 3b_1, y_2 = b_2, y_i = 2b_i, при i > 2
В этом случае ответы для последовательностей x_i и y_i совпадают и определить какая именно загадана не получится
Понял задачу сам, решил еë, но самое легкое сделать не смог, а именно доказать
как всегда, топ!)
С поступашек аву взял?
@@may_be_Leo у друга одолжил)
Здорово! Спасибо, интересно!)
Генетический алгоритм в помощь, заменить все х на 1 и запустить его, для 100 чисел через минуту или меньше будет ответ
(Поправка) с нулями и правда проще)))
(Поправка) за одну попытку можно взломать используя суперпозицию реальности, в одном из n^100 степени раз в одной реальности будет ответ с первого раза))
Спасибо. И спасибо за упражнение. )) я работал программистом и сразу решил задачу. Я бы сказал что это задача по информатике а не по математике. Это задача как разместить в памяти целые положительные числа чтобы точно хватило место- сколько байт. ))
Это задача прототип нейронных сетей в программировании
БВ, круто объяснили, спасибо))
Если сумма равна S, то каждое из чисел не превосходит S-99, и достаточно использовать S-98-ичную систему счисления, т.е. назвать числа (S-98)^99, (S-98)^98, ... (S-98)^0
Да, конечно. Только это чуть дольше объяснять )
КАТАРСИС!
Кстати, если рассматривать для иксов только положительные вещественные, то таким же методом (зная сколько комп хранит знаков после запятой) можно определить все числа (все равно компьютер бы их округлял)))
3:52 кибербуллинг, хаха)
Воспользуемся для дешифровки гиперкомплексными числами с размерностью пространства сто - центунионами. Тогда и вещественные можно угадать за один раз. Разве что алфавита может не хватить.
Хорошая задача, для заведомо однозначных даже сам решил
Вот это контент подъехал
Школота путает недостижимость числа 10^99 путем последовательного прибавления единицы (в текущей физической вселенной), типа, огромное, и мизерность ресурсов, необходимых для его хранения и арифметических операций с ним (для простоты, 100 байт). Длинное число - просто массив или строка. Числом его делают алгоритмы обработки.
Да. натуральные числа дают серьёзное ограничение. Почти та же задача:
Есть полином Nной степени. надо узнать его коэффициенты с помощью решателя, который на любое вещественное число даст точное значение полинома.
Эта задачка попроще и решается быстрее.
Задача показалась не очень трудной, но спасибо, хорошая разминка.
По ассоциации с ней есть такая задача, которую я хорошо решить не могу.
Имеется набор номиналов монеток (x_1,..,x_n), n -- не очень большое, x_i натуральное и можно даже считать что все x_i меньше 100. Предположим, что НОД( x_1,...,x_n) = 1
Понятно, что в этом случае начиная с какого-то X любую сумму можно выдать монетками номиналов x_1...x_n ( т.е. все числа больше X преставимы в виде сумм a_i*x_i где a_i натуральное или ноль).
Требуется придумать как получать хорошую нижнюю границу для X
В отличии от других задач на канале, эту сходу решил, таким же методом как и Борис, только степени выставил по возрастанию с первого элемента типа: x1*10^n*0, x2*10^n*1, x3*10^n*2, ... x100*10^n*99,
n так же вычислил, скармливая все 1 на первом вызове.
Зацепила задачка, второй день мысли вокруг. Кстати, если X - действительные конечные числа, то задачка также решается в 2 хода, причем все также с натуральными "a"
Что такое «конечные числа»?
@@trushinbv конечные десятичные числа/дроби
Для меня доказать то, что два шага это минимум оказалось гораздо сложнее, чем придумать алгоритм
По идее, когда мы умножаем все числа последовательности на 1 и получаем их сумму, нужно из этой суммы вычесть 99, и только тогда оценивать сколько знаков получилось в данном числе
Можно, но необязательно )
Получилось за три набора угадать для последовательности дейтсвительных)))) , минут 5 заняло , но вот до такой красоты нужно ещё догадаться )))
Т.к мы не знаем какое число будет больше суммы всех чисел, то мы не можем с уверенностью сказать в какой интервал нулей с 100% точностью поместиться наибольшее число из ряда, следовательно точность результата неизвестна, поэтому знание суммы необходимо, получение которого требует дополнительный шаг, исходя из этого для выполнения данной задачи необходимо как минимум два шага.
P.S. Сомневаюсь в корректности доказательства, но я попытался
Это рассмотрение частного случая, что числа будут искаться умножением на степень 10, так что это не доказательство, что в принципе нельзя за 1 ход
@@duartyom3468 Я об этом подумал, но решил все-таки записать поток мыслей, спасибо.
Допустим можно с помощью последовательности (а, в, с, ...), Но если в искомой последовательности будут стоят числа (а+в, а+в, 0, ..., 0) то результат будет (а+в)², а если в искомой последовательности (а+2в, в, 0, ..., 0), то результатом будет также (а+в)². То есть при различных неизвестных числах получили одинаковый результат (такого быть не может), значит в искомой последовательности стоят одинаковые числа, то есть а+в=а+2в, а+в=в, то есть а=в=0. Но тогда "угадывающая" последовательность будет начинаться с двух нулей, чего очевидно быть не может.
Следующее видео: как разложить огромное число в сумму простых за одно действие)))
Изи задача, в детском саду решали. Раскладываем на кучу двоек и тройку.
Запомните этот день. Трушин начал добавлять рекламу)
Это уже раз 10 было ))
А ничего что человек работает в фоксфорде сам. Не рассказать о своей работе оч странное. И не бинарные рейд шейдоу лутбоксы рекламист,а прикольные штуки
@@werwolfwaffen3657 Во первых я это знаю, и получше тибя, во вторых я ничего против не имею
Интересно, как они на Фортране в 60х годах оперировали 600-значными числами :)
Ровно так же, как и сейчас))
Скалярное произведение - плохой кандидат на асимметричный шифр +)
В начале все единицы. Потом что-то вроде xn = 10^(n * (len(str(res)) + 5))
пишешь на python?
@@nikita_x44 да
И как долго будет вычислять компухтер такие сколько угодно большие числа...
Кстати я вот до сих пор не могу добиться задачи с олимпиады, которая звучит так:" Докажите, можно ли выразить единицу в виде суммы четырех различных квадратов несокращаемых рациональных чисел?".Я нашел как выразить - (2/9)² + (4/9)² + (5/9)² + (6/9)² (сокращаемая, собака!).Ясно, что тут общий делитель 81, а сумма знаменателей (4+16+25+36) 81, равно один, но я не подобрал несокращаемых случаев, а тем более не понял как составить доказательство или опровержение.Было бы интересно увидеть ролик по данной задаче)
(3/5)^2 + (4/5)^2
?
@@cb_q лин, не уточнил, четырех
@@cb_q забываю постоянно длинное определение
@@bluebaby2349 а, тогда ясно, а то уж больно простой задача показалась.
и наверное еще есть ограничение на знаменатель? т.к. в вашем примере можно было бы сказать что берем (2/9)² + (4/9)² + (5/9)² + (2/3)² и получаем 1, все дроби в суме уже несократимы.
Как на счёт 1+0?)
Поставил на паузу. Есть хороший подход для решения задач: попробовать решить аналогичную задачу с меньшей размерностью. Кажется, что если взять 3 натуральных числа, то решение должно быть за 2 и менее ходов, иначе должен быть какой-то минимальный порог, или задача решается ровно за кол-во ходов, равное кол-ву неизвестных. Попробовав решить задачу для n = 3 пришел к варианту с 2 ходами для любого n.
Есть еще вариант, когда на втором шаге в качестве "a" передавать степени суммы, полученной на первом шаге, начиная с нулевой (хотя это не принципиально, главное, чтобы каждое "a" было с разной степенью) . Ну а далее полученную на 2 шаге сумму раскрутить, последовательно деля на степени и вычитая дробную часть из остающейся суммы. Саму дробную часть умножаем на делитель на этом шаге и получаем одно из чисел.
Такое решение кажется более аналитичным. Ну и строго говоря, будет работать со степенью любого числа, большего, чем максимальное в исходном ряду.
Вроде все.
@@АртемГоловацкий-м7щ.Я бы этот вариант в двух словах назвал" Переход в систему исчисления максимального числа") Мне тоже как-то так хотелось решить, к тому же с т. зр. программирования вариант может оказаться чуть оптимальнее по скорости выполнения (если числа не помещаются в 1 регистр и т п )
Но с точки зрения педагогической простоты, Бориса подход намного удобнее и понятнее на мой взгляд) поэтому всё супер))
@@КириллСергеевич-м6д ничего страшного в сложности нет. Больно все разленились сейчас, все подавай простое и готовое. Еще небось большинство просто послушают решение, не поймут ни фига, зато уйдут довольные собой, типа "ну я примерно так и думал, задача фигня, умею решать такие пачками теперь"
Только вот в примере на ~ 8:43 используется 128-битный компьютер что ли ;)
Ну нафиг, я думал что-то про четность/кратность будет..
Klass
нечего не понял, но ооочень интересно! Борис спасибо!
1 вроде не было сказанно что числа идут по возрастанию тогда если х100 последние, как либо значное то возможна ошибка
2 нужен очень мощный компьютер иначе 10^10 комп не осилит и возможно быстрее провернуть операцию с единичной (вроде так правильно называется матрица с диоганалью из 1 и всеми остальными нулями) матрицей.
1. Возрастание не влияет на решение. Например, если секретная последовательность 1, 5, ..., 245, 13, 51 и мы знаем, что сумма не превышает 1000, то, умножив числа как на видео, получим 10050...245013051. Если число однозначное, то слева будет стоять 2 нуля, если двузначное - всего один ноль, ну и без нулей в последнем случае.
2. Компьютер в качестве примера взяли. Так то и человека можно посадить считать всё это
Ну
Банально
Если идти по пути который мы избрали
Умножая на 10^n
То среди натуральных всегда найдëтся такое, что оно будет больше любого 10^n
Наверно так
Я знаю как за 2 хода: 1) первая последовалельность (1,1,1,1,1....1)-> получаем некое натуральное число X (большее чем любое из x). 2) берем число N = 10^n, большее чем X, вторая поcледовательность будет (N^0, N^1, N^2,... N^99) вместо 10 можно взять любое другое основание, это только для удобства.
Прикольная задача. Ну, кажется, что за 1 ход нельзя, как минимум потому, что мы вообще ничего не знаем о последовательности. У нас даже примерной оценки нет, то есть мы не можем просто взять огромную степень десятки и верить, что больших этой десятки чисел в последовательности нет. Множество натуральных бесконечно, значит числа могут быть бесконечно большими, и всегда найдётся такое натуральное, которое больше, чем десятка в степени, на которую мы будем умножать. Не знаю, на сколько достаточно такого рассуждения, просто то, что в голову пришло.
1. Слово "угадать" в данном контексте неприемлемо.
2. Хотелось бы знать, как в реальности считают большие числа на компах - когда разрядности не хватает?
Очень просто, надо просто взять и запрограммировать длинную арифметику.
2. Есть разные приемы счета "длинных" чисел. Если требуется точность - каждый "знак" в отдельной ячейке памяти. 100 значное число - выделили 100 ячеек. Сложение и вычитание - попарно для каждого разряда с переносом остатка. Умножение и деление обычно не используют. Так же для декодирования и кодирования в число системы счисления N - используется логарифмическая аппроксимация. На практике редко попадаются программы.
Пример: warcraft 3 orpg the kingdom of kaliron. Сейв код - строка из букв латинского алфавита заглавных и строчных и цифр - 62 разрядные числа. Примерно 60-80 длина строки.В них компактно кодируются внутриигровые характеристики - золото, опыт, предметы на голове плечах ногах и т. д. Версия 1 - 3.3.3. Начиная с 3.3.4 алгоритм изменили из-за сильных тормозов во время считывания кода.
Если точность не требуется то обычно используют lua или basic, для которых есть специальные библиотеки.
По факту современный компьютер обрабатывает одновременно 32(64) бита информации. Встроенный сопроцессор(математический процессор) обрабатывает числа с плавающей запятой в формате мантиса+экспонента. При этом на мантису и экспоненту выделено фиксированное количество памяти и числа выходящие за пределы - округляются. Поэтому для точности редко используют, но для казуальных расчетов - самое модное.
иногда бывают случаи, что и за 1 ход можно получить ответ. напрмер, если мы все числа умножим на 1 (a_i=1), и получим сумму 100, то понятно, что и каждый x_i=1.
докажем, что в общем случае такой фокус не прокатит от противного. допустим, что есть некая последовательность {a_i}, такая что по ней любой набор определяется однозначно, то есть для любых двух разных наборов {x_i} и {x'_i} будет получаться разная сумма. но такого не может быть. предъявим два различных набора, дающих одну и ту же сумму:
x_i=a1+1
x'_1=(a1+...+a100)+1; x'_i=1, i>1
нетрудно проверить, что для обоих наборов сумма будет (a1+1)(a1+...+a100)
Зашёл написать коммент о возможном решении в 1 ход, если все иксы единицы, а он уже здесь)
Отличное решение - браво, Timur!!!
Но если первое число будет 5 значное а 2 число будет 5568 значное? Откуда ми знаем што они такие?
Всего-то 1400 знаков будет у последнего числа
Почему 1400, а не, например 56789?
@@canis_mjr я про рассматриваемый пример
так то все хорошо, если компуктер сможет выполнить операцию с таким большим числом) а если - нихт, катись все по экспоненте)
С каким большим? Тут ограничений нет
@@Uni-Coder я не про "тут", а про компуктер
@@компаниядоставкиЕдадомой.ру Вопрос остаётся - с каким "таким большим"?
В видео промелькнули 100-значные числа по основанию 10 млн, это порядка 10^800, т.е. примерно 2^2700.
Я в питоне генерирую рандомное 2700-битное число, потом второе, потом складываю и умножаю их - показывает 0 микросекунд...
Для компуктера это ерунда, а не числа.
Взять тот же протокол HTTPS, по которому вы выходите в интернет - там трафик шифруется и расшифровывается ключом 2048 бит, и вы этого даже не замечаете
Некорректно сформулирована задача. Я сначала подумал, что x1..x100 - натуральные числа строго от 1 до 100, и коэффициенты a1..a100 тоже могут быть только от 1 до 100, причем по одному разу :(
А где я говорил про то, что это "натуральные числа строго от 1 до 100"?
Не, все там четко, пересмотри.
Тут даже не столько натуральность играет роль, сколько конечность формы записи чисел или иными словами точность
В том и суть, что множество натуральных чисел принадлежит к счётным бесконечным множествам (там даже в определении про него, вроде, говорится), в отличие от множества действительных чисел, принадлежащего к несчётным.
В предложенном решении во первых нет ни слова о машинном представлении, во вторых тут принципиально именно то, что числа натуральны. Машинное представление является вторичным по отношению к множествам чисел из математики.
@@canis_mjr Причем тут машинное представление? Если вы знаете, что количество знаков в записи числа не больше определенного, то задача решается аналогично. А натуральные числа как раз подходят под определение. Разве что знак еще важен
@@elliotalderson6609 натуральные числа как раз снимают вопрос со знаком. Первый запрос и определяет эту длину, максимальную, заранее принципиально неизвестную.
@@canis_mjr Мне кажется мы друг друга не поняли. Я пытаюсь сказать, что если например будет иррациональное число зашифровано, то его уж точно не угадать. Аналогично, если там есть как отрицательные так и положительные числа. Но числа вида A,BCDEF..(
Если коэффициенты и ответ вещественные и точные, то можно за одну попытку: умножить на иррациональные коэффициенты (корни из простых чисел).
Так если загаданные числа тоже произвольные вещественные, то что ты по ответу сможете понять?
Умножить на 0.1 дальше на 0.01 и тп
Осталось только понять как умножать на 10^99 в степени как минимум. Или компьютеры такое умеют? Пока что кажется, что решение через систему уравнений будет работать быстрее
В с++ тип long double может хранить числа до 2.2 * 10^308 и занимает такое число 16 байт
Чтобы работать с числами длиннее можно, например, просто запихнуть их в строки и работать уже со строками
@@AnanasClassic ого, я помнил примерно только обычный long и там совсем скромный диапозон. Не знал, что в double он такой огромный
@@peachok3564 Различных long double чисел не больше 10^40
Блин, деформация уже профессиональная. Думаю: какой х1 в начале, когда там х0 должно быть =)
Хитро замаскированная задача про позиционные системы счисления с различным базисом. Программистам это хорошо известная вещь: разложение числа в базисе какой-либо системы счисления, буть то двоичная, шестнадцатиричная или всем известная десятичная.
Можно оптимизировать эту задачу с помощью двоичных сдвигов.
1 шаг) Посылаем последовательность из 100 единиц и получаем на выходе число x1 + x2 + ... + x100. Находим ближайшую степень двойки, которая больше, либо равна этому числу (2^n).
2 шаг) Посылаем последовательность
(2^n)^99, (2^n)^98, ..., 2^n, 1 и полученное число переводим в двоичную систему счисления. Далее разбиваем пачками полученное число с конца по n бит, и получаем 100 n-значных двоичных чисел. Переводим из в десятичную систему счисления и получаем ответ.
А почему это оптимальнее?
@@trushinbv Это оптимальнее с точки зрения программирования, т.к. нужно хранить меньше данных, хотя с точки зрения математики это все то же самое решение :)
На самом деле мы не знаем архитектуру "олимпиадного" компьютера. Если в результате 1го теста выявили что самое большое число 17 - Вы округлите потолок до 32( 2 в 5й), вместо 100. А можно ведь пользоваться степенями 17го числа. На практике это не займет много времени. Сам по себе алгоритм перевода из одной системы счисления в другую тоже прост. Только зачем?
Эх, а если бы в качестве своей последовательности можно было подсовывать действительные числа, то и за 1 раз бы можно было угадать...
Подскажите как?)
@@КириллСергеевич-м6д ну достаточно подобрать 100 действительных чисел, линейно независимых в поле рациональных чисел. например квадратные корни из первых 100 простых чисел точно подойдут. Правда разложение по базису окажется в общем случае довольно нетривиальной задачей
До ответа сразу додумался, но как программист скажу что если после первого хода число получится слишком большое, прям очень большое, то быстрее будет задать цикл на 100 ходов и подставлять 1 для каждого Х, чем ждать пока компьютер высчитает 10^n (при n->inf), если вообще сможет это сделать и не случится переполнения памяти и ошибка)
Борис, если бы можно было сообщать не только натуральные числа, а, скажем, действительные, то можно было бы получить за 1 шаг, предложив в качестве своего ряда чисел - набор из 100 иррациональных. Тогда из полученной суммы, как минимум полным перебором - можно получить исходный ряд чисел.
А загадывать можно только натуральные?
А что значит "ботай"?
Недавно возник следующий вопрос. Вот есть у нас уравнение фигуры P(x,y)=0 (также P(x,y,z)=0), интересно, а как меняется уравнение при определённых видах движения?
Почитайте про матрицы поворота
Задача, конечно, никак не учитывает затрачиваемые ресурсы при выполнении таких вычислений. Если судить даже по однозначным числам, то это очень огромное число 10^99, про 10^198 вообще молчу. Проблема ведь в хранении данных. А мы хотим получать ответ в течение нескольких секунд. Метод вычисления за 100 операций более реален и будет гораздо быстрее выполняться в действительности. Поправьте меня, если неправ.
Ну решение системы 100 уравнений тоже не так уж тривиально
@@duartyom3468 ты смотрел видео? Трушин явно сказал, какие наборы последовательностей брать, чтобы очень быстро посчитать все эти числа. Да и решение системы уравнений 100*100 всё же может оказаться проще, т.к. написать соответствующий код не так уж и сложно. Ты же не руками будешь считать это. А вот хранить 100-значные числа компьютеру тяжело. Конечно, python посчитает и 1000-значные, но это долго.
В этом есть смысл. Но такое дело что тебе придется создать 100 последовательностей, где одна 1 и остальные 0. А во втором случае вы создаёте только две. Если увеличить число переменных тут всё равно две последовательностей и две суммы. При чём этот вариант очень чувствителен к начальным условиям. Например запретят нули в последовательности. Тогда что делать будешь? Определители искать начнёшь или научишь компьютеру создавать хитрожопые уравнения друг под друга. А другой алгоритм всегда работает пока числа натуральные и не выпрыгнул за пределы программы.
@@СергейКондратьев-д7з я смотрел видео и предлагаю написать тебе код, который бы решал хотя бы систему из 3 уравнений, чтобы ты понял, что не всё так однозначно
Добавлю заранее
Понятное дело, что решение системы вычислительнее проще, чем работа с большимт числами, но задача не про это. Тем более мы сами это не вычисляем
А разве где-то в задаче спрашивалось, как хранить такие числа? Или о том, что мы хотим ответ за секунды?
Я соглашусь, что это весьма нетривиальная задача.
Но, мне кажется, часть про хранение и скорость додумана и не подразумевается исходной задачей.
Всё же это разминка для мозга, забавная абстракция, о которой можно думать, а не практическая задача, которую нужно решать.
Рассуждение-док-во того, что нельзя за один раз угадать последовательность:
Так как числа могут быть бесконечно большими, всегда может получиться такая ситуация, когда выбранное нами число 10^n , где n это натуральное целое число, будет меньше. Вроде бы и всё :)
Нас же никто не заставляет брать именно степени десятки брать. Вдруг есть какой-то совсем другой набор, который сразу решает )
А ответ в следующем видео будет?
Сразу сложно догадаться 😅
Взрыв мозга. Жаль такие задачи в вузе не решают. Тупо заставляют зубрить теорию, которую никто не помнит уже на следующий семестр. Навыков школьника тут за глаза хватает, но весь мой курс матана вряд ли бы решил это.
А в рамках какого курса такие задачи надо решать? Вас не смущает, что вас учат не задачи решать а инструмент для решения задач дают.
@@canis_mjr не дают как бы. Чисто если по знаниям тут справиться должен и восьмиклассник. Инструмент по решению таких задач нельзя получить просто если сказать что понадобится. Их нужно часто задавать, решать и учить как надо думать, в каком направлении. Это вам не квадратное уравнение, где сказал формулу и решил. Вообще неправильно к матану относятся люди. Это учение о том как надо думать а не мерить интегралом паркет на полу.
@@archilarkania7203 так я у вас и спрашиваю, в рамках каких курсов надо такое решать?
Разделы математики дают как инструмент для решения прикладных задач в рамках специальности.
Такие задачи это факультативы, олимпиады, хобби, но ни как не процесс обучения.
@@canis_mjr у нас на факультете мата есть такой предмет основной на первом курсе - основы программирования, без которого не проидёшь никуда. Там была часть про алгоритмы вот как раз эта тема. Поколениями народ этот предмет сдавал только со второй или с 3 попытки. Это просто кошмар был хотя учили нас как будто обычной школьной хуите. Так что направление даже сейчас существует просто её надо в школе учить и потом в универе требовать.
@@archilarkania7203 основы программирования говорите? Я преподаю основы программирования, мы там учим синтаксис языка, примитивные алгоритмы типа переменные переставить местами, массив отсортировать, максимум число перевести из десятичной системы в двоичную. У меня самые сильные студенты то не сразу смогут запрограммировать функцию расчёта определителя, через разложение по строки/столбцу, которая пишется за 5 минут.
Сейчас студенты приходя тна кафедру программной инженерии, которые с программированием сталкиваются в первый раз, элементы массива в обратном порядке записать - практически неподъёмная задача без помощи гугла, а вы тут что-то говорите про идентификацию системы.
А в какой тип данных влезет хотя бы стозначное число?) Задачка ведь была про взлом компьютерной базы данных)
Если очень заморочиться, то подобный тип данных как класс можно определить самому, так же как и все необходимые операции над ним)
Длинная арифметика снимает такое ограничение...
(java.math) BigInteger
За один раз нельзя, потому что если набор, на который говорят умножить, это a1, a2, ... a100, и если получится ответ a1*a2*...*a100 + (a1 + a2 + ... + a100), то есть слишком много вариантов, какими xi могут быть. Например (a2*...*a100 + 1, 1, 1, ... 1) ; (1, a1*a3*a4*...*a100 + 1, 1, ... 1) и т.д.
А можно узнать,это из высшей математики?
Ребят или сам Борис а можете мне обьяснить хотя бы коротко зачем мы каждый раз берем число больше когда узнаём сумму всех чисел ?
Не уверен, что понимаю вопрос. Можно поподробнее?
@@cheekibreeki904 ну вот когда мы узнавали что число к примеру семизначное зачем мы множили на восьмизначное число ?
@@Omanar_416 затем, что в восьмизначном числе семь нулей, и умножение на него будет сдвигать каждое число в последовательности ровно на семь разрядов.
...а потом они кричат "кибербуллинг"! Проливая на свитшот свой вишневый пудинг
В Америке задачу не оценят, там ноль считается натуральным числом))) весь такой алгоритм летит к чертям)
а первое решение за 100 шагов не работает - a1,a2,...,a100 по условию натуральные хехе, нули нельзя
Но если функция считает сумму не приближенно, то можно просто дать последовательность иррациональных чисел (корень из двух, корень из трёх и т.д.). Таким образом сумма будет (x1*корень2 + x2*корень3 и т.д.). Вот и решение в один ход.
Ты тоже задаёшь только натуральные числа, не прошёл твой фокус
если бы а1, ...., а100 были бы векторами можно было бы получить за 1 раз)
оспорю, пруфани
@@hippomaru2119
Пусть а1, ....., а100 это 100-мерные вектора и
a1 = (1, 0, 0, ....., 0)
a2 = (0, 1, 0, ....., 0)
a3 = (0, 0, 1, ....., 0)
.....
a100 = (0, 0, 0, ....., 1)
Тогда
x1a1 = (x1, 0, 0, ....., 0)
x2a2 = (0, x2, 0, ....., 0)
x3a3 = (0, 0, x3, ....., 0)
.....
x100a100 = (0, 0, 0, ....., x100)
Ну и тогда сумма
x1a1 + x2a2 + ..... + x100a100 = (x1, x2, ....., x100)
Все числа у тебя на руках и за 1 действие)
@@antonmanin3521 лол ты имеешь ввиду х просто числа а а вектора? неее, так то понятно, только у тебя последовательности все таки одного пространства должны быть, так не пойдет :)
@@hippomaru2119 сразу же написал что только а вектора
Борис, что вы думаете об Проекта Венера? Очень хочется, чтобы вы познакомились с данным проектом! Время не пожалеете)
Математика, математикой, а число более чем 2^64 в компьютер довольное проблематично засунуть и, к сожалению, не все так просто
это длинная арифметика, валим)
@@Hocotun Даже длинная арифметика не поможет, если тот компьютер, который выдает сумму, выдает ее в int или long...
@@Шесть-по-пять а почему не строка?
@@РоманПолоз Может и строка, но, боюсь, что этого компьютера уже давно нет с нами и проверить, какой тип данных на нем использовался не представляется возможным)
Так то верно, но есть специальные библиотеки программные - для работы с числами любой длины. Для шифрования используют ключи размера до 1024 бит. Тот же ssl https
Хакерсь починалась би з X0
Интересно, решение этой задачи поможет открыть сейф, где деньги лежат?
Думал намного серьёзней задача будет.
Если не криптография во всей красе, то хотя-бы введение в неё.
В итоге результат не помещается в int.
зато помещается в big integer. В языке Haskell они например, встроены из коробки, часто с их помощью методом подбора решал разные очень сложные задачи) Например с их помощью можно вычислить, чему равен к примеру, тангенс 10^100, получив достаточно огромную дробь, приближающую число пи с достаточной точностью.
По поводу доказательства того, что за один раз нельзя гарантированно узнать информацию:
Даже если мы сотое число умножим на 1цу ,99е на 10^n, 98е число на на 10^2n и наконец первое число на 10^99n, то возможен вариант когда максимальное число из секретной последовательности состоит из n+1 знаков, тогда первая попытка не сработает.
Вроде такое доказательство, что одной попытки не хватит
Нельзя за 1 ход сделать потому-что мы не знаем максимально возможную длину самого большого числа в последовательности.
А если мы, допустим, скажем: пусть максимально длинное в ней будет 1000 (3 знака). То, если это не так, и в ней есть хотя бы 1000 (999+1 = 4 знака), все преобразования со степенью 1000^x перемешаются, и разгадать будет сложно (но возможно? - тут не знаю, может и нет)
Для этого нужно добавить массив, состоящий только из 1 (вначале так сделал, но потом узнал, что не так понял условие) и мы узнаем максимально возможную длину чисел в исходной последовательности, т.к. очевидно, что длина суммы чисел больше или равна длины максимально длинного числа в этой сумме. (как доказать, без понятия, скорее всего по типу (1x+10x+100x+...+10^nx) + (1x+10x+100x+...+10^nx) = 2(...), но хотелось бы это узнать точно, надеюсь, кто-то в ответе расскажет)
P.S: поступаю в университет на инженерное программирование, учу Java, C++, C# и другие (кроме Python, т.к. я очень трепетно отношусь к памяти носителя, а этот язык использует много её по моим меркам)
То, что за один ход нельзя сделать данным подходом, понятно и так. Надо доказать, что вообще за один ход не узнать, в общем случае.