руccкий
english
РЕГИСТРАЦИЯ
ВХОД
Баку:
15 окт.
20:09
Помочь нам долларом - рублём ЗДЕСЬ
> подробно

Форум: Communities: Строгая задача

Начало

shg1
апр. 10, 2006 03:08

Communities: Строгая задача

Community: Шевелим извилинами


Статья: Строгая задача
Автор: shg1
Опубликовано: 2006-03-28 20:50

прочитать
 
Всего ответов: 16
Показывать
Все комментарииРейтинг
Ответы
Uluchshajzer
авг. 18, 2009 23:10
Занумеруем группу из шести человек A, B, C, D, E и F. Выберем одного человека из группы, допустим A. Ясно, что при любом раскладе, из оставшихся пяти человек у A будут иметься, по крайней мере, либо трое знакомых, либо трое незнакомых ему людей. Предположим, что у A имеется трое знакомых. Допустим это B, C, и D. Тогда, если какие-либо двое из этой тройки обоюдно знакомы, скажем B и C, то мы получаем тройку попарно знакомых между собой - A, B и С. Точно также, если в тройке B, C и D нет знакомых между собой, получаем тройку попарно незнакомых между собой людей - B, C и D. Что и требовалось доказать.
Kamo60
авг. 17, 2009 10:54
Я не понял решения. 6 точек можно соединит 8 палочками при этом не образуя ни одного треуголника.

A-C, A-D, B-E, B-F, C-D, C-F, D-E, i E-F

Я нашел другое решение.

Обозначим линии когда оба человека знакомы между собоы красним (К) тсветом, и не знакоми зеленим (Z) тсветом.

Поыдем от противного. Среди трех линиы соединяюшиых A, B и C по кране мере две лини будут одного тсвета. Для простоты допустим что это линии тсвета Z. Имеем три линии.

A-Z-B, A-Z-C, B-K-C

Среди линиы соединаюших D, E, F будет по краынеы мере одна тсвета Z. Пуст это будет D-Z-E. Продолжаем дорисовыват линии. Среди линиы А-Е и А-D будет по кране мере одна К, пуст это будет А-К-Е.

Среди B-F и C-F по краынеы мере одна Z. Так как линии симметрични, то пуст это будет B-Z-F. Далше рисуем A-K-F (A-B-F), E-Z-F (A-E-F), B-K-E (B-E-F), D-K-F (D-E-F), A-Z-D (A-D-F), C-Z-E (B-C-E), C-K-D (C-D-E), B-Z-D (B-C-D). Получилос что треуголник A-B-D соединен линиями Z.

This is not trivial solution. It'll be interesting to hear trivial solution.
нояб. 27, 2006 20:48
Vstretilis 6 chelovek. Dlya togo, c htobi im vsem vstretit'sya, oni dolzhni imet' minimum odnogo znakomogo, kot. ob etoy vstreche soobschil bi. Mozhet bit' dva varianta:

1. Cep' , t.e. perviy soobschaet vtoromu, vtoroy svoemu zankomomu-tretyemu i t.d. po cepochke, do 6go... Togda oznachaet, chto kak minimum troe ne znayut drug druga.

2. Odin soobschaet minimum dvoim znakomim o vstreche. Sledovatel'no, vse troe znayut drug druga...

sirocco00
май 25, 2006 02:44
Точно! Условия задачи не ясны.
Обоюдно надо заменить словом "взаимно" (?)
Тогда: А, В и С втроём знают друг друга или втроём не знают друг друга .
А вот как насчёт слова "либо" ?
Это слово значит ХОR (exclussive ОR)? или просто ОR?
май 24, 2006 17:44
Да, что это значит: трое обоюдно знакомы? Слово "обоюдно" имеет "2 конца", то есть нельзя сказать "обоюдно" про троиx. Они знакомы "троюдно", то есть все знают всеx?
Трое "обоюдно незнакому" - значит никто не знает никого?
май 16, 2006 02:09
Хорошо бы также доказать, что если у вас 8 палочек и шесть точек, то как бы вы не соединяли ими точки, по крайней мере всегда будет получаться 1 треугольник.

Это можно по моему сделать так : Докажем от противного . Нам удалось соединить 6 точек при помощи 8 палочек и при этом не образуя ни одного треугольника . Если у вас 8 палочек - то это значит 16 концов. На 6 точек получается что как минимум 2 точки имеют не больше 2 соединений. ( 6 * 3 = 18 ) .
Если удалить две эти точки и палочки - связи к ним , то останется по крайней мере 4 точки и 5 палочек ( Связей не может быть 4 ( на остальные 4 точки останется 4 связи - тогда мы выберем другие точки ) . А это помятно , что как бы вы не старались с ними у вас всегда получится треугольник.
май 13, 2006 02:08
По моему уже понятно , что предполагается что если А знает В , то В знает А ( обоюдно знакомы ) и наоборот если А не знает В , то В не знает А ( незнакомы) .
По моему только тогда задача имеет смысл .
sirocco00
май 12, 2006 22:40
A very productive Staff Meeting, I guess!
У меня вопрос к господину шг1:
" Докажите, что в любой группе из шести человек трое либо обоюдно знакомы, либо обоюдно незнакомы. "
Вопрос: "обоюдно незнакомы" значит:
1. оба друг друга не знают.
2. (игра слов): отрицание слов "обоюдно знакомы". Т.е. не обоюдно знакомы.
Напишите пожалуйста какой из двух вариантов вы имели в виду?
А то мы тут голову ломаем...
Thanks!

май 11, 2006 07:02
Я сегодня сидел на staff meeting и вместо того чтобы дремать как всегда, думал об этой вашей задаче.
Если у нас есть 6 вершин то есть 15 линий соединить их. Предположим если знакомы А и В, будем соединять их красной палочкой , если не знают то синей.
Если мы возьмем 7 палочек ,например красных , то мы можем соединить 6 вершин не создавая треугольников А - В - С - D - E -F - A + соединить предположим А и D . Но куда бы вы не поставили 8 -ю палочку - у вас получится треугольник .
Ясно что у вас должно быть или 8 или больше каких то палошек - или краснух или синих. Mне лично так каажется.

май 5, 2006 02:36
Пусть меня поправят более умные товарищи , но у меня в таком случае получается что возможно , чтобы каждый знал кого-то или никого и не было "взаимного знания или незнания".

Для этого А должен знать 5 остальных , В - остальных 4 ( всех кроме А ) , С - остальных троих , и т.д. и послединий бы никого не знал . Разве это невозможно ?
I am confused . Где же я не прав ?


sirocco00
май 4, 2006 23:27
По моему: нет.
это "one to one mapping" ?
а-->б и б-->а
а-->c и c-->а
???
май 4, 2006 05:49
Ответьте пожалуйста - если А знает В и В знает С , означает ли это , что А знает С и С знает А ?
shg1
апр. 10, 2006 03:08
Данная задача является очень интересной задачей, хотя и имеет достаточное простое доказательство. Эту задачу в 2002 году я задал одному профессору в Риге, который преподает студентам дискретную математику. Уважаемый профессор достаточно хитер (не путать ни с талантом, ни умом!), ибо, как потом обнаружил, он при своем довольно ограниченном знание, мастерски умеет создать миф о себя как об очень сильном математике (в 2002 я об этом еще не знал). Так вот, через некоторое время этот профессор категорично утверждал (причем, очередной раз сделав умный вид), что иной метод доказательства, чем метод полного перебора для данной задачи не придумать. Тогда я доказал ему, а также другим коллегам, которые присутствовали на этом спектакле, что эту задачу можно доказать 7 различными методами, один из которых является наиболее тривиальным. С тех пор уважаемый профессор, увы, .... Но, это уже не имеет отношение к данной задаче.

Дерзайте и наслаждайтесь своими творениями!

Удачи Вам!!!