Author |
Topic: Fair Shares (Read 1250 times) |
|
MathsForFun
Full Member
Posts: 153
|
 |
Fair Shares
« on: Jul 28th, 2010, 2:21am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Fair Shares
« Reply #1 on: Jul 28th, 2010, 2:38am » |
Quote Modify
|
One solution I did by hand gives each of them: 4069, 4073, 4099, 4077
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Fair Shares
« Reply #2 on: Jul 28th, 2010, 3:38am » |
Quote Modify
|
Also by hand, I got to
| hidden: | 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 |
|
|
IP Logged |
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Fair Shares
« Reply #3 on: Jul 28th, 2010, 4:00am » |
Quote Modify
|
on Jul 28th, 2010, 2:38am, towr wrote:One solution I did by hand gives each of them: 4069, 4073, 4099, 4077
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...
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Fair Shares
« Reply #4 on: Jul 28th, 2010, 5:14am » |
Quote Modify
|
on Jul 28th, 2010, 4:00am, 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 
[/edit]
|
| « Last Edit: Jul 28th, 2010, 5:19am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Fair Shares
« Reply #5 on: Jul 28th, 2010, 5:41am » |
Quote Modify
|
on Jul 28th, 2010, 5:14am, 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 |
|
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!
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Fair Shares
« Reply #6 on: Jul 28th, 2010, 6:19am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 28th, 2010, 6:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Fair Shares
« Reply #7 on: Jul 28th, 2010, 8:00am » |
Quote Modify
|
on Jul 28th, 2010, 6:19am, 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! 
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Fair Shares
« Reply #8 on: Jul 28th, 2010, 8:27am » |
Quote Modify
|
on Jul 28th, 2010, 8:00am, 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.
|
|
IP Logged |
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Fair Shares
« Reply #9 on: Jul 28th, 2010, 8:37am » |
Quote Modify
|
on Jul 28th, 2010, 8:27am, 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!
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print