Главная > Конференции > О своем, о девичьем

Конференция "О своем, о девичьем""О своем, о девичьем"

В блог Подписаться на Дзен!

Отвечать в конференциях и заводить новые темы может любой участник, независимо от наличия регистрации на сайте 7я.ру.

помогите с задачей!

Выбежав после уроков на двор, каждый школьник кинул снежком ровно в одного другого школьника. Докажите, что всех учащихся можно разбить на три команды так, что члены одной команды друг в друга снежками не кидали.

25.01.2010 18:33:14, lsy

41 комментарий

От кого:

Вы не авторизованы. Авторизоваться

Если Вы отправите сообщение анонимно, то потеряете возможность редактировать и удалить это сообщение после отправки.

E-mail:

получать ответы на E-mail

показывать ссылки на изображения в виде картинок

Гм, а я докажу, что это невозможно доказать.
Вот пусть детей было всего двое. Каждый бросил снежком в другого, так? А на 3 команды никак не разобьешь. 26.01.2010 00:45:39, маугленок

И что вы доказали? Что 2 на 3 нацело не делится? Это вроде и раньше было известно. Очевидно, что речь идет о числе большем или равном 3. 26.01.2010 00:52:00, SVETKA

Я привыкла считать, что в задачах по математике НИЧЕГО не очевидно, кроме того, что прямо сказано. Или в крайнем случае - кроме того, что является общеизвестным фактом, например, то, что кошки не бегают быстрее скорости звука (впрочем, эта задача уже по физике :). А если приходится использовать фразы типа "это же очевидно" - значит, задача плохо сформулирована. 26.01.2010 00:59:57, маугленок

Кошки, не бегающие со скоростью звука к математике не имеют никакого отношения. Что же до формулировки задачи, то если в ней есть нечеткость, то обычно при формулировке решения или доказательства оговариваются условия при которых оно выполняется. 26.01.2010 01:08:00, SVETKA

Кошка - это из задачи про привязанную к хвосту жестянку :)
А про то, что условия можно оговаривать в решении, а не в задании, я как-то и не подумала :) 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, канемура

В приведенной Вами задаче каждый пожал руку каждому. В моей задаче - только одному.И ищем мы не общее количество бросков. По-моему, не совсем такая задача. 26.01.2010 00:08:45, Isy

Лен, ссылку надо давать в строке Ссылка, тогда она будет активной

[ссылка]

25.01.2010 23:52:53, Zeta

если число равно или больше 3, делим на 3, остаток приписываем к любой команде. Если детей было 2, то нельзя доказать.
"кинул ровно в 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

ой, там же могут быть еще "звездочки" - когда несколько бросили в одного. 26.01.2010 12:30:43, Ci Sara

Спасибо! Сейчас буду рисовать и вникать. 25.01.2010 22:36:26, Isy

Рисовать не надо, только запутаетесь. Вожно понять что для трех условие удовлетворяется, для 3+1 удовлетворяется, и если n удовлетворяет условию задачи, то n+1 тоже удовлетворяет. Этого достаточно для доказательства. 25.01.2010 22:55:00, SVETKA

Теория графов? Хорошая задача. : ) 25.01.2010 19:30:00, SVETKA

SVETKA, а ведь я много-много лет назад в институте программу писала по раскраске графов...А сейчас ребенкину задачу не решила. Голова полностью очистилась:( Спасибо Вам большое! 25.01.2010 22:34:16, Isy

А если это решение для школьника, то тогда так.
Для трех выбежавших школьников условие верно, потому что они не могут кинуть сами в себя.
Для трех + один решение верно, потому что он может кинуть в "представителя одной команды" и в него может кинуть представитель "другой" (второй или третей) команды и будет еще одна команда, с которой он не "пересекся". И тоже самое для четырех человек и так далее. Получается, что если у нас есть n уже удовлетворяющее условию, n+1 тоже всегда удовлетворяет этому условию. 25.01.2010 20:19:00, SVETKA

Нет, индукция здесь не годится, потому что если на каждом шаге условие выполняется, добавленный должен кидать сам в себя. 25.01.2010 22:51:00, Елна

Нет, не должен. Важно, чтобы условие выполнялось на первом шаге (трое) и дальше для любого n+1 25.01.2010 22:53:00, SVETKA

Нет. Каждый кинул и в каждого попали один раз, цикл завершен, новый участник прибавиться не может.
Потому что надо не просто написать *он может и в него могут*, а надо доказывать, что такие найдутся, но такие не найдутся, на предыд. шаге условие должно быть выполнено тоже.
25.01.2010 23:01:00, Елна

Цикл выполнился для полного количества участников. Речь же идет о сортировке участников на три команды ПОСЛЕ того, как все броски были сделаны. 25.01.2010 23:25:00, SVETKA

Если они не сделаны, надо доказывать, что они могут быть сделаны нужным образом. Это получится индукция по броскам, а не участникам, не знаю, можно ли её удобно(и вообще), расписать, и нужно ли... по-моему, ни к чему.
25.01.2010 23:46:00, Елна

Вы фантазируете. В условии задачи сказано, что броски уже сделаны. Случайным образом. И нужно доказать, что участников можно поделить на три команды. Исходя из того, какие броски ими УЖЕ сделаны. 25.01.2010 23:49:00, SVETKA

Вот именно, они уже все сделаны, никто не может бросить второй раз не из какой команды. Смотрите, второй и третий шаги индукции по участникам: предположим, верно для n, добавляем n+1. Он может бросить? нет, во всех уже попали. В него могут бросить? нет, все уже кинули. На втором шаге.

Света, подумайте немного и поймете, что я хотела сказать.
Сто раз уже зарекалась влезать в темы про задачи, именно потому, что всякая ерунда превращается в ужасающе длинные диалоги. 26.01.2010 00:06:00, Елна

n - это не максимальное количество участников, это порядковый номер участника внутри произвольного количества, хоть m, хоть z. 26.01.2010 00:51:00, SVETKA

Кстати, я поняла, где наврала - в одного могут попасть больше одного раза, теоретически по условию.
Вопрос про *можно* это не снимает, тем не менее. 26.01.2010 01:30:00, Елна

Да, я тоже об этом подумала сейчас. Уже не школьная задача получается, если предположить, что число "полученных" снежков произвольное. Тогда нужно, действительно, описывать правила сортировки участников исходя из того сколько ударов они получили, "формировать кластеры".

Если же считать, что каждый участник кинул и получил ровно один удар, то тогда задача решается так, как я описала выше. И порядок сортировки не важен. 26.01.2010 01:47:00, SVETKA

Число полученных снежков точно произвольное.

Что интересно, я нашла решение этой задачи в интернете, но если бы еще поняла его...:) Хотете ответ?:)

Отметим школьников на плоскости точками и соединим стрелочкой, если один кидал во второго. Получившаяся картинка будет выглядеть как несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на четные и нечетные вершины. 26.01.2010 12:34:27, Isy

Если она и решается так, вы этого всё же не объяснили, но это неважно уже, кажется.

Она легко может быть школьной, у меня просто не получается придумывать решение и одновременно эдесь болтать(поэтому обычно отвечаю, только если сразу вижу, не думая), я вон условие в процессе забываю:) 26.01.2010 01:53:00, Елна

Т.е., по броскам всё-таки.
И опять: нельзя писать *можно бросить*, это надо доказывать. 26.01.2010 01:04:00, Елна

в условии задачи сказано, что их делят на три команды.
Т.е. если их четверо, то в одной команде будет 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

я тоже думала, что должно быть три или нечетное число. Но ведь эти три человека могут кидать друг в друга по кругу:) или я не права? 25.01.2010 20:34:03, М@Алина

Какая разница как они кидают. Три человека всегда могут быть поделены на три команды, поскольку они не могут кинуть в самого себя. 25.01.2010 20:35:00, SVETKA

мда... не математик я:( 25.01.2010 20:57:07, М@Алина

А кто эту задачу решает? Потому что в общем виде это на самом деле теорема:
§ 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:19:37, GalaNTka

бред 25.01.2010 19:08:38, имхо

Вернуться в конференцию

помогите с задачей!

Загруженные изображения