Author |
Topic: Best non-transitive set item (Read 8023 times) |
|
shmuha
Guest
|
 |
Re: Best non-transitive set item
« Reply #25 on: Dec 12th, 2003, 7:39am » |
 Quote  Modify
 Remove
|
Can you find best item among the set of: rock,paper,scissors ?
No.
Why?
Because they are in non-transitive relation.
The same is true for the riddle.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Best non-transitive set item
« Reply #26 on: Dec 12th, 2003, 2:25pm » |
Quote Modify
|
on Dec 12th, 2003, 7:39am, shmuha wrote:Can you find best item among the set of: rock,paper,scissors ?
No.
Why?
Because they are in non-transitive relation.
The same is true for the riddle. |
|
Wow, one case were it doesn't work, and you immediately generalize to every case..
My one year old niece can't solve 1+1, so nobody can.. yep, seems to make sense 
Non-transitivity does not exclude 'best-ness' of any item. Whereas transitivity on the other hand does guarantee it. But it's an implication, not an equality, so you can't just turn it around.
I allready gave a non-transitive example that does have a best 'item', so that proves there can be.
Note also that, although you're given one kind of 'better than'- relation, which happens not to be transitive, you can still (try and) use it to build another one that is.
|
| « Last Edit: Dec 12th, 2003, 2:33pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Best non-transitive set item
« Reply #27 on: Dec 12th, 2003, 10:20pm » |
Quote Modify
|
on Dec 12th, 2003, 2:25pm, towr wrote:| Wow, one case were it doesn't work, and you immediately generalize to every case.. |
|
Everybody does that, towr. I know I do.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Best non-transitive set item
« Reply #28 on: Apr 30th, 2004, 2:13pm » |
Quote Modify
|
First you need to define "the best".
a. x is best if x is better than y for each y.
b. x is best if x is better or equivalent to y for each y.
c. x is best by some evaluation of the number of items it is better than.
a. it is easy, take them each in turn, compare them 2 by 2 and keep the one (or none) that is better than the other.
b. it is also easy, except that you have to keep the set of items that are equivalent. A possible optimisation would be a binary elimination where both players can be promoted and only items worse than some other are eliminated.
c. Is badly defined and needs more clarification. For instance, if A is better than B and C is better than D, then should A be considered better than C if B is better than more items than D is, something like in the ranking for chess players? And you have to decide how "impossible" the decision is.
|
|
IP Logged |
|
|
|
unknown
Guest
|
|
Re: Best non-transitive set item
« Reply #29 on: Jul 7th, 2005, 8:11pm » |
Quote Modify
Remove
|
on Dec 12th, 2003, 2:25pm, towr wrote:
Whereas transitivity on the other hand does guarantee it. |
|
Sorry to nitpick, but transitivity does not guarantee a best item, especially if the best should be better than all items. Here's a case.
a = b
a > c and d
b > b and d
c > d
On the other hand, you could consider a and b to be the best because both of them are >= then all items.
To solve this problem, I would use the celebrity algorithm. Hey, this is the first time I see an application for this one.
First, let's go trying to find the easy case : looking for 1 item > than all other items. This runs in O(n).
1) Set best = item 1.
2) for all items i from 2 to n do
3) compare item i to best item.
4) If Item i > currently best item, best = item i.
5) Go back to 2 until finished.
We should now verify if our best item is really the best. To do this, we compare it to every other items. If it is >, we have a best item, else it doesn't exist.
If we allow for >= instead of >, it gets a bit more complicated. We need to keep a list of the best items. Then when we compare a new item to the list, we might need to remove some of the items are < than the current one.
The worst case would probably O(n^2) if all items are equal.
I hope this makes a bit of sense.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print