Любые два жителя города либо дружат, либо враждуют между собой. При этом известно, что если A - друг B, а B- друг C, то A - также друг C, а также среди любых троих жителей хотя бы двое дружат между собой. Каждый день не более чем один житель может начать новую жизнь: перессориться со всеми своими друзьями и подружиться со всеми своими врагами. Доказать, что все жители города могут подружиться.
АЛЬТЕРНАТИВНАЯ ФОРМУЛИРОВКА: В городе "Многообразие" живут n жителей, любые два из которых либо дружат, либо враждуют между собой. Каждый день не более чем один житель может начать новую жизнь: перессориться со всеми своими друзьями и подружиться со всеми своими врагами. Доказать, что все жители могут подружиться.
Примечание. Если A — друг B, а B — друг C, то A — также друг C. Предполагается также, что среди любых троих жителей хотя бы двое дружат между собой.
|
|
|