Конференция "О своем, о девичьем""О своем, о девичьем"
Раздел: ...затрудняюсь выбрать раздел
Отвечать в конференциях и заводить новые темы может любой участник, независимо от наличия регистрации на сайте 7я.ру.
помогите с задачей!
Выбежав после уроков на двор, каждый школьник кинул снежком ровно в одного другого школьника. Докажите, что всех учащихся можно разбить на три команды так, что члены одной команды друг в друга снежками не кидали.
25.01.2010 18:33:14, lsy
41 комментарий
Гм, а я докажу, что это невозможно доказать.
Вот пусть детей было всего двое. Каждый бросил снежком в другого, так? А на 3 команды никак не разобьешь. 26.01.2010 00:45:39, маугленок
И что вы доказали? Что 2 на 3 нацело не делится? Это вроде и раньше было известно. Очевидно, что речь идет о числе большем или равном 3.
26.01.2010 00:52:00, SVETKA
Кошки, не бегающие со скоростью звука к математике не имеют никакого отношения. Что же до формулировки задачи, то если в ней есть нечеткость, то обычно при формулировке решения или доказательства оговариваются условия при которых оно выполняется.
26.01.2010 01:08:00, SVETKA
Вот пусть детей было всего двое. Каждый бросил снежком в другого, так? А на 3 команды никак не разобьешь. 26.01.2010 00:45:39, маугленок
Я привыкла считать, что в задачах по математике НИЧЕГО не очевидно, кроме того, что прямо сказано. Или в крайнем случае - кроме того, что является общеизвестным фактом, например, то, что кошки не бегают быстрее скорости звука (впрочем, эта задача уже по физике :). А если приходится использовать фразы типа "это же очевидно" - значит, задача плохо сформулирована.
26.01.2010 00:59:57, маугленок
Кошка - это из задачи про привязанную к хвосту жестянку :)
А про то, что условия можно оговаривать в решении, а не в задании, я как-то и не подумала :) 26.01.2010 01:15:24, маугленок
А про то, что условия можно оговаривать в решении, а не в задании, я как-то и не подумала :) 26.01.2010 01:15:24, маугленок
Да нет, это как раз ерунда, Света права, доп. условие *дост. много* добавить можно здесь.
26.01.2010 01:08:00, Елна
http://school-sector.relarn.ru/dckt/projects/ctrana/graf/gr1.htm
только там надо мужиков заменить на учеников и сделать оговорку, что n должно быть больше 2-х. 25.01.2010 22:40:19, канемура
только там надо мужиков заменить на учеников и сделать оговорку, что n должно быть больше 2-х. 25.01.2010 22:40:19, канемура
В приведенной Вами задаче каждый пожал руку каждому. В моей задаче - только одному.И ищем мы не общее количество бросков. По-моему, не совсем такая задача.
26.01.2010 00:08:45, Isy
"кинул ровно в 1го" не значит что " получил только один снежок в спину"? если означает, задача решаема только для чисел, ктр делятся на 3.
Как доказать? ну, наверно надо нарисовать круг, на нем 3 точки и "если все кидают только по часовой стрелке то...." 25.01.2010 19:56:25, NatalyaLB
"пары" разбить на 2 команды (одного члена пары в команду №1, другого - в №2)
"треугольники" разбить на 3 команды (№№1,2,3)
"квадраты" разбить в команды 1 и 2 (чередовать точки 1-2-1-2)
"пятиугольники" нумеровать 1-2-1-2-3.
ну и далее по правилу:
"фигуры" с четным количеством точек разбиваем на 2 команды (1-2-1-2...)
с нечетным - на 3 (по правилу 1-2-1-2-1-2...2-3) 25.01.2010 19:48:41, Ci Sara
Спасибо! Сейчас буду рисовать и вникать.
25.01.2010 22:36:26, Isy
SVETKA, а ведь я много-много лет назад в институте программу писала по раскраске графов...А сейчас ребенкину задачу не решила. Голова полностью очистилась:( Спасибо Вам большое!
25.01.2010 22:34:16, Isy
Для трех выбежавших школьников условие верно, потому что они не могут кинуть сами в себя.
Для трех + один решение верно, потому что он может кинуть в "представителя одной команды" и в него может кинуть представитель "другой" (второй или третей) команды и будет еще одна команда, с которой он не "пересекся". И тоже самое для четырех человек и так далее. Получается, что если у нас есть n уже удовлетворяющее условию, n+1 тоже всегда удовлетворяет этому условию. 25.01.2010 20:19:00, SVETKA
Нет, индукция здесь не годится, потому что если на каждом шаге условие выполняется, добавленный должен кидать сам в себя.
25.01.2010 22:51:00, Елна
Нет. Каждый кинул и в каждого попали один раз, цикл завершен, новый участник прибавиться не может.
Потому что надо не просто написать *он может и в него могут*, а надо доказывать, что такие найдутся, но такие не найдутся, на предыд. шаге условие должно быть выполнено тоже.
25.01.2010 23:01:00, Елна
Потому что надо не просто написать *он может и в него могут*, а надо доказывать, что такие найдутся, но такие не найдутся, на предыд. шаге условие должно быть выполнено тоже.
25.01.2010 23:01:00, Елна
Если они не сделаны, надо доказывать, что они могут быть сделаны нужным образом. Это получится индукция по броскам, а не участникам, не знаю, можно ли её удобно(и вообще), расписать, и нужно ли... по-моему, ни к чему.
25.01.2010 23:46:00, Елна
25.01.2010 23:46:00, Елна
Вот именно, они уже все сделаны, никто не может бросить второй раз не из какой команды. Смотрите, второй и третий шаги индукции по участникам: предположим, верно для n, добавляем n+1. Он может бросить? нет, во всех уже попали. В него могут бросить? нет, все уже кинули. На втором шаге.
Света, подумайте немного и поймете, что я хотела сказать.
Сто раз уже зарекалась влезать в темы про задачи, именно потому, что всякая ерунда превращается в ужасающе длинные диалоги. 26.01.2010 00:06:00, Елна
Света, подумайте немного и поймете, что я хотела сказать.
Сто раз уже зарекалась влезать в темы про задачи, именно потому, что всякая ерунда превращается в ужасающе длинные диалоги. 26.01.2010 00:06:00, Елна
Кстати, я поняла, где наврала - в одного могут попасть больше одного раза, теоретически по условию.
Вопрос про *можно* это не снимает, тем не менее. 26.01.2010 01:30:00, Елна
Вопрос про *можно* это не снимает, тем не менее. 26.01.2010 01:30:00, Елна
Если же считать, что каждый участник кинул и получил ровно один удар, то тогда задача решается так, как я описала выше. И порядок сортировки не важен. 26.01.2010 01:47:00, SVETKA
Число полученных снежков точно произвольное.
Что интересно, я нашла решение этой задачи в интернете, но если бы еще поняла его...:) Хотете ответ?:)
Отметим школьников на плоскости точками и соединим стрелочкой, если один кидал во второго. Получившаяся картинка будет выглядеть как несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на четные и нечетные вершины. 26.01.2010 12:34:27, Isy
Что интересно, я нашла решение этой задачи в интернете, но если бы еще поняла его...:) Хотете ответ?:)
Отметим школьников на плоскости точками и соединим стрелочкой, если один кидал во второго. Получившаяся картинка будет выглядеть как несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на четные и нечетные вершины. 26.01.2010 12:34:27, Isy
Если она и решается так, вы этого всё же не объяснили, но это неважно уже, кажется.
Она легко может быть школьной, у меня просто не получается придумывать решение и одновременно эдесь болтать(поэтому обычно отвечаю, только если сразу вижу, не думая), я вон условие в процессе забываю:) 26.01.2010 01:53:00, Елна
Она легко может быть школьной, у меня просто не получается придумывать решение и одновременно эдесь болтать(поэтому обычно отвечаю, только если сразу вижу, не думая), я вон условие в процессе забываю:) 26.01.2010 01:53:00, Елна
Т.е., по броскам всё-таки.
И опять: нельзя писать *можно бросить*, это надо доказывать. 26.01.2010 01:04:00, Елна
И опять: нельзя писать *можно бросить*, это надо доказывать. 26.01.2010 01:04:00, Елна
в условии задачи сказано, что их делят на три команды.
Т.е. если их четверо, то в одной команде будет 2 человека и кто помешает одному из них метнуть снежок в представителя своей команды?
Странная задача какая-то.. 25.01.2010 21:02:08, Hel
Т.е. если их четверо, то в одной команде будет 2 человека и кто помешает одному из них метнуть снежок в представителя своей команды?
Странная задача какая-то.. 25.01.2010 21:02:08, Hel
25.01.2010 21:13:00, SVETKA
Но в условии не сказано, что он обязательно должен кинуть в представителя другой команды. Ну и что, что свой снежок он истратит на представителя своей команды, а представитель третьей команды остался без снежка от него? В него кинут другие школьники..а в кого-то и два снежка прилететь может.
25.01.2010 21:19:56, Hel
Это направленный граф со степенью два. : ) 25.01.2010 21:37:00, SVETKA
аааа...а я поняла условие как будто они выбежали, поделились на команды и после этого стали кидать снежки:)))
25.01.2010 21:40:10, Hel
§ 7. Раскраска графов
Пусть G = (V, E) – некоторый граф. Пусть {1, 2, ..., k} – множество "цветов".
Отображение f: V → {1, 2, ..., k} называют k-раскраской вершин графа G. К-раскраска
называется правильной, если
∀(v1, v2) (v1, v2) ∈ E ⇒ f(v1) ≠ f(v2).
т.е. смежные вершины получают различную окраску. Граф G называется k-
раскрашиваемым, если для него существует правильная k-раскраска. Наименьшее k, для
которого граф G является k-раскрашиваемым, называется хроматическим числом графа
G (обозначение: x(G)). Если x(G) = k, то граф G называется k-хроматическим.
Существует ряд задач кибернетики, которые приводят к раскраске графа (задачи
составления расписаний, обслуживания и др.).
Заметим сначала, что для любого натурального n существует граф G, такой, что
x(G) = n. Примером такого графа является Kn. Очевидно, что x(Kn) = n.
Ясно, что 1-хроматические графы это графы, состоящие из изолированных вер-
шин. 2-хроматические графы – это двудольные графы и только они.
В настоящее время нет описания k-хроматических графов при k ≥ 3. Нет также
эффективных алгоритмов нахождения хроматического числа графа. Однако, имеются
хорошие оценки хроматического числа.
Теорема 1. Пусть p – максимальная степень вершин графа G = (V, E). Тогда
справедливо неравенство
x(G) ≤ p+1
Индукция по n = |V|. Выберем произвольную вершину v ∈ V и удалим ее вме-
сте с инцидентными ей ребрами. Получим граф G′, у которого максимальная степень
вершин р′, причем р′ ≤ p. Число вершин у G′ равно n – 1 и по индукции для G′ имеется
(p′+1)-раскраска, а значит и (p+1)-раскраска. Тогда (p+1) – раскраску для G можно полу-
чить так: окрасим v в цвет, отличный от цветов вершин, смежных с ней, число которых
не больше p.
И согласно этой теореме, в графе второй степени хроматическое число меньше или равно 3м. 25.01.2010 19:59:00, SVETKA
бред
25.01.2010 19:08:38, имхо
Читайте также
Гид по уходу за автомобилем для современной женщины
Узнайте, как легко ухаживать за машиной: от ежедневных проверок до замены расходников. Будьте уверены и в безопасности на дороге!
Почему важно вовремя диагностировать и лечить скрытые родовые травмы у детей
Проблемы со сном, аппетитом или поведением могут быть следствием травмы, которую малыш получил при рождении. В статье расскажем, как распознать такие нарушения и почему важно вовремя их корректировать.
