Есть гора писем от N человек

Сколько должно быть N, что бы гарантировано нашлась цепочка из 7 человек которые писали друг другу или не писали друг другу?

13

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

(10) нет

(11) это понятно, а остальное? я про "цепочка из 7 человек которые писали друг другу"

(13) допустим если писали то все ребра синии, если не писали, то все ребра красные

задача странно сформулирована

Есть гора писем(т.е. хз сколько). какое количество чеовек должно было участвовать в написании этой горы(хз, кто -  сколько, может все кроме одного написали по одному письму, а остальные письма накатал последний), чтобы нашлась цепочка из 7 писем.

(15) задачи часто странно сформулированы

(16) странно = неполно или нечетко = решение возможно, только если самостоятельно додумать начальные условия

(13) тоже не понял условия задачи.
те нужен полный подграф на 7 вершинах.
такого может не быть ни при скольки N

+(17) додумать = взять с потолка

(14) каждый с каждым? тогда слово "цепочка" не совсем уместна

или достаточно ребер одного цвета вот так: А1-А2-А3-А4-А5-А6-А7?

(18) есть полный граф в котором или ребро синее (нет писем) или Красное (есть переписка)

при каком N всегда в графе будет полный подграф только с синими ребрами или только с красными

размер подрафа 7

или просто нужен связный подграф на 7 вершинах? такого тоже может не быть никогда7

(20) замкнутая цепочка

(16) задача тупая

(20) есть еще вариант полный подграф

выбирай любую

(21) нет писем лучше интерпретировать как нет ребра

(25) зато абелевский премий за нее надавали....

N может быть хоть миллион миллиардов. и все они могут писать друг дружке. ибо никаких других ограничений на гору писем нет.

(25) нет, задача интересна, просто ТС четко её сформулировать пока не может

(27) вначале пытался так объяснить.... потом перешел к красному ребру, так вроде народу понятнее

(29) мало

ответ повесит мисту

(32) ты не понял. N может быть бесконечным ибо про размер кучи ничего не написано. ты задачу не написал целиком.

(34) минимальное N

(0) Нет решения, так как любой человек мог написать письмо самому себе

(35) если это полный граф, то при N=7 найдется семь связных ребер)

+(37) если по условию нужная цепочка писем может посещать вершины по нескольку раз, то и N=2 досточно))

(37) при любом графе N=7 найдется 7 связанных ребер?
задача не найти когда есть победа, задача найти такое условие, что всегда есть победа

(38) разных.

(39) в (21) ты описал ситуацию как полный граф. Если это так, то N=7 всегда достаточно.

+(41) в полном графе любая пара вершин смежна

Если переформулировать, то получается.
При каком количестве вершин всегда найдется связный подграф порядка 7.
тк о изначальном количестве ребер ничего не известно, то ответ: ни при каком

При каком количестве вершин всегда найдется связный подграф порядка 7 или не связный подграф порядка 7.

пусть N=7 тогда существует граф из 3х вершин полносвязный и из 4х вершин полносвязный, но в этом графе нет полносвязного графа из 7 вершин и нет графа из 7 вершин между которыми нет связей

(43) уточнение: существует либо связный подграф либо пустой подграф.
Вот теперь уже можно решать

(45) если в графе из 7 вершин нет полносвязного графа из семи вершин, тогда это не полный граф, что противоречит (21)

Я же про что и говорю - ты сначала задачу сформулируй корректно, а потом уже решение спрашивай

(46) в такой постановке нужно 6+7=13 вершин

(49) хотя нет не так

Ну и как обычно это задача на принцип Дирихле

(51) неа

(49) а если там есть не два, а несколько не связанных между собой графов?

(51) Тогда верный ответ в (1)

(6) Вопрос звучит при каком N гарантированно.
При 36 не гарантированно. Я привел структуру - шесть групп по 6 человек. Письма пишут только внутри группы.
Если ты говоришь что и при 37 не гарантированно - то приведи структуру. Если ты говоришь что при 36 гарантированно - я тебе привел структуру с кучей писем где не гарантированно.

N=42
Если есть хотя бы один полносвязный граф из 7, то это он, если все полносвязные графы из 6 вершин, тогда имеем хотя бы один граф без связей между вершинами семи шестивершных полносвязных графов.

хотя да, чет сосредоточился на этих графах из 6-ти вершин

тогда (3)

Условия фиговые

(55) соедини каждый из графов через свободную вершину.

(0) поскольку в условиях не написано что отправитель обязан писать кому то другому кроме получившего письма, то никакое количество не гарантирует наличие цепочки.

(61) там либо цепочку надо, либо отсутствие цепочки

7 "писали друг другу" + 7 "не писали друг другу", далее совмещаем так чтобы не испортить цепочки.

На одного точно можно совместить, итого при минимальном N = 13 точно может быть выполнение двух условий.
А может и не быть...

(60) и получится граф из 7 вершин, как и требовалось

(60) :)))))

Тогда N=7 тебя чем не устраивает?

(62) при таких расплывчатых условиях и наличие цепочки - нельзя гарантировать. И гарантированное отсутствие цепочки - можно гарантировать только если количество писем меньше длины этой цепочки )

(0) А если только А написал письмо Б - от как считается? Они писали друг другу, или они НЕ писали друг другу? Или ребро зеленое? ))

+(65) Если есть два граф 3 и 4 вершины, не связанных между собой, то между вершинами этих графов можно провести цепочку отсутствия связей

(65) см (45)

(0) В горе писем любого размера всегда может оказаться, что все письма написаны на одного и того же адресата, то есть никакой цепочки нет. Так что "гарантированно" - никогда

(67) Цепочки А>Б и Б>А разные

(67) если было письмо, то зеленое, если не было переписки то грасное

Ответ 7
1>2>3>4>5>6>7 - писали
7>6>5>4>3>2>1 - не писали ))

(70) тогда есть много людей которые никогда не писали друг другу. т.е. есливие или 7 писали друг другу или 7 не писали дру другу
тут второе сразу

(70)
7 человек которые писали друг другу или не писали друг другу)

(73) ве важно кто кому граф неоринтированный

(64) Не устраивает тем, что внутри может быть, что 1-й написал 2-му и 2-й первому, так что между ними связь "Синяя", а между остальными она "Красная" и тогда нету 7 человек НЕ писавших друг-другу. И нету цепочки в 7 человек, которые писали друг-другу.

(76) "писали друг другу" подразумевает наличия писем в обе стороны или достаточно в одну?

И "цепочка" это 1-й со 2-м, 2-й с 3-м и т.д.?

(72) I Вариант:
1. Если А написал Б и Б написал А, то ребро Синее.
2. Если или только А написал Б, или только Б написал А - ребро Зеленое.
3. Если А не писал Б, и Б не писал А, то ребро Красное?
-----
Или
II Вариант:
1. Если или А написал Б, или Б написал А - ребро Синее.
2. Если А не писал Б, и Б не писал А, то ребро Красное?

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

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

Тогда N=10.

Условия не четкие. Не указана кому пишут N человек. Адресат должен быть в этих N? Или пишут на деревню дедушке или родственникам за границу?

(82) Если все написали на деревню дедушке, то они точно НЕ писали друг другу, и тогда берем любых 7 человек из них и получаем условие в (0).

(83) Задача в стиле двух крокодилов...

То есть полносвязный граф, ребра раскрашены в два цвета.
Какое максимальное количество вершин может быть в графе, чтоб не было цепочек из семи разных вершин соединенных ребрами одного цвета?

https://ru.wikipedia.org/wiki/Теорема_Рамсея

(85) тут вопрос. что он понимает под цепочками

(85) Тогда в одной группе 6 вершин, во второй 3 - не гарантированно.
6+4 гарантированно. Итого ответ 10.

Ответ 14

Один человек может написать шестерым или не написать шестерым. Тогда тринадцать плюс 1

(87) Вопрос что он подразумевает под цепочками людей, никогда не писавших друг другу. Это любые 6 контактов

6 неконтактов

Задача о расскраске полного графа в 2 цвета, чтобы получился полный подграф порядка 7

Видимо это группа из 6 контактов, каждый участник которой никогда не писал 5 другим.

(94) Прямо не писал, но могут иметь общий контакт?

(93) Тогда это нерешенная задача и ответ N из интервала [205, 540]

Здесь не хватает условия сколько писем у каждого есть. Если всего писем написано 0, то ответ 7, если одно письмо написано, то ответ 8

и. т.д.

Пронумеруем людей от 1 до N. Пусть А написал письмо для Б тогда и только тогда, когда индекс А меньше чем у Б.

Тогда не только цепочек не будет, но даже и пар таких.

Если писем написано всего 3, то надо искать только группу неписавших

При стремлении числа писем к бесконечности вероятность ненаписания писем стремится к нулю

+(99) даже если рассматривать "односторонние" (направленные ребра) цепочки, то в таком варианте замкнутой цепочки нет

Числа писем не хватает, хотя бы общего

(103) Это совершенно неважно. Т.к. А либо писал Б, либо не писал Б, но связь между ними всегда есть.

(104) автор пишет "друг к другу", поэтому связи может не быть вообще А написал к Б, а Б не написал к А

Да, направленность цепочки это тоже вопрос. Я про это писал выше

Или "друг другу" надо понимать что писем было как мининум два?

"которые писали друг другу или не писали друг другу" - как понимать условие?

по идее выходит что в обе стороны, одно письмо не в счет