Вход | Регистрация

  1  2   
О жизни... :: Математика и алгоритмы

OFF: Задачка. Есть гора писем от N человек

OFF: Задачка. Есть гора писем от N человек
Я
   ERWINS
 
15.06.18 - 11:39
Есть гора писем от N человек

Сколько должно быть N, что бы гарантировано нашлась цепочка из 7 человек которые писали друг другу или не писали друг другу?
 
 
   NSSerg
 
1 - 15.06.18 - 11:40
37
   ERWINS
 
2 - 15.06.18 - 11:40
(1) нет
   NSSerg
 
3 - 15.06.18 - 11:41
6*6+1
Шесть групп по шесть человек, в каждой письма только внутри группы. добавление одного человека вызывает (0)
   Asmody
 
4 - 15.06.18 - 11:41
(0) Если А0 пишет только А1 и наоборот, то N может быть сколь угодно большим, но цепочки не будет.
   ERWINS
 
5 - 15.06.18 - 11:44
(4) A0 A2 A4 A6 A8 A10 A12 не пишут друг другу
   ERWINS
 
6 - 15.06.18 - 11:46
(3) ты привел когда так, а надо доказать что при любой конфигурации и фиксированном N будет такая структура
   Ненавижу 1С
 
7 - 15.06.18 - 11:47
что такое "цепочка из 7 человек которые писали друг другу"?
   Asmody
 
8 - 15.06.18 - 11:47
(5) Тогда это задача про связность орграфа.
   ERWINS
 
9 - 15.06.18 - 11:50
(8) неорграфа
   Basilio
 
10 - 15.06.18 - 11:51
13
 
 Рекламное место пустует
   ERWINS
 
11 - 15.06.18 - 11:51
(7) 2 человека или посылали письма друг другу или не посылали
(есть ребро графа или нет) ну или можно интерпретировать как полносвязный граф, где ребра 2х цветов
   ERWINS
 
12 - 15.06.18 - 11:52
(10) нет
   Ненавижу 1С
 
13 - 15.06.18 - 11:52
(11) это понятно, а остальное? я про "цепочка из 7 человек которые писали друг другу"
   ERWINS
 
14 - 15.06.18 - 11:54
(13) допустим если писали то все ребра синии, если не писали, то все ребра красные
   Малыш Джон
 
15 - 15.06.18 - 11:54
задача странно сформулирована

Есть гора писем(т.е. хз сколько). какое количество чеовек должно было участвовать в написании этой горы(хз, кто -  сколько, может все кроме одного написали по одному письму, а остальные письма накатал последний), чтобы нашлась цепочка из 7 писем.
   ERWINS
 
16 - 15.06.18 - 11:55
(15) задачи часто странно сформулированы
   Малыш Джон
 
17 - 15.06.18 - 11:57
(16) странно = неполно или нечетко = решение возможно, только если самостоятельно додумать начальные условия
   Вафель
 
18 - 15.06.18 - 11:57
(13) тоже не понял условия задачи.
те нужен полный подграф на 7 вершинах.
такого может не быть ни при скольки N
   Малыш Джон
 
19 - 15.06.18 - 11:57
+(17) додумать = взять с потолка
   Ненавижу 1С
 
20 - 15.06.18 - 11:58
(14) каждый с каждым? тогда слово "цепочка" не совсем уместна

или достаточно ребер одного цвета вот так: А1-А2-А3-А4-А5-А6-А7?
   ERWINS
 
21 - 15.06.18 - 12:00
(18) есть полный граф в котором или ребро синее (нет писем) или Красное (есть переписка)

при каком N всегда в графе будет полный подграф только с синими ребрами или только с красными
   ERWINS
 
22 - 15.06.18 - 12:00
размер подрафа 7
   Вафель
 
23 - 15.06.18 - 12:00
или просто нужен связный подграф на 7 вершинах? такого тоже может не быть никогда7
   ERWINS
 
24 - 15.06.18 - 12:01
(20) замкнутая цепочка
   toypaul
 
25 - 15.06.18 - 12:01
(16) задача тупая
   ERWINS
 
26 - 15.06.18 - 12:01
(20) есть еще вариант полный подграф

выбирай любую
   Вафель
 
27 - 15.06.18 - 12:01
(21) нет писем лучше интерпретировать как нет ребра
   ERWINS
 
28 - 15.06.18 - 12:02
(25) зато абелевский премий за нее надавали....
   toypaul
 
29 - 15.06.18 - 12:02
N может быть хоть миллион миллиардов. и все они могут писать друг дружке. ибо никаких других ограничений на гору писем нет.
   Малыш Джон
 
30 - 15.06.18 - 12:02
(25) нет, задача интересна, просто ТС четко её сформулировать пока не может
   ERWINS
 
31 - 15.06.18 - 12:03
(27) вначале пытался так объяснить.... потом перешел к красному ребру, так вроде народу понятнее
   ERWINS
 
32 - 15.06.18 - 12:03
(29) мало
   ERWINS
 
33 - 15.06.18 - 12:03
ответ повесит мисту
 
 
   toypaul
 
34 - 15.06.18 - 12:04
(32) ты не понял. N может быть бесконечным ибо про размер кучи ничего не написано. ты задачу не написал целиком.
   ERWINS
 
35 - 15.06.18 - 12:05
(34) минимальное N
   cincout
 
36 - 15.06.18 - 12:06
(0) Нет решения, так как любой человек мог написать письмо самому себе
   Малыш Джон
 
37 - 15.06.18 - 12:06
(35) если это полный граф, то при N=7 найдется семь связных ребер)
   Малыш Джон
 
38 - 15.06.18 - 12:07
+(37) если по условию нужная цепочка писем может посещать вершины по нескольку раз, то и N=2 досточно))
   ERWINS
 
39 - 15.06.18 - 12:08
(37) при любом графе N=7 найдется 7 связанных ребер?
задача не найти когда есть победа, задача найти такое условие, что всегда есть победа
   ERWINS
 
40 - 15.06.18 - 12:08
(38) разных.
   Малыш Джон
 
41 - 15.06.18 - 12:09
(39) в (21) ты описал ситуацию как полный граф. Если это так, то N=7 всегда достаточно.
   Малыш Джон
 
42 - 15.06.18 - 12:10
+(41) в полном графе любая пара вершин смежна
   Вафель
 
43 - 15.06.18 - 12:11
Если переформулировать, то получается.
При каком количестве вершин всегда найдется связный подграф порядка 7.
тк о изначальном количестве ребер ничего не известно, то ответ: ни при каком
   ERWINS
 
44 - 15.06.18 - 12:12
При каком количестве вершин всегда найдется связный подграф порядка 7 или не связный подграф порядка 7.
   ERWINS
 
45 - 15.06.18 - 12:14
пусть N=7 тогда существует граф из 3х вершин полносвязный и из 4х вершин полносвязный, но в этом графе нет полносвязного графа из 7 вершин и нет графа из 7 вершин между которыми нет связей
   Вафель
 
46 - 15.06.18 - 12:16
(43) уточнение: существует либо связный подграф либо пустой подграф.
Вот теперь уже можно решать
   Малыш Джон
 
47 - 15.06.18 - 12:17
(45) если в графе из 7 вершин нет полносвязного графа из семи вершин, тогда это не полный граф, что противоречит (21)
   Малыш Джон
 
48 - 15.06.18 - 12:18
Я же про что и говорю - ты сначала задачу сформулируй корректно, а потом уже решение спрашивай
   Вафель
 
49 - 15.06.18 - 12:18
(46) в такой постановке нужно 6+7=13 вершин
 
 Рекламное место пустует
   Вафель
 
50 - 15.06.18 - 12:19
(49) хотя нет не так
   Вафель
 
51 - 15.06.18 - 12:19
Ну и как обычно это задача на принцип Дирихле
   ERWINS
 
52 - 15.06.18 - 12:21
(51) неа
   Малыш Джон
 
53 - 15.06.18 - 12:22
(49) а если там есть не два, а несколько не связанных между собой графов?
   Вафель
 
54 - 15.06.18 - 12:23
(51) Тогда верный ответ в (1)
   NSSerg
 
55 - 15.06.18 - 12:24
(6) Вопрос звучит при каком N гарантированно.
При 36 не гарантированно. Я привел структуру - шесть групп по 6 человек. Письма пишут только внутри группы.
Если ты говоришь что и при 37 не гарантированно - то приведи структуру. Если ты говоришь что при 36 гарантированно - я тебе привел структуру с кучей писем где не гарантированно.
   Малыш Джон
 
56 - 15.06.18 - 12:24
N=42
Если есть хотя бы один полносвязный граф из 7, то это он, если все полносвязные графы из 6 вершин, тогда имеем хотя бы один граф без связей между вершинами семи шестивершных полносвязных графов.
   Малыш Джон
 
57 - 15.06.18 - 12:26
хотя да, чет сосредоточился на этих графах из 6-ти вершин
   Малыш Джон
 
58 - 15.06.18 - 12:26
тогда (3)
   _Дайвер_
 
59 - 15.06.18 - 12:31
Условия фиговые
   ERWINS
 
60 - 15.06.18 - 12:33
(55) соедини каждый из графов через свободную вершину.
   antgrom
 
61 - 15.06.18 - 12:35
(0) поскольку в условиях не написано что отправитель обязан писать кому то другому кроме получившего письма, то никакое количество не гарантирует наличие цепочки.
   Малыш Джон
 
62 - 15.06.18 - 12:35
(61) там либо цепочку надо, либо отсутствие цепочки
   Garykom
 
63 - 15.06.18 - 12:36
7 "писали друг другу" + 7 "не писали друг другу", далее совмещаем так чтобы не испортить цепочки.

На одного точно можно совместить, итого при минимальном N = 13 точно может быть выполнение двух условий.
А может и не быть...
   Вафель
 
64 - 15.06.18 - 12:37
(60) и получится граф из 7 вершин, как и требовалось
   Малыш Джон
 
65 - 15.06.18 - 12:38
(60) :)))))

Тогда N=7 тебя чем не устраивает?
   antgrom
 
66 - 15.06.18 - 12:38
(62) при таких расплывчатых условиях и наличие цепочки - нельзя гарантировать. И гарантированное отсутствие цепочки - можно гарантировать только если количество писем меньше длины этой цепочки )
   Salimbek
 
67 - 15.06.18 - 12:38
(0) А если только А написал письмо Б - от как считается? Они писали друг другу, или они НЕ писали друг другу? Или ребро зеленое? ))
   Малыш Джон
 
68 - 15.06.18 - 12:39
+(65) Если есть два граф 3 и 4 вершины, не связанных между собой, то между вершинами этих графов можно провести цепочку отсутствия связей
   ERWINS
 
69 - 15.06.18 - 12:39
(65) см (45)
   cincout
 
70 - 15.06.18 - 12:39
(0) В горе писем любого размера всегда может оказаться, что все письма написаны на одного и того же адресата, то есть никакой цепочки нет. Так что "гарантированно" - никогда
   Garykom
 
71 - 15.06.18 - 12:40
(67) Цепочки А>Б и Б>А разные
   ERWINS
 
72 - 15.06.18 - 12:40
(67) если было письмо, то зеленое, если не было переписки то грасное
   Garykom
 
73 - 15.06.18 - 12:41
Ответ 7
1>2>3>4>5>6>7 - писали
7>6>5>4>3>2>1 - не писали ))
   ERWINS
 
74 - 15.06.18 - 12:41
(70) тогда есть много людей которые никогда не писали друг другу. т.е. есливие или 7 писали друг другу или 7 не писали дру другу
тут второе сразу
   _KSA_
 
75 - 15.06.18 - 12:41
(70)
7 человек которые писали друг другу или не писали друг другу)
   ERWINS
 
76 - 15.06.18 - 12:41
(73) ве важно кто кому граф неоринтированный
   Salimbek
 
77 - 15.06.18 - 12:42
(64) Не устраивает тем, что внутри может быть, что 1-й написал 2-му и 2-й первому, так что между ними связь "Синяя", а между остальными она "Красная" и тогда нету 7 человек НЕ писавших друг-другу. И нету цепочки в 7 человек, которые писали друг-другу.
   Garykom
 
78 - 15.06.18 - 12:43
(76) "писали друг другу" подразумевает наличия писем в обе стороны или достаточно в одну?
   Garykom
 
79 - 15.06.18 - 12:46
И "цепочка" это 1-й со 2-м, 2-й с 3-м и т.д.?
   Salimbek
 
80 - 15.06.18 - 12:46
(72) I Вариант:
1. Если А написал Б и Б написал А, то ребро Синее.
2. Если или только А написал Б, или только Б написал А - ребро Зеленое.
3. Если А не писал Б, и Б не писал А, то ребро Красное?
-----
Или
II Вариант:
1. Если или А написал Б, или Б написал А - ребро Синее.
2. Если А не писал Б, и Б не писал А, то ребро Красное?
   Малыш Джон
 
81 - 15.06.18 - 12:49
Аххаа, ну вообще да, для графа с тремя вершинами не будет цепочки отсутствия связи из 7 ребер, даже если другой граф - с любым количеством вершин.

Т.е. максимальная конфигурация НЕ удовлетворяющая задаче - это 3+6 (нет отсутствия связи из 7 ребер и внутри графов нет связи из семи ребер)

Тогда N=10.
   Redkiy
 
82 - 15.06.18 - 12:50
Условия не четкие. Не указана кому пишут N человек. Адресат должен быть в этих N? Или пишут на деревню дедушке или родственникам за границу?
   Salimbek
 
83 - 15.06.18 - 12:56
(82) Если все написали на деревню дедушке, то они точно НЕ писали друг другу, и тогда берем любых 7 человек из них и получаем условие в (0).
   Redkiy
 
84 - 15.06.18 - 12:58
(83) Задача в стиле двух крокодилов...
   NSSerg
 
85 - 15.06.18 - 13:01
То есть полносвязный граф, ребра раскрашены в два цвета.
Какое максимальное количество вершин может быть в графе, чтоб не было цепочек из семи разных вершин соединенных ребрами одного цвета?
   Ненавижу 1С
 
86 - 15.06.18 - 13:02
   Вафель
 
87 - 15.06.18 - 13:02
(85) тут вопрос. что он понимает под цепочками
   NSSerg
 
88 - 15.06.18 - 13:03
(85) Тогда в одной группе 6 вершин, во второй 3 - не гарантированно.
6+4 гарантированно. Итого ответ 10.
   Вася Теркин
 
89 - 15.06.18 - 13:05
Ответ 14
   Вася Теркин
 
90 - 15.06.18 - 13:05
Один человек может написать шестерым или не написать шестерым. Тогда тринадцать плюс 1
   Вася Теркин
 
91 - 15.06.18 - 13:07
(87) Вопрос что он подразумевает под цепочками людей, никогда не писавших друг другу. Это любые 6 контактов
   Вася Теркин
 
92 - 15.06.18 - 13:08
6 неконтактов
   Вафель
 
93 - 15.06.18 - 13:08
Задача о расскраске полного графа в 2 цвета, чтобы получился полный подграф порядка 7
   Андрюха
 
94 - 15.06.18 - 13:09
Видимо это группа из 6 контактов, каждый участник которой никогда не писал 5 другим.
   Вася Теркин
 
95 - 15.06.18 - 13:10
(94) Прямо не писал, но могут иметь общий контакт?
   Вафель
 
96 - 15.06.18 - 13:10
(93) Тогда это нерешенная задача и ответ N из интервала [205, 540]
   Вася Теркин
 
97 - 15.06.18 - 13:12
Здесь не хватает условия сколько писем у каждого есть. Если всего писем написано 0, то ответ 7, если одно письмо написано, то ответ 8
   Вася Теркин
 
98 - 15.06.18 - 13:12
и. т.д.
   Ненавижу 1С
 
99 - 15.06.18 - 13:13
Пронумеруем людей от 1 до N. Пусть А написал письмо для Б тогда и только тогда, когда индекс А меньше чем у Б.

Тогда не только цепочек не будет, но даже и пар таких.
   Вася Теркин
 
100 - 15.06.18 - 13:13
Если писем написано всего 3, то надо искать только группу неписавших
  1  2   

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует