Originally posted by: Random Variable
The probability of getting 13 games right is (1/3)^13, while the probability of getting 12 games right is 13*(1/3)^12*(2/3); therefore, the probability of getting at least 12 games right is (1/3)^13+13*(1/3)^12*(2/3) = 1/59049. So if you submit 59049 entries, there will theoretically be a 100% chance of getting first or second place.
Note that 59049 = 3^10. The fact that there are 13 games is immensely important. Consider one submission. How many of the 3^13 results are within one game of it? Well, you can be off in any one of the 13 different games in two different ways. Therefore, one submission can account for 1+2*13 = 27= 3^3 results. Therefore, you need at least 3^13/3^3 = 3^10 submissions. All that's left to show is that you can cover all the results in this way without overlap. (This is non-trivial)
This is immensely important in coding theory. There are codes called Hamming Codes, which can correct one error. There is a code called the (13,10) Hamming Code that takes in 10 ternary bits, and tags on 3 more ternary bits (the resulting string of length 13 is called a codeword) in such a way that if one of the bits is wrong, it can correct that bit to the right bit. You can show that every ternary bit string of length 13 is within one bit of those 3^10 codewords. Such codes that have this property are called Perfect Codes. There are two kinds of Perfect Codes: Hamming Codes and Golay Codes.
That's a little long winded, but I find this stuff fascinating.
