Ah! Real, living story problems!
January 17, 2011 11:14 AM   Subscribe

Math Filter: I am trying to find a name for this equation. I am not sure if I can solve it given the information that I currently have.

Suppose I have a list of photos that I have given to two people.

Originally, I gave each of them the same exact number of photos and the exact same photos.

I do not, however, know how many I have given them, I only know that person 1 said I gave them 9 photos and person 2 said I gave them 12 photos. Each photo has a unique name so I can look at their two lists and see that 7 photos match.

I am left with two unknowns:

1) the total number of photos

and

2)what photos person 1 has that person 2 doesn't and what photos person 2 has that person 1 doesn't.

Is this solvable?

Essentially, I need to find the names of the photos that they do not have in common. The problem is, that I do not know the original list.

My main goal is to find the name of the equation or methodology that would solve this, and an explanation if possible. Feel free to ask for clarification.
posted by occidental to Science & Nature (14 answers total)
 
When you gave the photos to person 1 and person 2, did they each receive the full set of pictures you started with?
posted by xbonesgt at 11:24 AM on January 17, 2011


Best answer: 1) You can establish a lower bound on this number. If you can find the number of matching photos (in your example, 7), then you can say that there are:

7 common photos
2 more from person 1 that do not match
5 more from person 2 that do not match

That gives you a floor of at least 14 photos (but since they can both under report, you cannot get the exact number, just the lower bound)

2) Again, since they can both under report, you cannot get this complete list. You can get (2+5) from the same analysis as above, but again, that is a lower bound.

Does that make sense?
posted by milqman at 11:26 AM on January 17, 2011


Best answer: You want Set Theory.
posted by borkencode at 11:39 AM on January 17, 2011


Unification? Most General Unifier?
posted by the Real Dan at 11:53 AM on January 17, 2011


I think you need to clarify the problem. Is one or both of them lying? Are there constraints on what they did with them or what they can tell you? You could have given each of them 10 million photos (of which they cop to 7 and made up others) with the information provided.
posted by a robot made out of meat at 12:03 PM on January 17, 2011


Response by poster: Both people would have received the full set and both people are reporting to the best of their knowledge. However, as evidenced in the problem, both could have misplaced some of the photos. Person 1 or 2 could be over-reporting I suppose thinking they have additional photos that they do not.

Thanks for the help so far, any suggestions for an algebraic equation with the values listed?
posted by occidental at 12:18 PM on January 17, 2011


If they can under-report _and_ over-report, then you can't really determine anything at all.

Also, are they reporting the names back to you or just a count? Your question makes that a little unclear. The logic I used in my first answer:

(User1TotalPics-MatchingPics)+(User2TotalPics-MatchingPics)=NonMatchingPics is the best you can do with your information.
posted by milqman at 12:27 PM on January 17, 2011


If there is the possibility of mistakes on the answers you get, or the photos can get lost in a way that can't be foresaw, then I don't think you can't avoid the use of probabilities in modelling this situation. This means that at best you can obtain an expected value for the two things you are interested in, but only after you have specified how the mistakes and losses behave (what is called a probability distribution for those two things). If you are not familiar with this kind of modelling, try finding some coursework, lecture notes or such for any college/uni level course that is called (or mentions as its main contents) "mathematical modelling", particularly when they get to "probabilistic systems" or "randomness".
posted by Iosephus at 12:32 PM on January 17, 2011


Response by poster: Thanks milqman, I have been having trouble wrapping my brain around this so sorry if it becomes unclear. Having a lower bound definitely helps.
posted by occidental at 12:41 PM on January 17, 2011


While it looks like people aren't answering your question (name of this problem), the rules of the problem are crucial. Small changes in the rules can have big affects on the solvability.
posted by a robot made out of meat at 12:42 PM on January 17, 2011


Response by poster: It seems that without moving into probability that this may not be solvable given the information. Sorry I am not explaining the rules well but since it is growing out of an actual world scenario it is difficult to ensure that all of the rules are established.

What would happen if I found out how many photos from person 1 did not match person 2 and also how many photos person 2 has that do not match person 1? Could I calculate the total?

Could I calculate how successful they were at matching photos?
posted by occidental at 1:04 PM on January 17, 2011


occidental: "What would happen if I found out how many photos from person 1 did not match person 2 and also how many photos person 2 has that do not match person 1? Could I calculate the total?"

This depends— can person 1 and 2 find the same photo on their own? Can person 1 and 2 discard one or more of the original seven photos? If the answer to both these questions is "no," then you can calculate the total.
posted by yaymukund at 2:32 PM on January 17, 2011


Best answer: And the count would be:

7 + (Person 1's photos that person 2 doesn't have) + (Person 2's photos that person 1 doesn't have)

In set theory notation, it's:
|A ∪ B| = |A ∩ B| + |A ∪ ¬B| + |B ∪ ¬A|
which simplifies to
|A ∪ B| = |A ∩ B| + |A ⊕ B|

(If person 1 and 2 can find the same photo or discard one of the original photos, that changes |A ∩ B| and we don't have any way to find the new amount.)
posted by yaymukund at 2:42 PM on January 17, 2011


Best answer: The set theory from the above posters is probably what you wanted, but you could also treat it as a mark and recapture problem if you need to estimate the total number of pictures if a bunch have been lost.

If you treat person 1 as the first visit and person two as the second visit, you can use the equations from wikipedia - Total photo number estimate = (photos from person 1)*(photos from person 2)/(photos shared by both).
posted by scodger at 7:21 PM on January 17, 2011


« Older How to manage iTunes library with an iPad and w/o...   |   overcoming the anxiety of speaking a foreign... Newer »
This thread is closed to new comments.