2
$\begingroup$

Other than ordinary farms like Animal Farm, there is a farm called 'Cows Training Farm', which is a farm that trains $15$ very orz cows. Each year, six cows are chosen to join a competition. Mason is now guessing which six cows would enter that competition. If he guesses at least three cows correctly, his guess is said to be accurate. Suppose Mason is smart and has an optimal strategy for guessing. How many times at most would Mason have to guess, such that at least one guess is accurate?

This problem is an unused problem proposed for a relatively unknown small contest, in which I am one of the problem setters and I prefer not to mention that contest here.

Bonus: Try to do this problem when there are more cows. Can you generalize? (I am interested in if there is a good generalization)

This problem is my first problem after one and a half years. Hope you like it!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Do the guesses come all at once, or can a guess depend on the outcomes of previous guesses? $\endgroup$
    – RobPratt
    Commented Oct 23, 2022 at 15:21
  • $\begingroup$ @RobPratt It does not make a difference. Try to see why $\endgroup$
    – Culver Kwan
    Commented Oct 23, 2022 at 22:32
  • $\begingroup$ If the guesses are made simultaneously, it sounds like the covering design number $C(15,6,3)$, which is known to be $30$ or $31$: ljcr.dmgordon.org/cover/show_cover.php?v=15&k=6&t=3 $\endgroup$
    – RobPratt
    Commented Oct 23, 2022 at 23:17
  • $\begingroup$ @RobPratt guessing all at once is same as guessing one by one until you hit a positive result because at the end you are making the exact same guesses. $\endgroup$
    – Manish Kundu
    Commented Oct 24, 2022 at 5:51
  • $\begingroup$ @RobPratt Our target here is a bit bigger, 6 cows instead of 3. So this is a generalised covering or "lotto" number L(15,6,3,6), not a pure covering number. $\endgroup$
    – Parcly Taxel
    Commented Oct 24, 2022 at 7:30

1 Answer 1

Reset to default
1
$\begingroup$

4 guesses

Let's guess $[1, 2, 3, 4, 5, 6]$ in the first guess. If it's accurate, we are done, otherwise there must be between $0$ and $2$ correct cows in this set.

Guess $[7,8,9,10,11,12]$ next. If it's not accurate either then there must be between $0$ and $2$ correct cows here as well, which means out of $[13,14,15]$ atleast $2$ cows must be correct since we have $6$ in total.

Now we guess $[1, 2, 3, 13, 14, 15]$. If we are wrong again, then there must be exactly $2$ correct cows in $[13,14,15]$ and none in $[1,2,3]$.

Next we guess $[4, 5, 6, 13, 14, 15]$. If this guess is not accurate, then that means there are $0$ correct cows in $[1,2,3,4,5,6]$ and $4$ correct cows in $[7,8,9,10,11,12]$. But we already checked the latter and we know there cannot be $4$ cows in that set, so this guess must be an accurate one.

Proof

For the first $2$ guesses it is optimal to use $12$ different cows since if we repeat any of the cows in both the guesses, then that does not give us any additional information about those cows at all. Either way all we know after the first $2$ guesses is a couple of sets that contain between zero and two cows. This is not enough to draw a conclusion in the very next guess so $4$ guesses must be the minimum we need.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You have not proved that you cannot do it using lesser guesses $\endgroup$
    – Culver Kwan
    Commented Oct 23, 2022 at 22:33
  • $\begingroup$ @CulverKwan updated my answer. $\endgroup$
    – Manish Kundu
    Commented Oct 24, 2022 at 5:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.