Awesome, that is the kind of counting I wanted to see :) Not too happy that I didn't see that myself though.
The 10 in front is C(5, 2), right? I didn't mean necessarily disjoint triples but that wouldn't change things too much anyway. Thanks Luke, On May 6, 9:01 pm, Luke Pebody <[email protected]> wrote: > I am pretty sure you can find such a set, yes. Greedy Algorithm will work. > Take the smallest positive integer you can at each stage that won't cause > two triples to have the same sum. > > The number of forbidden numbers, if you have n numbers already, is at most > 10C(n,5). For n = 500, this is about 500^5/12=31250000000000/12=2.6x10^12. > On 6 May 2012 19:29, "[email protected]" <[email protected]> wrote: > > > > > > > > > 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. -- 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.
