Рататуй

[wpoms.]

Гурман Жан сравнивал $n$ ресторанов, где $n$ --- положительное целое число. Каждая пара ресторанов сравнивалась по двум показателям: качеству еды и уровню обслуживания. В некоторых случаях Жан не мог определиться, какой из двух ресторанов лучше по какому-то одному показателю, но тогда он всегда выбирал лучший по другому показателю. Понятно, что если Жан узнал, что ресторан $A$ лучше ресторана $B$ по какому-то показателю, и ресторан $B$ лучше ресторана $C$ по этому же показателю, то он считает, что $A$ лучше $C$ по этому показателю. Докажите, что есть ресторан $R$ такой, что любой другой ресторан хуже чем $R$ хотя бы по одному показателю.

@темы: Дискретная математика

Comments

[Дилетант]

А могут быть два ресторана, по-разному упорядоченные? По одному признаку лучше один, а по другому другой?

[wpoms.]

Да

[Дилетант]

Лемма Цорна

[Дилетант]

Я, наверное, не понимаю условия.
Может быть вот такая ситуация?

Стрелочка означает "лучше", но это не так важно.
Получается, что есть несравнимые рестораны.

[wpoms.]

Получается, что есть несравнимые рестораны.

Никто не мешает сравннить нижние между собой.

[wpoms.]

Без посредника.

[Дилетант]

Или главное, чтобы были пути ко всем вершинам из какой-то одной, а цвет неважен?

[Дилетант]

аааа

[Дилетант]

Тогда по индукции, по идее.

[wpoms.]

Тогда по индукции, по идее.

Так!

[Дилетант]