Proof of optimality
Many posts here give an answer - but none of them (as far as I know) try to prove the optimality of the approach. Here I attempt to do so:\n\nFirst, let\'s flip
Many posts here give an answer - but none of them (as far as I know) try to prove the optimality of the approach. Here I attempt to do so:\n\nFirst, let\'s flip the problem and try to solve the following problem instead.\n\nGiven $ p $ pigs and $ t $ rounds (i.e.) $ t = \\left\\lfloor \\frac{\\text{minuteToTest}}{\\text{minuteToDie}} \\right\\rfloor $, what is the maximum number of buckets they can handle?\n\nNaturally, in the first round, one would use all $ p $ pigs, therefore we could have $ 2^p $ possible results. Sadly, some pig will die, and then we proceed to the next step. \n\nIn order to find the maximum number of pigs we can handle, let\'s consider a concrete case. Let\'s say we have 3 pigs, and we have 2 steps. We draw the typical Venn\'s diagram with 3 sets and therefore 8 regions (i.e. including the complement of the union). Now each set is the set of buckets a pig drinks, and therefore, in each of these region, we can put buckets into it. We wanted to put as many as possible.\n\nHow? Note that in each region, we know exactly how many pigs survived, and they have exactly $ t - 1 $ steps remaining. Exactly which bucket to put there is irrelevant, all we need to know is how many is there, so we can write down the recurrence as follows. Let $ m_{pt} $ to be the maximum number of buckets $ p $ pigs can handle with $ t $ steps. we have:\n\n$ m_{pt} = \\sum\\limits_{i=0}^p {_pC_i m_{i(t-1)}} $\n\nWe have the obvious base cases - if you have no pigs, no matter how much time step you have, you can only handle 1 bucket (which is obviously poisonous)\n\nCompare this with the standard binomial expansion.\n\n$ (1+t)^p = \\sum\\limits_{i=0}^p {_pC_i t^i} $\n\nWe see that $ m_{pt}  = (1+t)^p $, the fact that we have a unique solution is obvious, so any solution is **the** solution.\n\nThat is why the **optimal** solution is $ \\left\\lceil\\frac{\\log \\text{buckets}}{\\log (1 + t)}\\right\\rceil $.\n\nFrom a result perspective, this is nothing new. I just filled the gap that none of the proof I have seen here shows the reason why their solution is in fact optimal. The T ary number combinatorial interpretation is cool and all, but isn\'t obvious why it is optimal. Many other answers forget pig dies and therefore you aren\'t actually getting all the bits at all rounds.\n\nWould love to see if someone can come up with an information theoretic based argument.
['Python']