Author |
Topic: Best non-transitive set item (Read 8025 times) |
|
tes
Guest
|
You have a group of items, each of which can be used as a
parameter to the function better (item1, item2), which will tell you which of the two items is "better" or that none of them are clearly "better". Find the best item in the group if possible given that the better function is non-transitive (i.e. if item1 is "better" than "item2" and "item2" is better than "item3", it does not imply that "item1" is better than "item3")
|
|
 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 #1 on: Dec 4th, 2003, 2:06am » |
 Quote  Modify
|
if it's not transitive, define what 'best' means..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #2 on: Dec 4th, 2003, 2:11am » |
Quote Modify
|
Is there a time complexity that your looking for  (i.e. finding the element in O(n2) is trivial and even finding the element with O(n log(n)) expected time is quite easy, so are you looking for something better) ?
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best non-transitive set item
« Reply #3 on: Dec 4th, 2003, 2:16am » |
Quote Modify
|
if there is an item i which is the best of the lot,
that means when i put (item j and item i) in the function it would return me item i. and also for some (item k and item i) the function would return me item i. when i input (item j and item k) into the function it would return me either item j or item k. This would mean the function is transitive and the premise is false
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #4 on: Dec 4th, 2003, 2:17am » |
Quote Modify
|
on Dec 4th, 2003, 2:06am, towr wrote:| if it's not transitive, define what 'best' means.. |
|
towr hi,
I think that 'best' means the element that is "better"/equal (tes: "...none of them are clearly "better"...") in respect to all the other elements (assuming that such an element exists (tes: "...if possible..."))  .
I hope I got it right !?
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #5 on: Dec 4th, 2003, 2:32am » |
Quote Modify
|
on Dec 4th, 2003, 2:16am, TenaliRaman wrote:| This would mean the function is transitive and the premise is false |
|
TenaliRaman hi,
I think there is no problem. I believe that tas meant that the function is non-transitive in the sense that it isn't obligatory that (if x<y and y<z [to] x<y). e.g. for every k (> 2) elements there might be a circle of "better" relations (and, of course, there might not be)...
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best non-transitive set item
« Reply #6 on: Dec 4th, 2003, 2:51am » |
Quote Modify
|
Dudidu,
quoting tes here,
Quote:| ..given that the better function is non-transitive.. |
|
If it had been as you said, then prolly it should have been "the better function is not necessarily transitive".
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #7 on: Dec 4th, 2003, 3:09am » |
Quote Modify
|
on Dec 4th, 2003, 2:51am, TenaliRaman wrote:| If it had been as you said, then prolly it should have been "the better function is not necessarily transitive". |
|
TenaliRaman you are right (tas should have written that "the better function is not necessarily transitive") but as I said, I believe that tas meant it (and his explanation...
Quote:| i.e. if item1 is "better" than "item2" and "item2" is better than "item3", it does not imply that "item1" is better than "item3"... |
|
supports it).
|
|
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 #8 on: Dec 4th, 2003, 3:14am » |
Quote Modify
|
suppose we have three items,a,b,c
a > b, b > c, c > a
tell me, which is better?
rock,paper,scissors
|
| « Last Edit: Dec 4th, 2003, 3:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #9 on: Dec 4th, 2003, 3:23am » |
Quote Modify
|
on Dec 4th, 2003, 3:14am, towr wrote:suppose we have three items,a,b,c
a > b, b > c, c > a
tell me, which is better? |
|
In such a case you should return (in my opinion) that there is no element that has the desired property (i.e. the 'best'). (I think that) the following quote of tas supports it:
Quote:| Find the best item in the group if possible... |
|
Now its your turn... 
|
|
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 #10 on: Dec 4th, 2003, 3:29am » |
Quote Modify
|
or how about a,b,c,d,e
a > b,c,d
e > a
b=c=d=e
If you give each item 1 point for being better than another then clearly a wins with 3 points
If you give each item half a point for being better than item X + half a point for each item X is better than. Then
a get's 1.5 point, and e get's 2.. So e is now better
So how do we uniquely determine which of a set is better? When there transitivy you simply have a very best, when there's cycles you need to define what 'best' means.. Majority? Weighing?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Best non-transitive set item
« Reply #11 on: Dec 4th, 2003, 3:36am » |
Quote Modify
|
on Dec 4th, 2003, 3:23am, Dudidu wrote:
Now its your turn...
|
|
It's allways possible.. It just depends on your criteria.
supose a>b>c>a
a scores 2 points over b
b scores 1 over c
c scores 1 over a
value of a = 2-1=1
value of c = 1-1=0
value of b = 1-2=-1
Something may be a bit better, or a lot better, or a hell of a lot better..
It really depends on how you define better/best
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #12 on: Dec 4th, 2003, 3:43am » |
Quote Modify
|
Help !
I didn't imagine that there will be so many questions and I'll be the only one that tries to defend this problem...
However, I'm not going to break (yet )
Quote:For my opinion and as I posted earlier (quoting myself  ):
Quote:| I think that 'best' means the element that is "better"/equal in respect to all the other elements... |
|
Thus, in your problem I would say e since e [ge] a,b,c,d and a > b,c,d and a < e...
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #13 on: Dec 4th, 2003, 3:52am » |
Quote Modify
|
on Dec 4th, 2003, 3:36am, towr wrote:| ...a scores 2 points over...b scores 1 over...c scores 1 over... |
|
towr, I don't think this question deals with scores (or how big/small an element in relation to other element). It just deals with relations (i.e. you are given a set of relations and you need to find the 'best')...
|
|
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 #14 on: Dec 4th, 2003, 3:54am » |
Quote Modify
|
hmm.. yes.. I forgot about that..
But really, I'm sure you can imagine a case where that won't work..
Just try the whole set of webpages, and as 'better' relation use
webpage a better than b if b links to a
Now find the best webpage.. I very much doubt you'll find any page that every other page links to. But page ranking f.i. would be a way of finding the best page..
|
| « Last Edit: Dec 4th, 2003, 3:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best non-transitive set item
« Reply #15 on: Dec 4th, 2003, 4:02am » |
Quote Modify
|
on Dec 4th, 2003, 3:54am, towr wrote:| I very much doubt you'll find any page that every other page links to... |
|
towr, I agree with you but lets leave aside the practical things and deal with this hypothetical problem ...
|
|
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 #16 on: Dec 4th, 2003, 4:25am » |
Quote Modify
|
I don't really think you hypothetically need to have one hypothetical item being hypothetically better or equal to all the others hypothetically to be considered hypothetically best..
That just really really limiting, and uninteresting..
Sure if one item is better than all the others it's best..
But if an item is better than the majority of items, wouldn't that also be a sufficient condition?
Or if it's better than more items than any other? (top rank with 1 point for each item it is better as)
etc
So many possible ranking schemes..
|
| « Last Edit: Dec 4th, 2003, 4:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
flan
Guest
|
|
Re: Best non-transitive set item
« Reply #17 on: Dec 4th, 2003, 8:18am » |
Quote Modify
 Remove
|
Don't forget what category this is. An interview q might not have a right or wrong answer, just rate how creatively and analytically you answer it.
So let's say that Better(a,b) is used to judge job applicants. First it categorizes them according to the job they're seeking and sorts them by the criteria of that job. When comparing applicants in different job categories, the primary criteria may be inapplicable, so it falls back on a tie-breaker criterion such as years of experience or IQ.
SO a and b are programmers. a knows C++ better than b.
But c is a salesman; his programming skill is irrelevant, so he's compared to the others by IQ. That's how you can end up with a>b>c>a. In that specific case there's no way to tell from the output who's the best.
But if you had 1,000 applicants it might be possible; first I'd try comparing each to every other one. If that failed because a lot of them are tied for first, Perhaps you could sort the output. I'm not sure any method would work in all situations, but I'd look for the largest subset which is completely transitive, and repeat using the remaining applicants to divide the thousand into categories as much as possible (of completely transitive subsets). Assume that the tie-breaker cross-category comparisons are less significant, and rescore. That might break the tie.
That method would presumably fail if there are many categories with few members in each being judged on the top priority criteria. In that case I think this method would end up sorting them first by that secondary criterion (IQ), and in this case I think that's the only criterion that could actually identify a "best."
|
|
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 #18 on: Dec 4th, 2003, 9:07am » |
Quote Modify
|
I'd think that if there were many different jobs that needed to be filled you'd select one applicant for each job (unless one can do multiple jobs cheaper/better)..
If you were limited to selecting one applicant the best would probably be the one that earns your company the most money. (So every other trait/skill is translated into a common currency, so that it's comparable)
And if all else fails, just pick whoever you like best.. Natural selection at work
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best non-transitive set item
« Reply #19 on: Dec 4th, 2003, 9:22am » |
Quote Modify
|
for the job thing,
i could solve it as a knapsack problem or an LPP even(and ppl ask me how higher mathematics applies to real life).
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
flan
Guest
|
|
Re: Best non-transitive set item
« Reply #20 on: Dec 4th, 2003, 2:31pm » |
Quote Modify
Remove
|
My point was not that I'd hire employees that way. That's just an example of one way a>b>c>a where the comparisons are not arbitrary or subjective and where further analysis could determine which comparisons used a first level, important comparison and which ones used a second level tie-breaker (for all we know, the tie-breaker could be shoe size, and we may not be told anything at all about what's being compared or how except that item1>item2). If the question can be answered then there must be some way to further analyze the output than simply a>b>c>a.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Best non-transitive set item
« Reply #21 on: Dec 10th, 2003, 5:57am » |
Quote Modify
|
This is closely tied into the idea of the run-off election method. One way to do this is to first perform all comparisons, taking O(n^2), then throw away all "bad" candidates. Rerun the test, winnowing out some more "bad" candidates. Keep doing this until there are only two left, and pick the better of the two.
There are a number of ways you could determine which are "bad", but one way would be to throw away all below-average candidates. Another would be to throw away all candidates that did not get the highest score received.
Not efficient, but I think it addresses the problem.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
shmuha
Guest
|
|
Re: Best non-transitive set item
« Reply #22 on: Dec 10th, 2003, 8:38am » |
Quote Modify
Remove
|
I am afraid that the answer to this riddle is "it is not possible to find the best item"
In order for a set to have best item it must posses the property "total(linear) ordering".
http://mathworld.wolfram.com/TotallyOrderedSet.html
One of the requierements for "total order" is the transitivity set property. Since the given set is non-transitive it is not possible for the set to be lineary orderer -> no best item can be found.
|
|
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 #23 on: Dec 10th, 2003, 9:57am » |
Quote Modify
|
on Dec 10th, 2003, 8:38am, shmuha wrote:| I am afraid that the answer to this riddle is "it is not possible to find the best item" |
|
That's not true..
supopose a game between players a,b,c and d, scoring like in chess
round 1: a beats b, c and d tie
round 2: a beats c, b beats d
round 3: a loses to d, c beats b
a has 2 points, b 1 point, c and d 1 1/2 points
a is better than b and c, but not better than d, yet still the overall best.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best non-transitive set item
« Reply #24 on: Dec 10th, 2003, 12:38pm » |
Quote Modify
|
Shmuha,
i said the same thing some post earlier (though in different words). As much as you are right (because i was  )but consider this as the employee selection problem which flan suggests wherein the transitivity is "not necessary".
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print