a) Divide these coins into 3 groups, each group has 3 coins. Then weighing 2 random groups. If they are balance, the fake coin is in the last group, if not, The fake coins is in the lighter group. Then take 2 random coins from this group. If they are balance, the fake coin is the last coin of that group. If not, the fake coin is the lighter one!

In order to solve (b) I think one requires usage of Linear Algebra. I am surprised that they would ask such a problem as P1.

Let $S$ be a set of $N$ coins. We claim that the smallest number of weighings needed to find the fake coin in $S$ is $\lceil \log_3 N \rceil$. Let us first consider the case when $|S| = 3^n$, where $n \in \mathbb{N}$. We can split $S$ into three sets $S_1, S_2, S_3$, where each has $3^{n-1}$ coins. If we compare the weights of $S_1$ and $S_2$ and both are the same, then $S_3$ has the counterfeit coin. Otherwise, one of $S_1$ or $S_2$ has the counterfeit coin. Nonetheless, we've narrowed down our search to one set with $3^{n-1}$ coins. Then, we continue this procedure until we are left with $3^0 = 1$ coin, which will be the counterfeit count. Thus, a total of $n$ weighings will have been conducted. Now, suppose we have $3^{n-1} < |S| < 3^n$. We may split $S$ into $3$ sets, $S_1,S_2,$ and $S_3$, such that each set has at most $3^{n-1}$ coins and $|S_1| = |S_2|$. We can then compare the weights of $S_1$ and $S_2$ to isolate one of the three sets to inspect further as done previously. We then repeat this process until we have one more coin left, resulting in a total of $n$ weighings. We have now determined that for a set of $3^{n-1} < |S| \leq 3^n$ coins, we are able to find the fake coin in $n$ steps. Thus, we can find the fake coin in $\lceil \log_3 |S| \rceil = \lceil \log_3 N \rceil$ weighings.

Green4Applez wrote: Let $S$ be a set of $N$ coins. We claim that the smallest number of weighings needed to find the fake coin in $S$ is $\lceil \log_3 N \rceil$. Let us first consider the case when $|S| = 3^n$, where $n \in \mathbb{N}$. We can split $S$ into three sets $S_1, S_2, S_3$, where each has $3^{n-1}$ coins. If we compare the weights of $S_1$ and $S_2$ and both are the same, then $S_3$ has the counterfeit coin. Otherwise, one of $S_1$ or $S_2$ has the counterfeit coin. Nonetheless, we've narrowed down our search to one set with $3^{n-1}$ coins. Then, we continue this procedure until we are left with $3^0 = 1$ coin, which will be the counterfeit count. Thus, a total of $n$ weighings will have been conducted. Now, suppose we have $3^{n-1} < |S| < 3^n$. We may split $S$ into $3$ sets, $S_1,S_2,$ and $S_3$, such that each set has at most $3^{n-1}$ coins and $|S_1| = |S_2|$. We can then compare the weights of $S_1$ and $S_2$ to isolate one of the three sets to inspect further as done previously. We then repeat this process until we have one more coin left, resulting in a total of $n$ weighings. We have now determined that for a set of $3^{n-1} < |S| \leq 3^n$ coins, we are able to find the fake coin in $n$ steps. Thus, we can find the fake coin in $\lceil \log_3 |S| \rceil = \lceil \log_3 N \rceil$ weighings. That's all fine and well. But you've missed a small detail (actually come to think of it, it is rather large) . While you have shown that we can determine the faulty coin in $\lceil \log_3n \rceil$ weighings, how do you show that at least these many are required? For example why can I not come up with a strategy that finishes in less than $\lceil \log_3n \rceil$ moves? At this point, to me there seem to be two ways. Introduce a new player as the weighing machine and make him adapt the hidden coint to keep it a secret for as long as possible; or use LA to show that a certain system cannot give a unique solution.