$15.00
$5.00
$20.00
Jeff Warrender
United States
Averill Park
New York
flag msg tools
designer
publisher
mbmbmbmbmb
I have a math problem for which I don't know what branch of mathematics is the right one to use, but I believe that one exists.

The idea is this. Say that I have a mystery game, and players are trying to identify which of the six possible suspects committed the crime. (Actually, the game in question is about a different subject but the underlying math problem is the same).

Say that each suspect has several traits -- "tall", "wearing a hat", "has a beard", etc. Say there are six traits in total, but each suspect will only have a subset of these.

Now say that I have six "witness" cards, each of which corresponds to one of the six traits. So a witness card might say "the culprit was tall" or "the culprit was female".

Further, let's let the "solution" for the game consist of four of these witness cards, randomly drawn during setup -- these are the four traits that the culprit has. They would start the game hidden, and then the action of the game would be about gaining access to these witness cards.

What I need to figure out is how to distribute the traits among the suspect cards so as to guarantee that any four witness cards identify one and only one suspect.

I know that I need to adhere to a rule whereby any pair of suspect cards can only share at most three traits. Or maybe it's stronger than that, and that every pair of cards must share exactly three traits.

It's a small enough problem space that I might be able to brute force it out, but if any of the numbers (number of witness cards, number of possible traits, etc) become bigger this will be harder to do.

I know there's some mathematical method for achieving this; Spot it! does something similar, for example. Does anyone know how this kind of thing is done?

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Colin Gillespie
Canada
Strathmore
Alberta
flag msg tools
mbmbmbmbmb

Sounds like you will at least need some statistics, and maybe some set theory in there too. I'll take a stab at a simplified version of what you said though:

Say just for that sake of argument that your traits are Athletic, Brainy, Charismatic, Dangerous, Enigmatic, and Funny. Assuming that the traits are not dependent on each other (e.g. being Charismatic affects whether or not you can be Funny), and that each suspect has 4 traits assigned to them, the total number of suspect combinations would be:

6 x 5 x 4 x 3 = 360

That sounds like way more than you would want though, so that's where you bring in dependent variables and it lowers things down by quite a bit and you go down from the number of cards in a spot-it deck to the number of suspects in Mystery of the Abbey or the number of faces on a Guess Who board. So now instead of random traits that may be assigned, we have categories that are linked...

Lets say that the traits are more like what you started off with. The suspect could have a certain Body Type (Stocky/Thin/Athletic), a hairstyle (Bearded/Clean shaven/mustachioed), and a defining article of clothing (hat/glasses/jewelry). You now have 9 clues that could be given, but the list of suspects is down to:

3 x 3 x 3 = 27

You should Definitely check out Mystery of the Abbey from DoW. It sounds like even if the gameplay is nothing alike, you could gain inspiration from it's method of deduction.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Warrender
United States
Averill Park
New York
flag msg tools
designer
publisher
mbmbmbmbmb
Thanks! Yes, Mystery of the Abbey is a good analogy for the kind of thing I'm hoping to achieve, at least with respect to having a suspect pool and having people in that pool having traits.

One key difference is that, if at all possible, I'm hoping that the traits will be fully orthogonal. What I mean is that there's a witness card that says "the culprit had a beard", but there is NOT a card that says "the culprit did NOT have a beard". This simplifies the setup -- just shuffle your witness cards, pick 4, and go. Admittedly it's not that much more effort to pick one trait card from each of several piles.

Looking at the Spot It forums, it sounds like something like "Fano planes" might be pertinent, but the issue with that approach seems to be that you can have several traits but any pair of traits intersects at one and only one point; whereas it seems that my idea, to work, would need each pair of traits to have several overlapping points, or else you've overdetermined the solution with 4 cards.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Gibbs
Canada
Ottawa
Ontario
flag msg tools
mbmbmbmbmb
I'd say the branch of Mathematics would be Combinatorics.

https://en.wikipedia.org/wiki/Combinatorics
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Warrender
United States
Averill Park
New York
flag msg tools
designer
publisher
mbmbmbmbmb
Hmm, that may be right. But I think there's definitely a graphical approach to this. It seems tricky to have each trait be a line, and to need to intersect every other line three times. It seems like the trait could be a U shape, and if two U's are at some angle to each other then they can touch at 3 points. But I'm not sure yet how to arrange 6 U's such that each node is touched by four U's and each U touches each other U at exactly 3 points...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Gibbs
Canada
Ottawa
Ontario
flag msg tools
mbmbmbmbmb
jwarrend wrote:
Hmm, that may be right. But I think there's definitely a graphical approach to this. It seems tricky to have each trait be a line, and to need to intersect every other line three times. It seems like the trait could be a U shape, and if two U's are at some angle to each other then they can touch at 3 points. But I'm not sure yet how to arrange 6 U's such that each node is touched by four U's and each U touches each other U at exactly 3 points...



"One of the oldest and most accessible parts of combinatorics is graph theory, "

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
msg tools
designer
mbmbmbmbmb
coligill wrote:
Say just for that sake of argument that your traits are Athletic, Brainy, Charismatic, Dangerous, Enigmatic, and Funny. Assuming that the traits are not dependent on each other (e.g. being Charismatic affects whether or not you can be Funny), and that each suspect has 4 traits assigned to them, the total number of suspect combinations would be:

6 x 5 x 4 x 3 = 360

This is wrong, unless order matters. You are treating Athletic + Brainy as being different from Brainy + Athletic.

Assuming that traits are simply "on" or "off", and the order they are listed has no effect, then the number of combinations is given by the binomial coefficient 6-choose-4, which happens to be 15. (Also notice that 6-choose-4 equals 6-choose-2; choosing 4 traits to use is the same as choosing 2 traits to leave out.)

This is pretty similar to identifying the monster in my game Hunt: The Unknown Quarry, where the monster gets 2 random powers out of a set of 5 options (and you can find the other 3 to use process of elimination), which gives 10 possible monsters.

Also note that this is MUCH simpler than what you have to do for Spot it!, whose gameplay requires that any pair of cards has exactly one trait in common. That means there are many combinations of symbols from their set that they can't use (without breaking the game)--for instance, if one card has traits ABC, then you can't ever make a card with traits DEF, because there's no commonality, and you also can't use ABD, because there's too much commonality.

However, it's also more restrictive, because 6-choose-4 requires you to have exactly 15 suspects in your game. If you discover for some reason that your game would really work better with 14 suspects, you're out of luck, because when you shuffle 6 cards and draw 4, there's no way to guarantee that one of those 15 possible combinations simply won't come up; you'd have to change the total number of traits and/or the number of traits per suspect (and you'd have a hard time finding a combination that gives exactly 14 suspects). In contrast, Spot It! works totally fine if you remove a few of the cards (and IIRC, they actually did remove 2 of the possible cards they could have included, probably for no reason other than manufacturing convenience).
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Dimitri Sirenko
Canada
Vancouver
BC
flag msg tools
jwarrend wrote:
I have a math problem for which I don't know what branch of mathematics is the right one to use, but I believe that one exists.

The idea is this. Say that I have a mystery game, and players are trying to identify which of the six possible suspects committed the crime. (Actually, the game in question is about a different subject but the underlying math problem is the same).

Say that each suspect has several traits -- "tall", "wearing a hat", "has a beard", etc. Say there are six traits in total, but each suspect will only have a subset of these.

Now say that I have six "witness" cards, each of which corresponds to one of the six traits. So a witness card might say "the culprit was tall" or "the culprit was female".

Further, let's let the "solution" for the game consist of four of these witness cards, randomly drawn during setup -- these are the four traits that the culprit has. They would start the game hidden, and then the action of the game would be about gaining access to these witness cards.

What I need to figure out is how to distribute the traits among the suspect cards so as to guarantee that any four witness cards identify one and only one suspect.

I know that I need to adhere to a rule whereby any pair of suspect cards can only share at most three traits. Or maybe it's stronger than that, and that every pair of cards must share exactly three traits.

It's a small enough problem space that I might be able to brute force it out, but if any of the numbers (number of witness cards, number of possible traits, etc) become bigger this will be harder to do.

I know there's some mathematical method for achieving this; Spot it! does something similar, for example. Does anyone know how this kind of thing is done?



You should look into using nCr formula for this. It is combination probability formula easily described on many websites when googling.

On the side note. Is this a game you are designing? It sounds A LOT like Deception: Murder in Hong Kong. Might want to check it out to make sure its not too similar
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Byron S
United States
Ventura
California
flag msg tools
I don't remember what I ate last night
badge
but I can spout off obscure rules to all sorts of game like nobody's business!
mbmbmbmbmb
If you have 6 traits, then your unique combinations (15 of them, as Antistone said) are:
1234
1235
1236
1245
1246
1256
1345
1346
1356
1456
2345
2346
2356
2456
3456

You can extend this pattern to any number of traits without too much difficulty.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Colin Gillespie
Canada
Strathmore
Alberta
flag msg tools
mbmbmbmbmb
I realized upon review that my initial evaluation of the "Independent variables" example was wrong. And when I brute forced it and looked at what the actual arrangements were, it got a bit weird on me, and I ended up with only 15 different combinations:

A B C D
A B C E
A B C F
A B D E
A B D F
A B E F
A C D E
A C D F
A C E F
A D E F
B C D E
B C D F
B C E F
B D E F
C D E F

This assumes that the same variable cannot come up more than once (AAAA is not valid), and that the order is not relevant (ABCD = DCBA). It seems that it might be more feasible than I thought to just throw a bunch of variables in.

* Edit - Ninja'd!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Alison Mandible
United States
Cambridge
Massachusetts
flag msg tools
mbmbmbmbmb
I believe that what you're asking about is a "block design".

https://en.wikipedia.org/wiki/Block_design

That may be too technical to help (it was too technical for me to figure out how it applies to your situation!) but if you want to math it up, might be useful?

2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Warrender
United States
Averill Park
New York
flag msg tools
designer
publisher
mbmbmbmbmb
Thanks for all the replies. My hope had been that there was some sophisticated way to assign the traits so as to ensure that you always get a unique solution no matter which 4 witness cards you pick, but it seems like the only way to guarantee this AND to guarantee that you need all 4 witness cards is the brute force "many suspects" approach. Maybe that's not too bad; or alternatively, it does seem that it's possible to choose a set of (say) 6 suspect combinations such that (a) each trait is present in exactly four suspect cards and absent from 2, and (b) every pair of traits is present on at least two cards, and (c) any four witness cards is certain to give a unique solution. In some cases you find that you only actually needed three of the witness cards to yield the solution, but maybe that level of redundancy is tolerable; will have to playtest to see.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
msg tools
designer
mbmbmbmbmb
jwarrend wrote:
Thanks for all the replies. My hope had been that there was some sophisticated way to assign the traits so as to ensure that you always get a unique solution no matter which 4 witness cards you pick, but it seems like the only way to guarantee this AND to guarantee that you need all 4 witness cards is the brute force "many suspects" approach.

Sorry, I thought that was a given.

Ignore for the moment that you also wanted all 4 witnesses to be required, and just think about cutting down the number of witnesses.

This is limited mostly by the assumption that each witness works by absolutely excluding all of the suspects without the matching trait. That is, if you get a witness saying the suspect was tall, then you immediately know with 100% certainty that all of the non-tall suspects are innocent, no matter what the rest of the witness cards are.

Given that--plus the fact that the number of traits per suspect is equal to the total number of witnesses--you need at least as many suspects as there are combinations of witnesses in order to ensure that one of them is always guilty.

Look at it this way: one of the possible combinations of witnesses is ABCD. If there is no suspect with A, B, C, and D traits, then if you happen to draw that combination of witnesses, there will be no valid solution (no suspect will match the full description). If each suspect only matches one description, then clearly you need as many suspects as there are descriptions.

In order to get around that, you would need one suspect that is a valid solution for multiple combinations of witnesses. For example, if the combinations ABCD and ABCE both pointed to the same suspect.

You could do that by giving each suspect more than 4 traits--maybe the suspect has ABCDE, and so he works as a suspect for the witness sets ABCD, ABCE, ABDE, ACDE, and BCDE.

Or you could do that by not requiring a 100% match. Maybe the suspect only has traits ABC, but you say that 3 out of 4 traits is close enough and that 4th witness must be mistaken.

Maybe you've got a scoring system where each witness says something more complex, like "tall: 3 points; red-head: 1 point" and then once you have all the witnesses you need to add up a score for each suspect based on how many of the qualities they match to determine which of them is the best fit.

But as long as the number of traits per suspect matches the number of witnesses, and you choose the witnesses at random, and every witness lists 1 trait, and the guilty suspect is required to match ALL of them...you will need as many suspects as there are combinations of witnesses.



Which means I'm pretty sure you're wrong in this part:
jwarrend wrote:
alternatively, it does seem that it's possible to choose a set of (say) 6 suspect combinations such that (a) each trait is present in exactly four suspect cards and absent from 2, and (b) every pair of traits is present on at least two cards, and (c) any four witness cards is certain to give a unique solution. In some cases you find that you only actually needed three of the witness cards to yield the solution, but maybe that level of redundancy is tolerable; will have to playtest to see.

If by a "unique solution" you mean that there are never TWO (or more) suspects that match all of the witnesses, you can do that. But you're accepting cases where ZERO of the suspects match. If you want to ensure that exactly one suspect matches, then no, that's not possible.

Your rules for determining who is guilty are a function from the set of all descriptions (that is, all possible combinations of witnesses) to the set of all suspects. If you want that function to be one-to-one, then those sets need to be the same size.
2 
 Thumb up
1.00
 tip
 Hide
  • [+] Dice rolls
Chris Robbins
United States
Alcoa
Tennessee
flag msg tools
mbmbmbmbmb
I'm too lazy to do all the mathy stuff, but it sounds like Lie Detector.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Warrender
United States
Averill Park
New York
flag msg tools
designer
publisher
mbmbmbmbmb
Ah, I see your point, and you're right; it does need a full set of possible solutions to ensure that there's always a solution. One alternative might be "you keep adding traits until there's a valid solution (i.e. one and only one subject matches the face-up traits)", but it's probably possible to end up with a non-unique solution in that way.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
msg tools
designer
mbmbmbmbmb
jwarrend wrote:
Ah, I see your point, and you're right; it does need a full set of possible solutions to ensure that there's always a solution. One alternative might be "you keep adding traits until there's a valid solution (i.e. one and only one subject matches the face-up traits)", but it's probably possible to end up with a non-unique solution in that way.

Well, you can't end up with a non-unique solution, because if you do, that just means you need to keep drawing more witnesses. But you could end up with NO solution, if a single witness eliminates both of your last 2 suspects at the same time.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
wayne mathias
United States
Niceville
Florida
flag msg tools
mbmbmbmbmb
Think of each trait as a digit in a number. Each suspect must have a unique number.

A list of all possible numbers gives an even distribution of traits with each a unique combination of traits.

A trait would be something like sex or headgear or facial hair with multiple possible values.











 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.