|Posted: August 27, 2010, 1:17 am - IP Logged|
Here's a math problem that I'm convinced I can use for specific types of lotteries if I can just figure out how to do it.
I have 34 variables and 48 equations. What I need to do is be able to sort the 34 variables, the exact values need not be known and the system of equations may not be deterministic. Most of the equations are of the form:
P(a) * P(b) * P(c) = P(1)
16 of them have three terms as above, others have 4 terms and 5 terms. the resultant P(1) is a published and known value.
However some of them are composite in that the result is only published for a sum of several of the equations i.e.:
P(a) * P(b) * P(c) + P(d) * P(e) * P(f) = P(1)
Obviously with the first form, one can take logarithms and solve a system of equations provided a deterministic set of 34 equations can be found. The logarithmic form would look like:
log( P(a) ) + log( P(b) ) + log( P(c) ) = log( P(1) )
but of course, I don't know how to deal with the composite relationship form other than omitting them or proportioning them in a trial and error fashion.
Brute force in hopes of finding a deterministic set of 34 equations in the set of 48 equations isn't an option because 48 choose 34 is huge and solving a set of equations is also compute intensive. The idea is to be able to arrive at a solution quickly at the convenience store.
Exact solutions are not needed and the probabilities represent whether a given symbol is in one group or another, however it is known that 23 symbols are in one group and 11 symbols are in the other. The idea is to select 12 or 13 likely candidates for the later group and to evaluate each combination for plausibility by a heuristic evaluation.
Since the probabilities only needs to be ordered, an exact solution is not needed so perhaps representation in terms of surprisal might help. Surprisal is when probabilities are expressed as bits of surprisal where each surprisal is a 50/50 event such as a coin toss therefore the probability of 1/1000 would be ln(1000)/ln(2) bits of surprisal i.e.: 1/( 10 * H(t) ).
Four of the published probabilities, affecting 9 of the equations are significantly lower than the others by at least two orders of magnitude so they could be assumed to be zero if necessary. Remember it's only the relative ranking that's important. But so far, that leads me to a time consuming manual Sudoku style heuristic solution. That is, I wind up with 9 statements of at least one of these 5, 4, or 3 symbols is in the second group and having to resolve the interelationships of these statements. I tried working with only those 9 equations but it's insufficient to identify candidates for the 11 symbols in the second group.
The task is essential decryption of a substitution code where 34 symbols have been substituted for 2 concepts. Normally such code-breaking is based on frequency of symbol prevalence which is why I'm relating them to published probabilities and followed by heuristic rationalization which in code breaking involves comparison with dictionary words. I have noted a set of heuristics conditions that must be satisfied for the solution to be plausible so I don't think I need any additional contributions there (best to limit the focus for the time being).