Здравствуйте, GSL, Вы писали:
GSL>Вот лог игры GSL>2, 3, 4, 6, 10..... бесконечность
Если бы каждую монету можно было использовать в сумме ровно по 1 разу, то любая супервозрастающая последовательность нас удовлетворила бы.
Например, степени 2.
Но фишка в том, что вводя очередную монету, мы предполагаем, что таких монет у нас неограниченное количество.
В твоём примере, ход "4" недопустим, поскольку 4=2+2.
Доказательство на пальцах:
Лемма (требует отдельного доказательства):
Имея набор M={m1,m2,...,mk}, мы можем получить любые суммы вида s = gcd(M)*(start(M)+k), где gcd — наибольший общий делитель, а start — некое стартовое значение множителя.
Разумеется, кроме этих сумм, мы можем получать и другие, но пока что рассмотрим только это.
Очевидно, что если M' = M+{m'}, то gcd(M')<=gcd(M), gcd(M')*start(M')<=gcd(M)*start(M) — то есть, добавляя новую монету, мы делаем решето более густым (уж точно — не менее густым).
Возьмём некоторый начальный набор M0. s0=start(M0), g0=gcd(M0).
Разобьём множество натуральных чисел на две части: V0 = [1..s0*g0], N0 = N\V0.
Предположим, что наша игра бесконечна. Это значит, что рано или поздно мы начнём делать ходы из N1. (Поскольку N0 конечно).
Теперь рассмотрим кольцо вычетов N mod g0. G0 = [0..g0-1]
Каждый ход в N1 должен быть не кратным g0, т.е. ему соответствует g = (m mod g0), g!=0.
Однако в этом случае корректируется НОД, g1 = gcd(g0,g), что приводит к сужению кольца: G1=[0..g1-1].
В конце концов, получим gt = 1, кольцо схлопнется — мы вычеркнем все элементы из N0.
После чего останемся с множеством V0, которое также исчерпаем.
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, VsevolodC, Вы писали:
VC>>Очевидно, выигрывает первый игрок, назвав 0 JB>И как с помощью 0 чего-нибудь кроме 0 выплачивать?
Мне как-то показывали монету с цифрой "0" в номинале и какими-то надписями на арабском. Так что, все честно. Только нолик там был слегка кособокий.
Навскидку:
G> 2b. Если у нас уже есть монеты достоинствами x[0]...x[n] (каждого типа — неограниченнок количество), то можно задать вопрос: как нам выплатить данную сумму денег S минимальным общим числом монет? Напишите соответвующую программу.
Видимо необходимо разложить S = i0*x[0] + i1*x[1] + ... + in*x[n] так, чтобы сумма i0 + i1 + ... + in была минимальной.
Если есть монета достоинством 1 задача решается достаточно тривиально. А вот если такой монеты нет... Надо думать.
G> 7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
1. Разделить монеты на две равные кучки.
2. Сравнить вес кучек, в более легкой — все монеты настоящие.
3. Повторять для более тяжелой кучки, пока не останется одна тяжелая монета.
Т. о. минимальное число взвешиваний — логарифм по основанию 2 от исходного кол-ва монет. Для 8 монет: 3 взвешивания.
G> 10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано "ЧЕРНЫЕ", на второй — "БЕЛЫЕ", на третьей — "ЧЕРНЫЕ И БЕЛЫЕ". В одной лежат белые шары, в другой — черные, в оставшейся — и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)
Достаем шарик из "ЧЕРНЫЕ И БЕЛЫЕ".
Если он черный:
в 3-й корзине черные шарики;
в 1-й корзине белые шарики;
во 2-й корзине черные и белые шарики.
Если он белый:
в 3-й корзине белые шарики;
во 2-й корзине черные шарики;
в 1-й корзине черные и белые шарики.
G> 23. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров, она опять столкнулась с бортиком. Тогда рыба повернула на восток, проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)
То есть в круг должен вписываться прямоугольник 6x8. Тогда диаметр бассейна — диагональ прямоугольника.
По т. Пифагора D = sqrt(6*6 + 8*8) = 10 метров.
G> 27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
1. Разнообразные варианты реактивного движения: кидать вещи, дуть и т.д. в противоположном требуемому направлении.
2. Поорать в противоложном направлении — звуковые волны отразятся от противоположного берега и подтолкнут в нужном направлении
3. Аналогично со светом.
G> 29. В какие времена суток положение всех трех стрелок часов (часовой, минутной и секундной) совпадает? (не помню откуда)Разъяснение Часы механические, и стрелки двигаются с равномерной скоростью.
Здравствуйте, Fedor Novikov, Вы писали:
FN>Мне как-то показывали монету с цифрой "0" в номинале и какими-то надписями на арабском. Так что, все честно. Только нолик там был слегка кособокий.
Ага. Это их 5 копеек.
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, GSL, Вы писали:
GSL>>Вот лог игры GSL>>2, 3, 4, 6, 10..... бесконечность JB>Правильная формулировка: "при помощи любого количества монет ранее названных достоинств".
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, GSL, Вы писали:
GSL>>Вот лог игры GSL>>2, 3, 4, 6, 10..... бесконечность
К>Если бы каждую монету можно было использовать в сумме ровно по 1 разу, то любая супервозрастающая последовательность нас удовлетворила бы. К>Например, степени 2.
К>Но фишка в том, что вводя очередную монету, мы предполагаем, что таких монет у нас неограниченное количество. К>В твоём примере, ход "4" недопустим, поскольку 4=2+2.
К>Доказательство на пальцах:
К>Лемма (требует отдельного доказательства): К>Имея набор M={m1,m2,...,mk}, мы можем получить любые суммы вида s = gcd(M)*(start(M)+k), где gcd — наибольший общий делитель, а start — некое стартовое значение множителя.
К>Разумеется, кроме этих сумм, мы можем получать и другие, но пока что рассмотрим только это.
К>Очевидно, что если M' = M+{m'}, то gcd(M')<=gcd(M), gcd(M')*start(M')<=gcd(M)*start(M) — то есть, добавляя новую монету, мы делаем решето более густым (уж точно — не менее густым).
К>Возьмём некоторый начальный набор M0. s0=start(M0), g0=gcd(M0). К>Разобьём множество натуральных чисел на две части: V0 = [1..s0*g0], N0 = N\V0.
К>Предположим, что наша игра бесконечна. Это значит, что рано или поздно мы начнём делать ходы из N1. (Поскольку N0 конечно).
К>Теперь рассмотрим кольцо вычетов N mod g0. G0 = [0..g0-1] К>Каждый ход в N1 должен быть не кратным g0, т.е. ему соответствует g = (m mod g0), g!=0. К>Однако в этом случае корректируется НОД, g1 = gcd(g0,g), что приводит к сужению кольца: G1=[0..g1-1].
К>В конце концов, получим gt = 1, кольцо схлопнется — мы вычеркнем все элементы из N0.
К>После чего останемся с множеством V0, которое также исчерпаем.
Я наверное уже просто давно не читал теории, и такие выкладки несколько сложны, но можно доказать и более чем просто....
Берем монетки от 2 и 3 не сложно показать что, их них можно набрать вот такие суммы
2, 3, 4, 5, 6, 7, 8, 9.....
Ну а теперь все тем, кто папался на такое доказательство предела игры
Просто распирает меня
Вообщем, то что я написал до этого
Это только говорит нам о том, что проиграет тот кто первым назовет 2 или 3 не более того.
Вопрос первоначальный, о доказательстве того что игра не бесконечна, несколько глуп. И вот почему.
Если рассматривать последовательность по вверхсходящей, то да игра не бесконечна( опять же 2 и 3 ). Однако, поробуем идти по низходящей ветке...например если начинать с 1000 то максимально имеем 1000 ходов
1000, 999, 998, 997
А если от бесконечности
бесконечность, бесконечность — 1, бесконечность — 2, ... ?
А что в конце ? А тут в зависимости от того от чего мы оттолкнемся, я бы предпочел от того что бесконечность — N = бесконечность. И у меня в конце бесконечность
Гораздо интереснее придумать тактику выгрыша, а тут надо точно иметь предел верхнего значения. Но скорее всего это будет алгоритм разделяй и властвуй только сильно адаптированный.
Здравствуйте, Grammer, Вы писали:
G>31. У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению, уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части? (Microsoft)
Разрезать по прямой, проходящей через центр симметрии торта и центр симметрии дыры.
Здравствуйте, GSL, Вы писали:
GSL>Здравствуйте, bedward70, Вы писали:
B>> B>>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A.
GSL>А почему sin ? или я чего-то не понял ? BC это вроде через косинус будет Я рассматрнивал верхний угол малого треугольника.
Но можно и прилежащий угол, соответственно COS(60) =0.5, что не повлияет на результат вычислений.
Здравствуйте, GSL, Вы писали:
GSL>Я наверное уже просто давно не читал теории, и такие выкладки несколько сложны, но можно доказать и более чем просто....
GSL>Берем монетки от 2 и 3 не сложно показать что, их них можно набрать вот такие суммы GSL>[b]Итого имеем не то, что ограниченное, имеем просто смехотворное количество монеток 2 и 3.
Естественно. Как только будут названы несколько чисел, у которых НОД = 1 — всё, игра стремительно близится к концу.
Моё доказательство основывалось на том, что через конечное число ходов приходится делать ход, заведомо некратный текущему НОДу — и, как следствие, уменьшающий итоговый НОД.
Почему "через конечное число ходов", а не "на следующий ход"?
Потому что могут быть ходы, кратные НОДу и не кратные ни одной из монет (например, меньшие, чем минимальная монета).
Теперь — доказательство леммы о том, что с помощью двух монет можно получить любые суммы, кратные их НОДу (начиная с некоего стартового значения).
Сперва сократим НОД (очевидно, что умножая/деля строго нацело, мы не меняем картину).
Итак: даны два взаимно простых числа p, q. Доказать, что с их помощью можно получить любые суммы, начиная с некоего стартового значения.
Рассмотрим кольцо по модулю q (пусть p<q).
Числа 0, p, 2p, 3p, ... (q-1)p mod q принимают разные значения, покрывая всё кольцо.
Пусть нам нужно найти разложение для произвольного числа x >= qp. Найдём k такое что x == kp mod q (очевидно, что оно найдётся, см.выше).
Тогда (x-kp)==0 mod q, то есть, (x-kp)==mq. m>=0, потому что x>=qp, а k<q.
Значит, по меньшей мере начиная с произведения (а, если подумать, то начиная с НОК) монет, разложимы все числа, кратные НОД.
Здравствуйте, bedward70, Вы писали:
B>Здравствуйте, GSL, Вы писали:
GSL>>Здравствуйте, bedward70, Вы писали:
B>>> B>>>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A.
GSL>>А почему sin ? или я чего-то не понял ? BC это вроде через косинус будет B> Я рассматрнивал верхний угол малого треугольника. B>Но можно и прилежащий угол, соответственно COS(60) =0.5, что не повлияет на результат вычислений.
Здравствуйте, Retran, Вы писали:
R>Привет!
R>Навскидку:
G>> 7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
R>1. Разделить монеты на две равные кучки. R>2. Сравнить вес кучек, в более легкой — все монеты настоящие. R>3. Повторять для более тяжелой кучки, пока не останется одна тяжелая монета.
R>Т. о. минимальное число взвешиваний — логарифм по основанию 2 от исходного кол-ва монет. Для 8 монет: 3 взвешивания.
Если было бы 9 монет, то наверно решил бы правильно.
R>>Т. о. минимальное число взвешиваний — логарифм по основанию 2 от исходного кол-ва монет. Для 8 монет: 3 взвешивания.
G>Если было бы 9 монет, то наверно решил бы правильно.
Там хорошая подсказка — "тяжелее". Во тесли бы просто отличалась по весу — то тоже бы три было.
А так две
Что мы можем за одно взвешивание? сравнить монету с эталоном.
Т.е. если у нас есть эталон и две монеты (фальшивка + нормальная) — мы находим фальшивку.
8-2 = 6. 6 = 3+3.
Взвешиваем кучки по три монеты. Если они одинаковы — фальшивка не на весах и см. выше.
Если одна кучка тяжелее, то взвешиваем две монеты из кучки и смотри какая тяжелее.
Вот если бы неизвестно было тяжелее/легче, тогда упс
Здравствуйте, Аноним, Вы писали:
А>тема пирога не раскрыта
Очевидно, что переменная толщина колбасы на решение не влияет, если нож движется непрерывно.
Если уж очень хочется, то можно двигать нож со скорость обратно пропорциональной толщине.
Здравствуйте, andyJB, Вы писали:
JB>Вопрос, собственно, какое ещё решение можно придумать?
Проинтегрировать. Это наверное даже не так сложно (думать лень), но первокурсник может и не справиться, а это именно то, что должно придти ему в голову.
Здравствуйте, Grammer, Вы писали:
G>27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
Высморкаться?...
Я, конечно, ничего в этом не понимаю,
но позвольте и мне высказаться!
Здравствуйте, Grammer, Вы писали:
G>6. Вы отправились в прошлое на машине времени и повстречали, ну скажем, Михайло Ломоносова (варианты: А.С. Пушкина, Томаса Эдисона, Николу Теслу итп). Объясните ему, что такое "Интернет"
Очень быстрый курьер.
G> (мое, по Микрософтовской идее). (Садистский вариант: объясните ему, что такое General Protection Failure
Открываете window и горшок с подоконника падает вам на ногу.
G>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
Стрелять насквозь через двоих?
Заготовить ещё стрел?
Договориться?
Спрататься?
Замаскироваться? == Стать орком?
G>>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
R3>Стрелять насквозь через двоих? R3>Заготовить ещё стрел?
Если они эгоситичные — м.б. пристрелить самого первого из них, и пусть они спорят, кто пойдёт первым ?
Нарисовать черту и пристредить кто переступит — и пусть спорят ?
Бегать по кругу и успевать доставать стрелы из трупов ?
Кстати, никто не сказал, а есть ли у него что-то кроме лука и стрел? С десяткой он не справится, но м.б. с пятёркой ?
Перекуём баги на фичи!
Только нолик там был слегка кособокий.
