I read somewhere about the incompatible pairs problem where you have a list of things, and a list of pairs that are incompatible (ie you can't pick both from a pair). You have to pick a certain number from the list w/out violating any of the incompatible pairs. It said solving with brute force (construct all possible answer lists ignoring the pairs, then go through and test them all) takes too much computing resources to be feasible (except with very small list and pair list). If you have to pick x things from n options with p incompatible pairs, brute force would take n! / ( x! * (n-x)! ) to get our lists and then *2px for worst case (our lists are size x and we gotta check p pairs and the simplest way is to scan list to find one half the of the pair, then scan for the other half ... not efficient but whatever). anyway, the important thing is that n!. factorial is evil and owns all the other numbers.
Anyway, I can do it using 2^p lists in the worst case, which is loads better usually (big n and not-insanely-big p), but still exponential resources use. my technique reminds me of MWI ^^ ok, start with 2 copies of the list of items. now take the first incompatible pair (1, 2) for any 1 and 2, and scratch 1 off one list, and scratch 2 off the other list, so they become differentiated. next up, take another pair, and for each list we have, differentiate it into 2 and mark off 1 on one list and 2 on the other. if a list has 1 or 2 missing, you don't have to split it this step, so we're not actually gonna use the full 2^p lists. not sure how to approximate how many we really will use. anyway, after you go through all the pairs, you'll have lots of lists with various amounts of items remaining. take all the ones with enough items, and for the ones with extra, use some combinatorics to get all the possible ways to pick x things out of them if you want. another way to save resources is if a list ever gets too small just delete it and never split it again.
anyway, anyone know a better way or another cool problem?
oh, umm, an example of an incompatible pairs problem: you have an apartment complex with space for x people and you want it full, a list of n applicants, and a list of p pairs of applicants who fight and thus you can't have both.
from comments, woty wrote: A person has a sibling. What are the chances that the sibling is the same gender as they are? (it's not 50%)
and Gil gave this answer: MF FM FF and MM are the possiblities, we'll go with boys, so FF is out, and MM is once of the 3 options, so 1/3 chance. this is a well-known answer.
anyway, that's WRONG
it *is* 50%. the above answer does not take into account anything about the possibility of meeting either sibling. the MM option is really *two* options, meeting *either* the younger or older sibling.
another way to put it, is: if you've met the older sibling, the options are FM and MM which is 50/50 either way. and if you met the younger sibling, the options are MF and MM which is also 5/50 either way.
Two troubled turtles trotted to the temple. There they told the templekeeper their troubles. Twice they'd tried, twice trashed: transforming tricky tensors too tough. The templekeeper told them to travel to the true temple to try the tenfold tensor trial there. Three trials of transforming tensors, three tribulations to triple tempo, two to try triangulating, then turning ten tridecagons to two tensors, then throwing trigons through the target. Temple trial taken, tempo tripled, tensor transforming totally terrific, the two turtles travelled to the terrible trap: two tests Thursday.
If you want to continue the story, you can in comments. You could do a diff letter if you wanted. I might later, if I feel like it.