На празновании корпоратива коллектив компании решил выстроиться колонной и устроить небольшой марш. Выстроились по два человека — одному пары не хватило, по 3 — опять один лишний, по 4, 5 и 6 — то же самое — всегда оставался один лишний человек. Выстроились по 7 — ура! все ширенги оказались полностью укомплектованы.
Сколько человек выходило строиться?
Понятно, что перебором ответ получается найти за пару минут, но здесь желательно привести аналитическое решение.
Здравствуйте, _Me, Вы писали:
_Me>Понятно, что перебором ответ получается найти за пару минут, но здесь желательно привести аналитическое решение.
(N * 6)! + 1 — должно делиться нацело на 7. Где N — либо единица, либо простое число >=7. Значит N * 6! должно делиться нацело на 6. Оно и делится на него. При N >= 7 число сотрудников больше населения Земли. Значит ответ 6! + 1.
Здравствуйте, _Me, Вы писали:
_Me>На празновании корпоратива коллектив компании решил выстроиться колонной и устроить небольшой марш. Выстроились по два человека — одному пары не хватило, по 3 — опять один лишний, по 4, 5 и 6 — то же самое — всегда оставался один лишний человек. Выстроились по 7 — ура! все ширенги оказались полностью укомплектованы. _Me>Сколько человек выходило строиться?
_Me>Понятно, что перебором ответ получается найти за пару минут, но здесь желательно привести аналитическое решение.
Обозначим через N общее количество людей в коллективе
1. Когда, например, выстраиваются по 5 человек и остается один, значит N = 5х+1, где х — целое.
2. Выстраивались по 2,3,4,5,6 человек и оставался один человек, значит N = 60х+1. Т.к. НОК(2,3,4,5,6) = 60
3. Выстроились по 7, все получилось, т.е. общее количество людей N = 7у
4. Решаем уравнение 60х+1 = 7у (п.2 и п.3). В целых числах. Получаем 60*5+1 = 7*43 = 301
Здравствуйте, NotImplemented, Вы писали:
NI>Здравствуйте, Буравчик, Вы писали:
Б>>2. Выстраивались по 2,3,4,5,6 человек и оставался один человек, значит N = 60х+1. Т.к. НОК(2,3,4,5,6) = 60 NI>Неочевидно, пояснять следует.
1. Допустим выстроились по k остался 1 =>
N = kx+1 =>
N-1 = kx =>
(N-1) делится на k (N-1 кратно k)
2. Выстроились по 2,3,4,5,6 оставался 1 =>
(N-1) делится одновременно на 2,3,4,5,6 (N-1 кратно 2,3,4,5,6) =>
(N-1) делится на 60 (НОК 2,3,4,5,6) =>
N-1 = 60x =>
N = 60x + 1
Здравствуйте, Буравчик, Вы писали:
Б>4. Решаем уравнение 60х+1 = 7у (п.2 и п.3). В целых числах. Получаем 60*5+1 = 7*43 = 301
В подобных задачах в этом месте у меня мозг всегда искрить начинал. Вроде бы есть уловки для решения уравнений в целых числах, но я их не помню и всегда решаю перебором. Но чем тогда это решение отличается от решения исходной задачи перебором?
Здравствуйте, _Me, Вы писали:
_Me>Понятно, что перебором ответ получается найти за пару минут, но здесь желательно привести аналитическое решение.
Ключевое слово "китайская теорема об остатках". Русская википедия об этом что-то знает, гугл знает больше. Есть какие-то аналитические решения (насколько простые и практичные — не смотрел). У вас числа не взаимно-простые, но к взаимно-простым свести тоже можно исходя из них (в результате все придет как раз к НОК, как Буравчик и писал).
Здравствуйте, Spiceman, Вы писали:
S>Здравствуйте, Буравчик, Вы писали:
Б>>4. Решаем уравнение 60х+1 = 7у (п.2 и п.3). В целых числах. Получаем 60*5+1 = 7*43 = 301
S>В подобных задачах в этом месте у меня мозг всегда искрить начинал. Вроде бы есть уловки для решения уравнений в целых числах, но я их не помню и всегда решаю перебором.
Для решения линейного уравнения в целых числах вида (ax+by = c) есть не уловки, а вполне конкретный алгоритм решения
S>Но чем тогда это решение отличается от решения исходной задачи перебором?
Из очевидного:
1. Эффективность решения (меньшее количество шагов)
2. Находятся все подходящие решения, а не единственное
Б>Для решения линейного уравнения в целых числах вида (ax+by = c) есть не уловки, а вполне конкретный алгоритм решения
это зависит от того как заданы a,b,c
Если как рациональные числа, то есть конечно.
А если какие-нибудь трансцендентные числа, заданные как предел (алгоритмически генерируемой последовательности), то вряд ли.
Здравствуйте, dilmah, Вы писали:
Б>>Для решения линейного уравнения в целых числах вида (ax+by = c) есть не уловки, а вполне конкретный алгоритм решения
D>это зависит от того как заданы a,b,c D>Если как рациональные числа, то есть конечно. D>А если какие-нибудь трансцендентные числа, заданные как предел (алгоритмически генерируемой последовательности), то вряд ли.
Занятная задачка, кстати.
Есть ли алгоритм, по данным алгебраическим (для трансцендентных ставлю рубль, что нету) a и b определяющий, решается ли ax + by = 1 в целых x,y.
Внешне очень похожа на 10ю проблему Гильберта, но у меня свести не получилось.
Здравствуйте, vnp, Вы писали:
vnp>Есть ли алгоритм, по данным алгебраическим (для трансцендентных ставлю рубль, что нету) a и b определяющий, решается ли ax + by = 1 в целых x,y.
Что значит алгебраическим? Рациональным? Приведите к общему знаменателю, домножьте обе части уравнения на знаменатель и решайте в целых числах уравнение с помощью расширенного алгоритма Евклида.
Здравствуйте, NotImplemented, Вы писали:
NI>Здравствуйте, vnp, Вы писали:
vnp>>Есть ли алгоритм, по данным алгебраическим (для трансцендентных ставлю рубль, что нету) a и b определяющий, решается ли ax + by = 1 в целых x,y.
NI>Что значит алгебраическим? Рациональным? Приведите к общему знаменателю, домножьте обе части уравнения на знаменатель и решайте в целых числах уравнение с помощью расширенного алгоритма Евклида.
