Pretty funny Vuelta in the end, very interesting to see how much damage a GC like Remco can do once he's allowed in the breakaways. Very happy for GC Kuss!
I also got the ~8.6% answer from simulations, but felt it wasn't satisfying enough to submit. Simulations don't really give an *answer*, just an approximation of said answer.
Here was what solver David Kravitz (mentioned in the write-up) wrote for "Show Your Work":
The solution is equivalent to making a permutation of 30 items 1,1,1,1,1,2,2,2,2,2,....,6,6,6,6,6, noting this is the order in which the teams finished from first to last, then seeing which comes first (1) 5 of something or (2) at least one of everything.
To do this I just a dynamic program, with the variable being the permutation of what is seen so far. So for example at the start we have '000000', and at the end we either have no zeros (for example '122234'), or at least one 5 (for example '023445').
It is relatively easy to compute probabilities recursively. For example in the case '012234', there are 1+2+2+3+4=12 teams accounted for, which means 30-12=18 teams remaining. So:
with probability (5-0)/18 we move to '112234',
with probability (5-1)/18 we move to '022234',
with probability (5-2)/18 we move to '013234',
with probability (5-2)/18 we move to '012334',
with probability (5-3)/18 we move to '012244',
with probability (5-4)/18 we move to '012235'.
We just recursively add all these up, storing as we go. This runs super fast because there just aren't that many possibilities. 6^6 is only 46656, but even that is an overestimate because we don't need to store cases with no zeros, or cases with any 5's, so in fact we only store 11529 cases.
In python this ran instantly, even with fractions instead of decimals.
Something I realized about the extra credit was that it could be stated equivalently as: You roll a d6 up to 21 times in a row, tallying the results. What is the probability that you will have five of the same number tallied before having all six numbers in the tally?
Here the d6 is equivalent to the number of divisions, and n-of-a-kind comes from divisions of size n. For (6, 5), 20 is the most rolls you can make without meeting one or the other condition (i.e., you can have 5 sets of 4-of-a-kind).
The equivalence comes through another equivalence, which is: you have a bunch of ping-pong balls, and randomly toss them into one of six buckets, each of which can hold five balls. What is the probability you'll fill one bucket before all the buckets have one ball in them? I hope the equivalence to the permutation formulation is clear.
The same goes for the sequence that has the smallest number needed for two formations, followed by the smallest number needed for three formations, followed by the smallest number needed for four formations, and so on
I have found that 8 formations comes before 7 does. So does the first 8 formations count as the 7? If not, does the lower 8 count part of the sequence or does it go up from there?
In my write-up, I assumed that the values for 7 and 8 we equal, hence the sequence was 15, a, b, c, c, d, d, f, g (as the same happened with 5 and 6 in my calculations, which makes me wonder about said calculations.)
I am looking for a little more clarity on "there are three distinct formations between triangle and a rhombus". Is another way of saying this: "Find at least two rhombus that have same rider count as a triangle."?
Does this mean that any three that match count even if all are "rhombus like". That is not how I would have read it. The count of the triangle provides a constraint that I can now remove than.
I read "three distinct formations between triangle and a rhombus" to include the endpoints, given that the first solution (15) includes an endpoint (triangle). So it could well have a rhombus, a triangle, and something in-between, or three in-between formations, etc. @Zach, can you confirm?
Pretty funny Vuelta in the end, very interesting to see how much damage a GC like Remco can do once he's allowed in the breakaways. Very happy for GC Kuss!
It sounds like many folks didn't enjoy it, but I thought that final week of intra-team drama was must-see TV. #GCKUSS
I also got the ~8.6% answer from simulations, but felt it wasn't satisfying enough to submit. Simulations don't really give an *answer*, just an approximation of said answer.
Curious, what was the dynamic programming approach to the Extra Credit?
Here was what solver David Kravitz (mentioned in the write-up) wrote for "Show Your Work":
The solution is equivalent to making a permutation of 30 items 1,1,1,1,1,2,2,2,2,2,....,6,6,6,6,6, noting this is the order in which the teams finished from first to last, then seeing which comes first (1) 5 of something or (2) at least one of everything.
To do this I just a dynamic program, with the variable being the permutation of what is seen so far. So for example at the start we have '000000', and at the end we either have no zeros (for example '122234'), or at least one 5 (for example '023445').
It is relatively easy to compute probabilities recursively. For example in the case '012234', there are 1+2+2+3+4=12 teams accounted for, which means 30-12=18 teams remaining. So:
with probability (5-0)/18 we move to '112234',
with probability (5-1)/18 we move to '022234',
with probability (5-2)/18 we move to '013234',
with probability (5-2)/18 we move to '012334',
with probability (5-3)/18 we move to '012244',
with probability (5-4)/18 we move to '012235'.
We just recursively add all these up, storing as we go. This runs super fast because there just aren't that many possibilities. 6^6 is only 46656, but even that is an overestimate because we don't need to store cases with no zeros, or cases with any 5's, so in fact we only store 11529 cases.
In python this ran instantly, even with fractions instead of decimals.
Something I realized about the extra credit was that it could be stated equivalently as: You roll a d6 up to 21 times in a row, tallying the results. What is the probability that you will have five of the same number tallied before having all six numbers in the tally?
Here the d6 is equivalent to the number of divisions, and n-of-a-kind comes from divisions of size n. For (6, 5), 20 is the most rolls you can make without meeting one or the other condition (i.e., you can have 5 sets of 4-of-a-kind).
The equivalence comes through another equivalence, which is: you have a bunch of ping-pong balls, and randomly toss them into one of six buckets, each of which can hold five balls. What is the probability you'll fill one bucket before all the buckets have one ball in them? I hope the equivalence to the permutation formulation is clear.
Regarding extra credit sequence.
The same goes for the sequence that has the smallest number needed for two formations, followed by the smallest number needed for three formations, followed by the smallest number needed for four formations, and so on
I have found that 8 formations comes before 7 does. So does the first 8 formations count as the 7? If not, does the lower 8 count part of the sequence or does it go up from there?
In my write-up, I assumed that the values for 7 and 8 we equal, hence the sequence was 15, a, b, c, c, d, d, f, g (as the same happened with 5 and 6 in my calculations, which makes me wonder about said calculations.)
I am looking for a little more clarity on "there are three distinct formations between triangle and a rhombus". Is another way of saying this: "Find at least two rhombus that have same rider count as a triangle."?
Not necessarily. Not all of the solutions are triangular numbers.
Does this mean that any three that match count even if all are "rhombus like". That is not how I would have read it. The count of the triangle provides a constraint that I can now remove than.
I read "three distinct formations between triangle and a rhombus" to include the endpoints, given that the first solution (15) includes an endpoint (triangle). So it could well have a rhombus, a triangle, and something in-between, or three in-between formations, etc. @Zach, can you confirm?
Confirmed! Triangles and rhombuses count.
But neither are required? Always having the triangle in the picture and the writeup made me think that a triangle was required.
Also correct. Neither bound is required.