По трем или всем?

Всего три. Так что более половины = два или три.

A, пардон, мне показалось, что всего 4.

мды, неочевдино.
это делается "школьной" математикой или нужно что-то нетривиальное знать по комбинаторике/алгебре?

да уж, спасибо, до вашей задачки никогда не осознавал, что женщин конечное число :(

Это да. А можно поинтересоваться ходом мысли? В смысле - прихода к данному осознаванию?

сижу, как-то вечером, думаю о женщинах.. :)

если бесконечное – очевидны примеры, когда задачка неверна. типа: если признаки совпадают, всегда найдётся женщина получше..

верно, но практически бесполезно, как и любые неконструктивные теоремы существования (eg Минковский-Хлавка)

Доказательство полностью элементарно и конструктивно.
А бесполезна эта теорема потому, что фиг упорядочишь :)

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

Как интересно! Ну-ка, ну-ка...

Маша: 1 2 3
Лена: 2 3 1
Таня: 3 1 2

Лена лучше Маши, Таня лучше Лены, но Маша лучше Тани! Нетранзитивность, ешкин пень!

Я хотел тоже отделаться латинским квадратом, но подумал, что неправильно понял задание.

Неправильно? А как же?

Из оставшихся женщин на планете, а не в тройке.

If you came up with this (and just a few more steps) about 50 years ago, you would've won the Nobel prize in Economics.

en.wikipedia.org/wiki/Arrow's_impossibility_theorem

A theorem from "Perfect mind" movie, right?

I doubt it - Beautiful Mind (if that's the movie you have in mind) was about John Nash, whose papers on bargaining and equilibrium are not related to Arrow's impossibility theorem.

I ment Beatuful Mind, of course.

Very simple.

1. Elect the prettiest of all - P.
2. Define a set of the smarter ones than P - sp;
if sp is empty, then done: (any two and P) rule.
3. otherwise elect the smartest out of sp - S;
4. define a set of the sexier ones than S - ss.
if ss is empty, than (any one, P, S) rule, because any girl is uglier than P, and either dumber than P - ie worse, or smarter than P and (ss is empty) less sexy than S - ie worse again.
5. Elect the sexiest of ss - X.
6.(P,S,X) are the best.

Увы, не работает...
Это сводится к тому, чтбы выбрать самую лучшую в каждом порядке. Вот пример, когда три самых лучших (1,2,3) не покрывают четвертую:
1423
2413
3412

и то.
плохой из меня математик, пойду в физики.

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

В вашем примере координаты точек такие:

1)022
2)203
3)330
4)111

Ясно, что любая комбинация, куда входит 4 годится.

Во-первых, видимо имелась ввиду плоскость, которая лежит на 3-х точках, такая, что все остальные точки лежат "ниже" ее? А следуя вашему алгоритму выберутся точки с минимальными параметрами...

Пусть женщин всего 4. Одна очень умная, вторая красивая, третья сексуальная. Оценки такие:
первая: 10 0 0
вторая: 0 10 0
третья: 0 0 10

А у четвертой все параметры близки к 5.
(чуть больше, или чуть меньше, так чтобы построеная вами плоскость проходила через первых трех кандидаток). Но эта самая четвертая все равно лучще всех, правда?

Вы молодой человек неправильно бутерброд едите.

Я строю пространство не по оценкам - они ведь могут быть и такие (1000000000, 999999, 2) - а по номеру места, начиная с нуля.

У меня подозрение (это к хозяину), что я нашел какое-то более сильное утверждение, чем требывалось.. требавылось.. трыбеволось.. вобщем, чем нужно.

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