2014-06-08
На множестве S введено отношение $\rightarrow$ которое выполнено для пар элементов из множества S и обладает следующими свойствами: 1) для любых различных элементов $a, b \in S$ выполнено ровно одно из отношений $a \rightarrow b$ или $b \rightarrow a$; 2) для любых трех различных элементов $a, b, c \in S$ выполнение отношений $a \rightarrow b $ и $b \rightarrow c$ влечет за собой выполнение отношения $c \rightarrow a$. Каково наибольшее число элементов, которое может содержать множество S?
Решение:
Предположим, что в множестве $S$ найдутся три элемента $a, b, c$ такие, что $a \rightarrow b$ и $a \rightarrow c$. Если $b \rightarrow c$, то из $a \rightarrow b$ и $b \rightarrow c$ следует $c \rightarrow a$, что противоречит условию $a \rightarrow c$. Если же $c \rightarrow b$, то из $a \rightarrow c$ и $c \rightarrow b$ следует $b \rightarrow a$, что противоречит условию $a \rightarrow b$. Аналогично доказывается, что в $S$ нет элементов $a, d, e$ таких, что $d \rightarrow a$ и $e \rightarrow a$. Если в множестве $S$ имеется 4 или более элементов (один из которых обозначим через $a$), то из первого условия задачи следует, что в $S$ найдутся или такие элементы $b$ и $c$, что $a \rightarrow b$ и $a \rightarrow c$, или же такие элементы $d$ и $e$, что $d \rightarrow a$ и $e \rightarrow a$. В обоих случаях получаем противоречие. Поэтому в множестве $S$ не более трех элементов. Пример множества S с тремя элементами $a, b, c$, удовлетворяющего обоим условиям задачи, может быть таким: $a \rightarrow b, b \rightarrow c, c \rightarrow a$.