Expanding and understanding the poison pills riddle

It's not true that you can solve this with $13$ pills; this page explains why.

You can get an upper bound on the number of pills for which this can be solved with $k$ weighings as follows. For $n$ pills, there are $2n$ different results to distinguish ($1$ out of $n$ pills and $1$ out of the $2$ possibilities "lighter" and "heavier"). From each weighing, you get one of $3$ results, so with $k$ weighings you can differentiate $3^k$ outcomes. Thus, if you can find an ideal weighing scheme such that the remaining possible results are distributed as equally as possible among the three outcomes of each weighing, you can solve the problem for $\lfloor3^k/2\rfloor$ pills with $k$ weighings. For $3$ weighings, this yields an upper bound of $13$ pills, so this bound isn't tight, since the problem can in fact only be solved for $12$ pills. For $4$ weighings, this yields $40$ pills, but a moment's reflection shows that this is in fact unsolvable for a similar reason as the $k=3,n=13$ case.

You may also be interested in this: Finding four numbers.

Problems of this kind fall in the category of what's called "combinatorial group testing." The standard reference appears to be Combinatorial Group Testing and Its Applications, by Du and Hwang. In Chapter 16 they discuss your problem. I can't access the entire chapter via Google books, but, for Question 1, there is some mention of information theory. The book gives other references that are probably worth tracking down as well.

With respect to Question 2, the author of this document claims that you can determine which of $n$ pills is the fake one in $k$ weighings if and only if $n \leq (3^k-1)/2$, $n \neq 2$. (Added: The OEIS entry for these numbers confirms this.) For 4 weighings, that would give a maximum of 40 pills. He also claims to have solved several variants of this problem, in which you (1) know or don't know whether there actually is a poisoned pill, (2) know or don't know if a fake pill is heavier or lighter than a genuine one, (3) have 0, 1, or infinitely many additional pills that you know are genuine, (4) do or don't have to identify whether the pill is heavier or lighter, and (5) must plan all the weighings in advance or not.

For a slight variation on Question 3, Du and Hwang give the following results for the case in which you know that the fake pills are lighter. If there are $d$ fake pills, $n$ total pills, and $g(d,n)$ is the minimum number of weighings required to identify the $d$ fake ones, then $$g(2,n) = \left\lceil \log_3 \binom{n}{2} \right\rceil,$$ $$\left\lceil \log_3 \binom{n}{3} \right\rceil \leq g(3,n) \leq \left\lceil \log_3 \binom{n}{3} \right\rceil+2,$$ $$\left\lceil \log_3 \binom{n}{d} \right\rceil \leq g(d,n) \leq \left\lceil \log_3 \binom{n}{d} \right\rceil+ 15d.$$

They say that the proof for the $g(2,n)$ result is a very complicated case-by-case argument. Your Question 3 is somewhat more difficult than this, and there may not be any known results. They may give some more results on the variation you specifically ask for, though; I would track down a hard copy of the book.

The arguments from information theory and coding theory give strong bounds, often within a small additive constant (independent of the $n$ = the number of coins/pills/objects) of the answer, but are not optimal in general. To determine the minimum number of weighings, or the maximum number of coins, can require an extremely complicated analysis that is sensitive to the details of the problem, including: the number of false objects, dynamic or pre-specified weighings, whether light or heavy state of the false objects is to be determined or only their identity, and whether an adversary can introduce errors.