I asked this question on MathOverflow and got a great answer there.
For $k = 2$ I can do it with ${\lceil \log_2 N \rceil + 2 \choose 2} - 1$ servants. In particular for $N = 1000$ I can do it with $65$ servants. The proof is somewhat long, so I don't want to post it until I've thought about the problem more.
I haven't been able to improve on the above result. Here's how it works. Let $n = \lceil \log_2 N \rceil$. Let me go through the algorithm for $k = 1$ so we're all on the same page. Number the wines and assign each of them the binary expansion of their number, which consists of $n$ bits. Find $n$ servants, and have servant $i$ drink all the wines whose $i^{th}$ bit is $1$. Then the set of servants that die tells you the binary expansion of the poisoned wine.
For $k = 2$ we need to find $n$ butlers, $n$ maids, and ${n \choose 2}$ cooks. The cooks will be named $(i, j)$ for some positive integers $1 \le i < j \le n$. Have butler $i$ drink all the wines whose $i^{th}$ bit is $1$, have maid $i$ drink all the wines whose $i^{th}$ bit is $0$, and have cook $(i, j)$ drink all the wines such that the sum of the $i^{th}$ bit through the $j^{th}$ bit, inclusive, mod 2, is $1$. This is how the casework breaks down for butlers and maids.
- If both butler $i$ and maid $i$ die, then one of the poisoned wines has $i^{th}$ bit $0$ and the other has $i^{th}$ bit $1$.
- If only butler $i$ dies, then both of the poisoned wines have $i^{th}$ bit $1$.
- If only maid $i$ dies, then both of the poisoned wines have $i^{th}$ bit $0$.
The second two cases are great. The problem with case 1 is that if it occurs more than once, there's still ambiguity about which wine has which bit. (The worst scenario is if all the butlers and maids die.) To fix the issue with case 1, we use the cooks.
Let $i_1 < ... < i_m$ be the set of bits where case 1 occurs. We'll say that the poisoned wine whose $(i_1)^{th}$ bit is $1$ is wine A, and the other one is wine B. Notice that the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine A mod 2 is the same as the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine B mod 2, and we can determine what this sum is by looking at whether cook $(i_1, i_2)$ died. The value of this sum determines whether the $(i_2)^{th}$ bit of wine A is 1 or 0 (and the same for wine B). Similarly, looking at whether cook $(i_j, i_{j+1})$ died tells us the remaining bits of wine A, hence of wine B.
One last comment for now. The lower bound is not best possible when $k$ is large compared to $N$; for example, when $k = N-1$ it takes $N-1$ servants. The reason is that any servant who drinks more than one wine automatically dies, hence gives you no information.
I completely agree with Henning Makholm: the important difference between this problem and the classic Monty Hall problem is not whether the apples are chosen by the players or assigned to them — in fact, that makes absolutely no difference, since they have no information to base any meaningful choice on at the point where the apples are given to them.
Rather, the key difference is that, in the classic Monty Hall problem, the player knows that Monty will never open the door they choose. Similarly, if one of the players in this problem knew that they wouldn't be asked to bite into the first apple, they'd be better off switching apples with the other remaining player. But of course, if the apples are assigned randomly, it's impossible for more than one of the players to (correctly) possess such knowledge: if two of the players knew they'd never be chosen to go first, and the third one got the wormless apple, Monty would have no way to pick a player with a wormy apple to go first.
Anyway, you don't really have to believe my reasoning above; as with the classic Monty Hall problem, we can simply enumerate the possible outcomes.
Of course, I'm making here a few assumptions which weren't quite explicitly stated by the OP, but which seem like reasonable interpretations of the problem statement and match the classic Monty Hall problem:
- Each of the players is equally likely to get the wormless apple.
- Monty will always choose a player with a wormy apple to go first.
- Of the two players with wormy apples, both are equally likely to be chosen to go first.
- All the players know all of the above things in advance.
Given these assumptions, there are six possible situations the might occur, with equal probability, at the point where the two remaining players are asked to switch:
- $A$ has the wormless apple, $B$ went first $\to$ $A$ and $C$ remain.
- $A$ has the wormless apple, $C$ went first $\to$ $A$ and $B$ remain.
- $B$ has the wormless apple, $C$ went first $\to$ $B$ and $A$ remain.
- $B$ has the wormless apple, $A$ went first $\to$ $B$ and $C$ remain.
- $C$ has the wormless apple, $A$ went first $\to$ $C$ and $B$ remain.
- $C$ has the wormless apple, $B$ went first $\to$ $C$ and $A$ remain.
From the list above, you can easily count that, for each player, there are four scenarios where they remain, and in two of those they have the wormless apple. So it makes no difference whether they switch or not.
But what if one player, say $A$, knew that they'd never be chosen to go first? Then, if $B$ or $C$ got the wormless apple, Monty would have to choose the other one of them to go first. Thus, scenarios 4 and 5 above become impossible, while 3 and 6 become twice as likely. Thus, if, say, $A$ and $B$ remain, they know that they have to be in scenarios 2 or 3 — and of those, the one in which $B$ has the wormless apple (3) is now twice as likely as the one in which $A$ has it (2), so $A$ should want to switch but $B$ should not.
Best Answer
Let's represent your starting location as $0$ and the destination as $1000$.
Let $f(x)$ be the greatest amount of fuel that can possibly be transported to or past $x$ miles from the starting point. For example, if you pick up $1000$ gallons, drive to $1$ (one mile), drop off $998$ gallons, drive back, repeat the trip to $1$ and back, and on the third trip out you drive to $100$ where you drop $801$ gallons of fuel, then you will have transported $2995$ gallons to point $1$: the $1996$ gallons you cached there and the $999$ gallons that were in the jeep when you passed $1$ on the third trip from $0$.
You should be able to show that for $0 \leq x \leq 200$, $f(x) = 3000 - 5x$. The intuitive reason is that you will either have to pass every point between $0$ and $200$ five times (three times outbound and twice in the return direction) have to abandon some fuel without using it; and the latter strategy will deliver less fuel to points beyond where you abandoned the fuel.
The previous example that transported $2995$ gallons to or past point $1$ was therefore optimal, or at least was optimal up to $1$.
It follows that only $2000$ gallons can reach $200$ no matter where you leave your caches along the way.
You should then be able to show that for $0 \leq y \leq \frac{1000}{3}$, $f(200 + y) = 2000 - 3y$. Moreover, you achieve this by delivering exactly $2000$ gallons of fuel to $200$, including the fuel in the jeep the last time you arrive at $200$ in the forward direction, then making sure you have $1000$ gallons in the jeep each time you drive forward from $200$.
Finally, for $0 \leq z \leq 1000$, $f\left(200 + \frac{1000}{3} + z\right) = 1000 - z$. You achieve this by delivering exactly $1000$ gallons of fuel to $200 + \frac{1000}{3}$ and then fully loading the jeep with any fuel you have cached at that point and making just one trip forward.
The answer is $f(1000)$.