Math problem for a dope, Part Deux...

Factual Questions
1

Thanks to everyone who helped with my previous question. I humbly turn to you all again for help as I stare into the cheering abyss of numbers and confront my own bewilderment.

I am trying to set up a very simple swapping game, using poker chips of different values. I have 100 white chips, 50 red chips, and 50 blue chips. I want to distribute the chips so everyone has the same total value of chips but in different combinations. It’s not important that everyone have a unique combination, only that there is significant variety between players.

The object of the game is for people to swap chips so each ends up with their original, identical value of chips but now everyone has the same distribution of denominations, say, 4 whites, 2 reds, 1 blue. (The actual number and values of the chips don’t matter as long as it all fits together, each person has the same starting value of chips and there is some variation in the combinations of chips.)

Here’s where my brain freezes in simple awe at the sheer implacable majesty of numbers.

I do not know how many people will show up for the game. It will be a number between 16 and 22. Is there a way to walk into the room with my chips, count heads, then quickly figure out the assigning of values to the different chips and the number of chips of each colour to distribute the chips in accordance with the rules laid out above?

I don’t need to distribute all the chips I have, but I don’t have any more. I want everyone to start with the same value of chips but with people having this value in different assortments of denominations, and I want it to be possible for everyone to end up with the same original value of chips in the same distribution of denominations. And I’d like this to be possible with all of the chips originally distributed in play.

I am completely baffled by this problem of my own creation and so I humbly appeal to the awesomeness of this board for aid and succour.

2

Not unless you’re going to leave some chips out of the distribution. For example you have 50 red chips. 50 = 255 so the only number of people that could end up with the same number of red chips are 1 2 5 10 or 25 and 50. None of those numbers are in your range of participants.

If for example 19 people show up. You’ll have to hand out either 19 or 38 red and blue chips.

3

Yes, that’s fine, I don’t need to distribute all the chips. It’s the “how to distribute however many it takes, given my amount available, sort of randomly and evenly” part that has driven me to distraction. I could just tell people, “here are the values, pick out the number you need,” but then may not have, for example, the needed 16-22 blue chips in play.

4

The only real contraint is how many chips you have – for chips of a given colour will have to be distributed in multiples of the number of players.

Example:
suppose there are 17 players and you have

90 white chips
60 blue chips
and
50 red chips

Then the maximum numbers of each colour distibuted will be

5 white chips, with 5 left over (517+5=90)
3 blue chips, with 9 left over (317+9=60)
2 red chips, with 16 left over (2*17+16=50)
In practice achieving this should not be hard. If there are N players, deal the chips of each colour one-at-a-time into N piles until you have less than N left, then stop.

Now make swaps of equal value between pairs of piles (swapping say, two 1$ chips in one pile for one 2$ chip in another). Continue like that until you’re satisfied with the mixture.

I’m curious, can you tell us what info each player will have? (just what chips they themselves have?) And what is the protocol for exchanges between players?

ETA

That probably won’t work unless by sheer chance the chips are selected in multiples of the number of players.

5

In the other thread you wrote
“They’ve been given these point values: white=1, red=2, blue=4.”
Is this fixed, or would you accept other value assignments?

Either way, I think you just want to prepare, by brute force, a printed recipe showing what you’ll distribute for each K, K = 16, …, 22. I think many Dopers could prepare such a recipe for you with relative ease.

BTW, if K is 17 or more, you’ll only be able to pass out 2K reds and 2K blues. How important is it that you be able to give 3K of each such color when K=16 exactly?

6

This is somewhat related to the Knapsack Problem.

If it were me, I’d probably just try a heuristic approach. Randomly distribute an equal number of chips (ignoring value) to each player. Then in a second step, move chips around to get everyone to have the same value. (Of course there are some cases where you’ll need to discard chips in this step; that is, remove a chip from one player but don’t give them to another player.) The details of this redistribution step are not entirely clear to me, but I think it can be done.

–Mark

7

Let’s work from the end state. If we want, e.g. 4 Blue + 3 Red + 2 White to be the end state for each player after folks have traded, then for N players we need to distribute a total of 4N Blues, 3N Reds, and 2N Whites at the start.

You talk about the “value” of the chips. So you have to decide ahead of time what the value of a blue, red, and white chip is so the idea of a total has meaning. If you decide that e.g. blue = 10 points, red = 5 points, and white= 1 point, then the goal state is worth 410 + 35 + 2*1 = 57 points.

So at the beginning you need to hand each person 57 points worth of chips, but not in the simple 4B+3R+2W arrangement. At the same time, you need to hand out a total of 4N Blues, 3N Reds, and 2N Whites to everyone collectively.

As you saw in the answers to your earlier post, there are a very finite number of ways to decompose, e.g. 57 points into the three kinds of chips and one thing they have in common is they don’t all require the same number of chips.

Qualitatively speaking, there is a very small overlap between solutions to the first problem (equal point totals) and those that add up to giving out the right total chip count so everybody can reach the goal state.

My intuition is the problem is only possible for carefully chosen values for all the starting variables (i.e. goal state, chip point values, and therefore total count of each kind of chip). And even then a particular set of starting values will only work for certain Ns. Different Ns may be impossible or will certainly require a different set of starting variables.

My secondary intuition is you’ll find the problem is impossible except in pretty trivial circumstances. e.g. make all the chips worth 1 point. Presumably the goal here is to create a party game and hope the players will collectively discover the trading algorithm that gets them all to the goal state. I fear you’re going to create a game that’s either a) utterly trivial, or b) utterly impossible.

Unless the only people you invite are chaps like septimus and indistinguishable.

8

The point value is immaterial. I started backwards (my spouse detects a pattern here) by thinking, okay, I need different point values and they should be easy for people to calculate. 1-2-4 is pretty easy… Sometime before I had my coffee this morning it dawned on me that was not the place to start and that the point values of each colour would have to be different and that was fine, if only I could figure out what they should be.

LSLGuy may have ignored one option: this might be utterly impossible AND utterly trivial.:eek:

I am pleased to reflect that what I thought would be a very simple problem with a solution like, “hey, dummy, just cross-multiply and divide!” is a little trickier. It hardly makes me feel smart, but it does make me feel very slightly less stupid. :o

9

The idea is simple, just walk over to somebody else and say, hey, I have X white chips and need Y blue chips, and I couldn’t help but notice you have more blue chips than you need…

It’s partly an icebreaker for a class (thus I don’t know if everyone will be there or not, but there are 22 people signed up) and a way to start people thinking about Adam Smith’s line about the human “the propensity to truck, barter, and exchange one thing for another” at the simplest level.

10

Broadly I like the idea, as a mathematical exercise I’m not sure what it means that everyone can see everyone else’s chips, but as an icebreaker I’m sure it works fine. What’s your subject? And at what level do you teach it? (ETA, I suppose Economics.)

11

It’s decidedly not a mathematical exercise! I was trying to figure out a simple way to start a discussion on trade that would also have students move around, talk to each other, make some noise, and think about some of the assumptions we make about trade. It’s a fourth year history class and part of what we’re doing is looking at Marx and why he thought production, not trade, was the key to understanding a society, if in only to consider that we have to produce goods before we can trade them. I thought, great, we’ll swap some stuff around, introduce ourselves, chat about what trade does and doesn’t tell us about a society, then hit the hard stuff. I’ve spent more time figuring out the damn chip distribution than the entire exercise will take! :smack:

12

You can certainly arrange it so that the problem is, at least in theory, solvable. If you have, say, 18 participants you can start by making 18 stacks, each containing 5 white, 2 red and 2 blue chips. Using your predetermined exchange rates, you then swap chips between pairs of stacks, maybe 20 times or so, before you hand them out.

Of course, there’s also a rather obvious Marxist solution to this: “Hey guys! Let’s just all put our chips on this table and share them evenly among us!”

13

That will be the correct answer to the final exam.:smiley:

14

Says the Comrade named Kropotkin. Perfect! :slight_smile:

15

Welcome to the Party! But we won’t be serving Lenin Harangue Pie.

16

The point values need not actually be different: they could be 1-1-1, but each player needs a proper complement of each of three “necessities.” Exchanges would be very simple.

A problem with 1-2-4 is it might not be much more interesting than the 1-2-4 case; you’d have almost nothing but trades of 2 whites for a red, and 2 reds for a blue. More interesting (and fun!) is 1-2-3 where 2 reds for blue-and-white, and red-and-white for blue would be common trades.

You’d probably not want 2-3-5 where more complex swaps would be needed.

Once you settle on a value assignment, I think it will be easy to get the “recipes” I mentioned.

17

I’ve already been exposed in a recent thread as the kind of pervert who works tedious little enumerations for pleasure, so I may as well show an example recipe for OP’s problem.

Let the chip “values” be
[ul]
[li] White #100 @ $2[/li][li] Red #50 @ $3[/li][li] Blue #50 @ $5[/li][li] Total #200 = $600[/li][/ul]
Divide the 200 chips into 25 bags, each with total value $24 according to the following schedule.

It remains only to select N bags for N players such that the total chips in the N bags are 4N white, 2N red, 2N blue; and uniform bags can be obtained via a series of 2-person equal-value swaps. This is achieved with the following assignments. I’ve arranged the 25 bags into three groups – eleven bags you always pass out; five bags you always pass out whenever N > 17; and nine bags which you must be careful with, giving them out only for particular N.



B-R-W     N=16  N=17  N=18  N=19  N=20  N=21  N=22
-----     ---   ---   ---   ---   ---   ---   ---
0-0-12     X     X     X     X     X     X     X
0-4-6      X     X     X     X     X     X     X
0-6-3      X     X     X     X     X     X     X
1-3-5      X     X     X     X     X     X     X
2-0-7      X     X     X     X     X     X     X
2-4-1      X     X     X     X     X     X     X
3-1-3      X     X     X     X     X     X     X
3-3-0      X     X     X     X     X     X     X
4-0-2      X     X     X     X     X     X     X
4-0-2      X     X     X     X     X     X     X
4-0-2      X     X     X     X     X     X     X

0-0-12     .     X     X     X     X     X     X
1-1-8      X     .     X     X     X     X     X
3-3-0      .     X     X     X     X     X     X
3-3-0      .     X     X     X     X     X     X
3-3-0      .     .     X     X     X     X     X

0-2-9      .     X     .     X     .     X     X
0-4-6      X     .     .     .     X     .     .
0-6-3      .     .     .     .     .     X     .
1-3-5      .     .     .     .     .     .     X
1-5-2      X     X     X     X     X     .     X
2-0-7      .     .     X     .     X     X     .
3-1-3      X     .     .     .     .     .     X
3-3-0      .     .     .     .     .     X     X
4-0-2      X     X     .     X     X     X     X
18

I am in awe, and very grateful. That such gods walk the Earth…well, I am not worthy.

Many thanks.

19

I think the auto-generated solutions were correct, but I managed to blunder when I manually transcribed into the table format. Those two lines should read


...
2-0-7      .     .     X     .     X     X     X
3-1-3      X     .     .     .     .     .     .

Back in the 20th century when I worked for a living, I did double- and triple-check my work — Honest! :stuck_out_tongue: