I'm a bit uncomfortable with using that formula for a rigorous analysis of the "examine all subsets of size k" solution.
I can agree with it for the "randomly sample all subsets" solution, because I can even show that it is quite pessimistic there. And it would certainly convince me during the contest (had I come up with it) that this approach was worth trying. However, from the problem setter's point of view, I'd want to come up with a set where all 3-subsets have distinct sums. More generally, I'd want to find a set that maximizes the minimum cardinality of the answer. The birthday paradox formula does not exclude the existence of such a set, though it indicates that it might be quite difficult to find. I'm fairly sure that the numbers in such a set simply grow too fast (from my attempts to construct it) though I don't have a proof that there isn't a significantly more economical construction. I found some literature about sets where all subsets have distinct sums, but nothing yet about k-subsets for small k. Flipping the problem around, can you find a set of 500 numbers in the range [1, 10^15] such that testing all 3-subsets won't find a collision? The birthday formula gives only a 7% success rate, but I suspect that it is guaranteed to work even in this expanded range. On May 6, 7:49 am, "Richard Braakman" <[email protected]> wrote: > > All results had 3 numbers or less for me, so probably there is more to it. > > No I think your analysis is enough. > > Picking 3 numbers from 500: about 20 million possibilities (500!/497!/3!) > > Range of the sum of 3 numbers of that set: about 3 * 10**12 > > According to the formulas on the wikipedia page for the birthday problem, > drawing 20 million numbers from that range gives an almost certain collision. > The chance of not finding one would be about 1 in 10**31. > > Richard Braakman -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
