|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
28.09.2012, 19:42 | #21 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Имеем группы A, B, C элементов разных цветов.
Ka, Kb, Kc - количество элементов в группах. Пусть Ka-Kb=2n (n>=0). Такие две группы есть при любых раскладах. Каждый элемент группы B спариваем с элементом нруппы A. Получаем Kb цвета C Осталось 2n цвета A. Один элемент из каждой оставшейся пары спариваем с элементом группы C. Получаем элемент цвета B, который в свою очередь спариваем с оставшимся элементом пары - получаем элемент цвета C. Все ADD - вот написал, только заметил прокол в логике. Это не пойдет
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 28.09.2012 в 19:49. |
28.09.2012, 20:24 | #22 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
1) Получается что k = у всех групп. А это не так.
2) Хорошо спариваем (хотя они только встречались ) ka + k(+2)b = k*2c + 2b опять же косяк. Вот нашел в интернетике решение через системы уравнений : Ответ - НЕТ Выразим цвета при помощи переменных: x - красный y - зеленый z - синий Цвета не одинаковые а значит: х≠у≠z Допустим возможность образования одного цвета: 13x+15y+17z=45x или 13x+15y+17z=45y или 13x+15y+17z=45z С условия мы знаем: x+y=2z x+z=2y y+z=2x Создадим систему: {13x+15y+17z=45y {x+y=2z {x+z=2y {y+x=2x Решаем систему: 13x+15y+17z+x+y+x+z+y+z=45y+2x+2y+2 z 15x+17y+19z=2x+47y+2z Выразим z через x и y: z=(x+y)\2 15x+17y+19*((x+y)\2)=2x+47y+2*((x+y )\2) 24,5x+26,5y=3x+48y 21,5x=21,5y x=y - а это невозможно: красный≠зеленый Ладно, более-менее разобрались,(еще б TinMan прокомментировал вообще бы супер было) Вот другая (Кстати я её тоже решил) Заключенные и переключатель В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу? Последний раз редактировалось Poma][a; 28.09.2012 в 21:15. |
29.09.2012, 01:56 | #23 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Мне кажется, условие (я про хамелеонов) совешенно ясное. Но все же его можно сделать еще яснее - вот так:
"На острове живут хамелеоны, принимающие 3 цвета. В некоторый момент было такое распределение: 13, 15 и 17. При встрече двух разных цветов, оба перекрашиваются в третий. Если других случаев перекрашивания не наблюдается, то может ли случиться, что все они окажутся одного цвета?" можно, ессно! Но сначала я хотел про твое решение пару слов - Okay? Сначала хочу уточнить: инвариантом тут являются не сами остатки от деления на 3 (сами они изменяются). Их сумма (снова по модулю 3) - да, есть инвариант, но это бесполезно. Инвариантом является сам ВИД распределения этих остатков - то, что там обязательно один 0, одна 1, и одна 2 - вот это неизменно. И интересно еще - почему это так. Начав решать, некоторое время я думал про четность, но оно как-то не помогало.. И типа ради хохмы проскочила мысля - мож, "третичность" (типа как четность, но по отношению к 3)? И тут разу заметил, что вычитание 1 и прибавление 2 эквивалентны по модулю 3. И стал копать дальше.. )) Теперь пояснения к "общему дубовому" решению.. a - начальное кол-во хамелеонов 1го цвета b - начальное кол-во хамелеонов 2го цвета c - начальное кол-во хамелеонов 3го цвета пусть на некоторый момент произошло: x - количество встреч ха. 2го и 3го цветов (с перекрашиванием в 1й) y - количество встреч ха. 1го и 3го цветов (с перекрашиванием во 2й) z - количество встреч ха. 1го и 2го цветов (с перекрашиванием в 3й) если мы хотим занулить 1й и 2й цвета, то кол-во ха. 3го цвета будет a+b+c a +2x -y -z = 0 b -x +2y -z = 0 c -x -y +2z = a+b+c Это система, я выписываю ее матрицу (после простых преобразований) и столбец свободных членов Код:
1. a=b=c=1, столбец свободных членов: 1 1 -2 Подставляем его на место первого столбца матрицы. Получившаяся матрица снова имеет нулевой детерминант. Следовательно, решений бесконечное число. Это согласуется с тем, что этот случай имел бы ответ ДА (встречаются два любых, и все становятся одного цвета). 2. Наш случай. Лень выписывать (муторно переключать раскладку)). Подстановка свободного на место любого дает матрицу с ненулевым детерминантом. Следовательно, решений нет. addendum Строго говоря, это решение нужно провести для всех пар цветов, для какой-то одной пары может найтись решение. Но в нашем случае решений нет ни для какой пары.
Предпочитаю на "ты".
Последний раз редактировалось TinMan; 29.09.2012 в 11:46. |
30.09.2012, 21:03 | #24 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Огромное спасибо!
Да-да. Согласен. Всё верно. Спасибо за разъяснения. |
30.09.2012, 23:24 | #25 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
1. Заключенные выбирают ведущего
2. Только он может включить и включает, как только видит выключенный 3. Остальные - только выключать и каждый не более 2 раз и выключают, как только видят включенный (если лимит не исчерпан) 4. Как только ведущий насчитает 17 своих включений можно смело идти на свободу Одного выключения для каждого из остальных не достаточно - ведущий не знает начального положения выключателя add В случае, если первый раз ведущий находит выключатель в положении выключено 17 раз маловато, а 18 в самый раз
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 01.10.2012 в 07:32. |
01.10.2012, 21:45 | #26 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Ага-ага. Сам долго просидел когда модератор задал вопрос про преодоление неизвестности начального положения выключателя.
Ок. Еще одна. Пусть хоть кто-то развлечется И так есть кольцевая дорога, на ней стоит n заправок (стоя эти заправки Random'но). Есть старый Вазик, с огромным баком, который вмещает любое кол-во бензина (Умели же люди машины делать ). Так же известно, что суммарного кол-ва бензина нам хватит что бы доехать из нашей точки в конечную точку (=наша начальная точка). Нужно доказать что есть такая точка, от которой можно начать движение и гарантированно мы попадем в место начала движения. Я решал так (поскольку моё решение может "вытолкнуть" Вашу гениальную мысль, то я выделил беленьким, кому надо тот выделит, другой же пройдет мимо) : от противного доказал что-то, и рекурсия |
02.10.2012, 04:14 | #27 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Эх, жалко, что тут нет тега [spoiler] или [hide], чтоб скрывать свой ответ от тех, кто хочет еще подумать. Можно, конечно, делать как Ромаха (красить ответ в белый цвет), но это не очень здорово смотрится. Я за все выходные (!) так и не смог выбрать времени подумать как следует над задачей про заключенных и выключатель.. А задача хорошая, и теперь уже мозги не почистишь, память не сотрешь, свой hard drive в башке не переформатируешь.. )) В любом случае - спасибо и за задачу, и за решение!
Теперь по поводу следующей задачи - "ралли консервной банки по Галактике" )). Лирическое отступление: сделать машину с большим баком совсем несложно: надо просто весь салон отвести под бензобак. Даже удивительно, что ВАЗовские конструкторы не додумались до такого. Водителю не хватит места? фигня, пусть выходит и тянет машинку за собой на вервочке.. Кстати, вы этом случае и подкапотное пространство тоже можно освободить от уже ненужного двигателя и использовать под бензобак! А как же люди, спросите вы? А пусть goto на поле, пахать.. )) Самое интересное, что, в отсутствие двигателя, расход бензина падает практически до нуля - и получаем экологически чистый автомобиль, способный проехать неограниченное расстояние на одной заправке.. Задача, мне кажется, несложная (проще предыдущих), но в ней все же есть своя изюминка. Нижеследующее адресуется Ромахе, начавшему разговор белым по белому.. << hidden text begins << Что ты имеешь в виду под "рекурсией"? Извини, но мы говорим не про программу на Pascal/C/etc! Может, ты подразумевал индукцию? Если да, то - я сомневаюсь, что она тут применима.. >> end of hidden text >>
Предпочитаю на "ты".
|
02.10.2012, 19:54 | #28 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Продолжим белые дебаты :
Именно рекурсия(может в математике называется по-другому (кажется не официальное название - Метод Чайника(тоесть - Как заварить чай? - Берем чайник наливаем воду, ..... - А если в чайнике уже вода? - Ставим на плиту,... - А математик сказал бы так : выливаем воду, получаем предыдущюю задачу, которая уже решена ))) Здесь же (Шаг А1) я доказал что-то (от противного), (Шаг А2) и на основании этого доказательства, рассматривал движение от одной(произвольной) точки, далее "стягивал" круг (тоесть соединял нашу точку ( от начала движения) и точку по к которой мы прибыли) далее повторялось действие Шаг А2(уже с n-1 кол-вом заправок) до тех пор пока не останется 2 заправки. А далее снова на основании док-ва от провивного. И всё Кстати - хамелеоны - 4 б Побег - 3 б А про Вазик - 5 б (по пятибалльной шкале ) Последний раз редактировалось Poma][a; 02.10.2012 в 20:54. |
04.10.2012, 07:13 | #29 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Гм. Мне кажется, все же пора нам с тобой поиметь совесть и перелезть в личку. Хотя, не исключено, что наш с тобой белый текст читает кто-то еще, и что он находит его интересным для себя..
======= белый текст: ============= Ромаха, я (думаю, что я) понимаю, о чем ты говоришь. В математике употребляется термин "индукция" (слово "рекурсия" буквально означает "повторный вход", при этом подразумевается, что в процедуру, так что это чисто программистский термин), и это не просто термин, а точно определенное понятие (как и все в математике). С твоего позволения, я все же оставлю за собой право на сомнения в твоем доказательстве - по крайней мере до тех пор, пока я не увижу его полностью. Если не хочешь показывать его тут (хотя, мне кажется, уже пора играть в открытую)), пришли мне в личке. ======= конец белого текста ======== Ну, оценка сложности задач может быть слишком субъективна, я на своей не стану настаивать.
Предпочитаю на "ты".
|
04.10.2012, 16:39 | #30 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Карты на стол
Предположим, что нельзя найти любую такую бензоколонку, от которой мы сможем "проехать" к любой другой (разумеется с некоторым кол-вом бензина, которое мы "найдем" на бензоколонке), тогда чтобы проехать от x1 до х2 на не хватает а1, чтобы проехать от х2 к х3 нам не хватает а2, ....., чтобы проехать от х(n-1) к x(n) нам не хватает a(n), и наконец чтобы проехать от x(n) до x1 нам не хватает a(n) бензина. И так сделаем вывод - чтобы проехать от x1 до x1 (по кольцу) нам не хватит a1 + a2 + a3 + ... +a(n-1) + a(n) бензина. Но ведь известно что бензина хватает => противоречие => можно найти хотя бы одну точку, от которой мы сможем проехать хотя бы еще до одной заправки. (часть 1) И так рассмотрим обобщенный вариант решения данной задачи. Найдем точку, которую можно использовать как начальную (от неё можно совершить хотя бы один проезд к другой заправке). Обозначим её 1. Мы можем отъехать от неё как минимум к точке 2(при этом слив весь бензин из точки 1, у нас останется какое-то кол-во бензина, даже возможно равное 0) Дальше возьмем, и соединим точки 1 и точки 2 в точку 1'. Вазик окажется в точке 1' c пустым баков. А бензин в точке 1' будет = бензин в точке 1 + бензин в точке 2 Дальше мы получаем задачу точно такую же задачу, НО с кол-вом параметров не n, а n-1. // Именно это и было названо рекурсией. Решаем её методом "?" до тех пор пока не останется 1 колонки. И всё. Теперь про по воду рекурсии и индукции, это два разных понятия. Индукция - Метод доказательства утверждений типа: «Для каждого натурального числа n верно, что ... ». Такое утверждение можно рассматривать как цепочку утверждений: «Для n= 1 верно, что ... », «Дляn= 2 верно, что ... », и т.д. Вот нашел в математическом словарике слово Редукция - сведение исходной задачи к другой, более простой (например, что бы найти сумму внутренних углов многоугольника, можно разрезать его на треугольники). Но всё равно другое значение. Вот цитата Вики Цитата:
(Да кстати возможно у Вас сложится не правильное мнение что я пытаюсь оправдаться, я лишь хочу найти подтверждение или опровержение существования рекурсии в математике.) Последний раз редактировалось Poma][a; 05.10.2012 в 14:41. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
игры | ivan12ivan | Общие вопросы по Java, Java SE, Kotlin | 2 | 07.03.2012 09:06 |
игры | Епгений | Общие вопросы Delphi | 14 | 14.05.2011 16:40 |
Моделирование человеческого разума булевской математикой | Fog | Свободное общение | 28 | 12.11.2010 06:51 |
разработка игры "Реверси". Имеется код этой игры на С++ | CD-RW | Помощь студентам | 0 | 28.03.2010 00:13 |