Non directly known people

[ins-]

In a group of people two persons $X$, $Y$ are named non-directly known if they know each other personally or if exists a chain of people $Z_1$, $Z_2$, ..., $Z_p$ such that $X$ and $Z_1$ are known, $Z_1$ and $Z_2$ are known, ..., $Z_p$ and $Y$ are known. Let the group consists of $134$ persons and for each $8$ of them at least two are non-directly known. Prove that there exists a group of $20$ people every two of which are non-directly known.

[Aritaborian]

ins-, вы считаете, что если не владеете русским языком, то имеете право пользоваться здесь английским. В этом вы полностью правы. Но беда в том, что и с английским у вас не очень хорошо, увы. Вот первый же пример (я могу привести другие).

ins- в сообщении #1095508 писал(а):

two mans

Ну куда это годится?

[Lia]

(Оффтоп)

Aritaborian в сообщении #1095512 писал(а):

Но беда в том, что и с английским у вас не очень хорошо, увы.

Aritaborian, помнится мне, ins- чуть ранее совершенно честно в этом сознавался, сообщив, что с русским у него еще хуже. Давайте не будем оффтопить, а? :)

[ins-]

(Оффтоп)

You are correct - languages aren't my strongest side.

[DeBill]

ins-

Я полагаю, у Вас опечатка:

ins- в сообщении #1095508 писал(а):

they not know each o

not здесь лишнее.

На человеческом языке условие означает: в графе 134 вершины. Из любых 8 вершин, есть пара связанных друг с другом. Доказать: есть компонента связности, состоящая из не менее 20 вершин.
Но это просто: пусть все не так: в каждой компоненте не более 19 вершин. Значит, компонент связности не менее $\frac{134}{19} >7$. Выберем в каждой из них по мэну - и получим 8 чел, попарно не nondirect known.

[ins-]

DeBill в сообщении #1095519 писал(а):

ins-

Я полагаю, у Вас опечатка:

ins- в сообщении #1095508 писал(а):

they not know each o

It explains many things ... I started solving the problem as it was with the mistake. Thus I was in a situation solving a different problem than the correct one. Thank you very much!

(Оффтоп)

"non directly known" in Bulgarian "косвено познати" probably should be something like "indirectly known" or "косвенно известной" the mistake you meant appears also here http://imomath.com/othercomp/Bul/BulMO377.pdf. I'm guilty! Shame on me!

[Otta]

ins- в сообщении #1095521 писал(а):

"non directly known" in Bulgarian "косвено познати" probably should be something like "indirectly known" or "косвенно известной"

Я не поняла, почему ошибка. Косвенно знакомы. Или опосредованно знакомы. То есть не знакомы лично, но имеют общих знакомых. Так и написано в условии, как мне кажется.

DeBill

DeBill в сообщении #1095519 писал(а):

not здесь лишнее.

Почему лишнее? Мне кажется, или все Ваши рассуждения успешно проходят, если в графе строить ребро только между "опосредованно знакомыми" вершинами?

[ins-]

Otta

Initially I copied and pasted Problem 6 from here http://imomath.com/othercomp/Bul/BulMO377.pdf on dxdy. I translated the problems from Bulgarian and sent them to imomath.com. But as DeBill mentioned there was an additional "non" that I added by mistake . Then I fixed the problem's statement.

[DeBill]

Otta

Ну да, можно и такую задачу рассмотреть. Я пытался соорудить контрпример (чтобы увериться в том, что действительно имела место быть опечатка) - но неуспешно...