wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Fair Shares
        
(Message started by: MathsForFun on Jul 28th, 2010, 2:21am)
Title: Fair Shares
Post by MathsForFun on Jul 28th, 2010, 2:21am
Here's a sharing puzzle that actually occurred in my previous job. There were hundreds of customers who had to be shared fairly (by both number and value of their turnover in the previous 12 months) between telephone reps. It was the most interesting work I have ever been paid to do!

Anyway - here's my simplified version of it: a legacy has to be shared between 4 people. Each should get the same number of items, and the value of each share should be as close as possible (measured by the difference in value between the best and the worst shares). Here are the values of the items:

£150, £200, £212, £215, £251, £277, £315, £370, £400, £414, £450, £477, £581, £697, £841, £888, £999, £1000, £1059, £1137, £1214, £1315, £1423, £1433

What would you give each person?
Title: Re: Fair Shares
Post by towr on Jul 28th, 2010, 2:38am
One solution I did by hand gives each of them: [hide]4069, 4073, 4099, 4077[/hide]
But there's a good chance it can be improved on. Maybe I'll write a program to solve it; I don't see a way to reason to an optimal solution.
Title: Re: Fair Shares
Post by pex on Jul 28th, 2010, 3:38am
Also by hand, I got to

[hideb]150+251+370+888+1000+1423=4082
200+450+477+581+1059+1315=4082
212+277+315+841+ 999+1433=4077
215+400+414+697+1137+1214=4077[/hideb]
Title: Re: Fair Shares
Post by MathsForFun on Jul 28th, 2010, 4:00am

on 07/28/10 at 02:38:52, towr wrote:
One solution I did by hand gives each of them: [hide]4069, 4073, 4099, 4077[/hide]
But there's a good chance it can be improved on. Maybe I'll write a program to solve it; I don't see a way to reason to an optimal solution.

Yours and Pex's solutions are both good - but neither are optimal I'm afraid. An interesting characteristic I discovered about this puzzle is that it has a "sweet spot": too small (too few items) and it can easily be done by brute force. Too large, and it also becomes very easy - because the number of optimal solutions rises very much more quickly than the search space as the size of the puzzle increases.

Although I haven't done it myself (I obviously learned how to program this puzzle to solve the much larger real life puzzle), and I will allow programming, I am sure that this puzzle could be solved without programming. Think about it...
Title: Re: Fair Shares
Post by towr on Jul 28th, 2010, 5:14am

on 07/28/10 at 04:00:24, MathsForFun wrote:
Too large, and it also becomes very easy - because the number of optimal solutions rises very much more quickly than the search space as the size of the puzzle increases.
I very much doubt this is true for worst case scenarios. I'm fairly sure there are arbitrarily large problems with just one optimal solution. And then it becomes a serious problem to find it.

[edit]
Specifically, the partition problem http://en.wikipedia.org/wiki/Partition_problem is a subset of this problem, and it is NP hard. So there is no hope :P
[/edit]
Title: Re: Fair Shares
Post by MathsForFun on Jul 28th, 2010, 5:41am

on 07/28/10 at 05:14:32, towr wrote:
I very much doubt this is true for worst case scenarios. I'm fairly sure there are arbitrarily large problems with just one optimal solution. And then it becomes a serious problem to find it. Specifically, the partition problem http://en.wikipedia.org/wiki/Partition_problem is a subset of this problem, and it is NP hard. So there is no hope :P

Maybe it is possible to design a large set which would be very difficult to resolve - but my experience is that as the puzzle in this thread is enlarged by adding more items to be shared, the number of optimal solutions grows very quickly, and they become very easy to find. I am therefore saying that while the Wikipedia article might be correct in theory, in practice the impression it gives of this type of puzzle becoming more difficult with size is very wrong indeed.

If anyone is looking for a mathematical thesis that breaks prevailing doctrine, this could be an opportunity!
Title: Re: Fair Shares
Post by towr on Jul 28th, 2010, 6:19am
The only way to even tell that your solution is optimal is if the difference is 0 or 1, or exclude all other solutions. True enough, if the number of numbers greatly outweighs the number of partitions, and the numbers are not chosen to frustrate partitioning, then chances are indeed greatly in your favour for finding such a solution with a difference of 0 or 1. But I don't think it is generally the case that the numbers greatly outweigh the number of partitions in that way.

Anyway, I don't know how much of the article you read, but it does say there are (and gives) a number of heuristics that work fairly well in most cases (at least for partitioning the set in two)


Oh, and
[150, 251, 477, 888, 999, 1315]
[215, 277, 315, 1000, 1059, 1214]
[200, 212, 400, 697, 1137, 1433]
[370, 414, 450, 581, 841, 1423]
To name but one of some 60 solutions.
Title: Re: Fair Shares
Post by MathsForFun on Jul 28th, 2010, 8:00am

on 07/28/10 at 06:19:37, towr wrote:
The only way to even tell that your solution is optimal is if the difference is 0 or 1, or exclude all other solutions.

My experience is that with large numbers of items, this is usually the case. In the case of this puzzle, the total value is £16318. Divided by 4, this is £4079.50, so a good starting place is to try to make the four piles each sum to either £4079 or £4080 (this works in this case).


Quote:
True enough, if the number of numbers greatly outweighs the number of partitions, and the numbers are not chosen to frustrate partitioning, then chances are indeed greatly in your favour for finding such a solution with a difference of 0 or 1. But I don't think it is generally the case that the numbers greatly outweigh the number of partitions in that way.

Anyway, I don't know how much of the article you read, but it does say there are (and gives) a number of heuristics that work fairly well in most cases (at least for partitioning the set in two)

I saw that, and I don't know how to reconcile it with the problem being NP-complete. Can anyone explain that, please?



Quote:
Oh, and
[150, 251, 477, 888, 999, 1315]
[215, 277, 315, 1000, 1059, 1214]
[200, 212, 400, 697, 1137, 1433]
[370, 414, 450, 581, 841, 1423]
To name but one of some 60 solutions.

Correct - well done!  8)
Title: Re: Fair Shares
Post by rmsgrey on Jul 28th, 2010, 8:27am

on 07/28/10 at 08:00:30, MathsForFun wrote:
I saw that, and I don't know how to reconcile it with the problem being NP-complete. Can anyone explain that, please?


While perfect solutions to NP-hard problems are inefficient but guaranteed to always find the right answer, it's often possible to find a good solution that is efficient, but not perfect - either it always finds an answer within a small error of the right answer, or it usually finds the right answer, but fails on pathological cases - and in either case, it gives you an answer quickly.
Title: Re: Fair Shares
Post by MathsForFun on Jul 28th, 2010, 8:37am

on 07/28/10 at 08:27:48, rmsgrey wrote:
While perfect solutions to NP-hard problems are inefficient but guaranteed to always find the right answer, it's often possible to find a good solution that is efficient, but not perfect - either it always finds an answer within a small error of the right answer, or it usually finds the right answer, but fails on pathological cases - and in either case, it gives you an answer quickly.

Thanks - that answer was helpful, comprehensive, and all packed into a single sentence!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board