**7/15 Plat Solution**

Call a cow a *decisionmaker* if it will, at some point, propose a distribution, assuming all higher-numbered cows are slaughtered.  (This is also just the set of cows congruent to N modulo K.)

**Lemma 1.**  Any decisionmaker X will give haybales to no more than max(ceil(X/2) - K, 0) cows, other than herself.

Proof: Any cow that is about to be slaughtered will vote for any plan, so cow X automatically has K votes in favor of her plan.  She needs ceil(X/2) votes in total, so that means she needs to buy max(ceil(X/2) - K, 0) votes to pass her proposal.  Obviously, there is no point in giving haybales to a cow who won't vote for the current proposal anyway, so cow X will give haybales to at most max(ceil(X/2) - K, 0) other cows, as desired.

**Lemma 2.**  Any decisionmaker X with X <= 2M+2K can propose a plan that will result in her own survival.

Proof: By induction.  First, suppose X <= 2K.  Then, X can give all haybales to herself, and min(X, K) cows will approve her plan to avoid being slaughtered.  This is enough to pass the vote.

Now, assume cow X-K can propose a successful plan.  Cow X should give 1 haybale to each of ceil(X/2) - K cows who do not receive a haybale in cow X-K's plan and can keep the remaining haybales for herself.  Then, cows X through X-K+1 will approve the plan to avoid being slaughtered, and the remaining ceil(X/2) - K cows will approve the plan in order to receive one haybale rather than 0.  This gives her a total of ceil(X/2) votes, which is enough to approve the plan.

We now need to prove that this plan is actually possible.  By our bound on X, we know ceil(X/2) - K <= M, since X - 2K <= 2M, and dividing by two gives X/2 - K <= M.  (Taking the ceiling is safe because K and M are integers.)

Then, we must show that there will actually be enough cows that receive no haybales from cow X-K.  Note that cow X-K, by Lemma 1, gives haybales to at most ceil((X-K)/2) - K + 1 cows, including herself.  (The case in which ceil((X-K)/2) - K < 0 is easy.)  Thus, there will be at least X - K - (ceil((X-K)/2) - K + 1) = X - ceil((X-K)/2) - 1 cows left.  Then, we want to prove that the difference between this and ceil(X/2) - K is nonnegative.  Subtracting this quantity, using the fact that ceil((X-K)/2) >= ceil(X/2) - floor(K/2), we have that X - ceil((X-K)/2) - 1 - (ceil(X/2) - K) >= X + K - floor(K/2) - 1.  Since K > 0, K - floor(K/2) - 1 >= 0, so this quantity is at least X, and since X is positive, this whole expression is positive.  Thus, there will be enough cows left over for this plan to be proposed, proving the lemma.

If N <= 2M+2K, then we know the correct decisionmaker X.  Otherwise, we must consider the possibility that some greater decisionmaker may exist.

**Lemma 3.**  Let X be some decisionmaker with X > 2M+K capable of passing a proposal.  The next decisionmaker who will be able to pass a proposal will be the first decisionmaker Y with Y >= 2X - 2M.

Proof: Consider the votes Y receives.  Cow Y can receive votes from cows X+1 through Y (as those cows will be slaughtered otherwise, by our assumption that the next decisionmaker who can pass a proposal is X), and from at most M remaining cows (as no cow <= X will vote for this proposal without receiving haybales--they all survive when proposal X passes and prefer to see cow Y slaughtered).  Thus, cow Y will receive at most Y - X + M votes, so we must have 2Y - 2X + 2M >= Y, so Y >= 2X-2M, as desired.

Now, we prove that the first such cow will be a valid decisionmaker.  As before, cow Y receives votes from Y-X cows who can only avoid the slaughterhouse by supporting cow Y's plan.  Then, note that Y-X >= X-2M >= K, where the X > 2M+K inequality is applied in the last step.  Thus, cow Y has at least K guaranteed supporters, and by the same logic used under Lemma 2, there will be at least ceil(Y/2) - (Y-X) cows that receive no haybales from cow X.

Hence, the next decisionmaker will exactly be the first Y with Y >= 2X-2M and Y = N modulo K, as desired.

**Lemma 4.** There are at most O(log N) decisionmakers X with 2M+K < X <= N.

Proof: By Lemma 3, the next capable decisionmaker Y after any decisionmaker X has Y >= 2X-2M, so Y-2M >= 2X-4M, so Y-2M >= 2(X-2M).  Thus, the difference between X and 2M doubles each time we replace X with the next decisionmaker.  Since this difference must be at most N, we have O(log N) such decisionmakers, as desired.

Therefore, we can apply Lemma 3 to find the next decisionmaker capable of passing a proposal O(log N) times until we run out of decisionmakers less than N.  This determines the cow who will be the first possible decisionmaker, and thus the cow whose proposal is actually passed.

Let X be the cow whose proposal is passed.  Let Y be the cow who would be the next successful decisionmaker, if cow X were hypothetically slaughtered, or 0 if no such decisionmaker exists.  Then, by similar logic to Lemma 3, X can pass a proposal consisting of giving one haybale to max(ceil(X/2) - (X-Y), 0) cows who would not receive a haybale from cow Y.  This leaves M - max(ceil(X/2) - (X-Y), 0) haybales for cow X.