This problem seems to be a little confuse, but i think that we must find all $N$ such that, for any wheights of the $N-1$ genuine coins, and for any wheight of the fake coin, one can find the fake coin, and whether it is lighter or heavier than a genuine coin. First, it's easy to see that $N=2,3$ are not solutions, because you can't say which coin is false, for $N=2$, and when you can say which coin is false for $N=3$, you find out that the two other coins are genuine, and then you can't use then to determine if the fake coin is lighter or heavier. Now, we'll prove that for $N=2n+1$, with $n$ a positive integer, it's impossible to find the fake coin and its wheight compared with the other coins. We'll prove this by induction on $n$. The initial case $n=1$ is already solved. Now, suppose that we have $2n+1$ coins, and the weights are distributed in such a way that when we put $a$ coins in a fan of the balance and $b$ coins in the another, with $a>b$, then the fan with $a$ coins will go down. So, with this configuration of wheights, the only useful move is to put a equal number of coins in each fan. Now, suppose that we put $c<n$ coins in each fan, and suppose that we got equilibrium. Then, all of the $2c$ coins on the balance are genuine, and now we must operate with $2(n-c)+1$ coins in order to discover what we want about the fake coin, but it is impossible by hypothesis. So, we must put first $n$ coins on each fan. If we get the equilibrium, then the only coin outside the balance is the fake coin. However, we can't determine if it is heavier or lighter, because all the $2n$ genuine coins are gone. Thus, we proved that for all $N$ odd it may be impossible to achieve the goal. Next, we'll prove that for every $N=2n+2$, $n$ positive integer, is solution, by induction on $n$. The first case ($N=4$) is proved as follows: Let $a,b,c,d$ be the four coins. Put $a,b$ in the first fan, and $c,d$ on the second. The balance'll be cleary unbalanced. Suppose that the fan with $a,b$ went up. Now, we remove all the coins and we put $a$ on a fan and $b$ on another. If the balance is unbalanced, then the false coin is $a$ or $b$, which impies that the fake coin is ligther, since the fan with $a,b$ went up on the fist wheight. On the second wheight, if $a$ went up, the $a$ is the fake coin, and it is lighter than the others. Now, suppose that the wheight of $a$ equals to $b$. Then, $a$ and $b$ are genuine coins (so we can't use then anymore), and the fake coin is $c$ or $d$, and it is heavier, because the fan with $c,d$ went down on the first wheight. Now, put $c$ on a fan and $d$ on another, and suppose that $c$ went down. Then, $c$ is the fake coin, and it is heavier than the others. It solves the case $n=1$. Now, suppose that we have $2n+2$ coins $a_1, a_2, \dots a_{2n+2}$. Put $a_1, \dots a_{n+1}$ on a fan and $a_{n+2}, \dots a_{2n+2}$ on another. Clearly, the balance'll be unbalanced, and we'll suppose that the fan with $a_{n+2}, \dots a_{2n+2}$ went up. Now, compare $a_{2n+1}$ and $a_{2n+2}$. If their weights are equal, they're genuine, and then we can operate only with $a_1, a_2, \dots a_{2n}$, and we can find the fake coin by hypothesis. If, however, $a_{2n+1}$ and $a_{2n+2}$ have different wheights (let us suppose without loss of generality a_{2n+1} lighter), then we conclude that the fake coin is on $a_{n+2}, \dots a_{2n+2}$, and so it is lighter, since the corresponding fan went up. Then, a_{2n+1} is the fake coin and it is lighter the the other. So, by induction, we proved that for all $N$ even, $N>2$, one can always achieve the goal. Finnaly, the answer is $N=2n+2$, $n \in \mathbb{N}$.

To make things easier, let's rephrase the problem. Alice tries to determine the fake coin and whether it's lighter or heavier, and Bob tries to prevent so. Alice puts the coins, and Bob will determine which side (if any) is heavier. Thus the goal is achievable if Alice wins, and not if Bob wins. First, clearly weighing different number of coins between both pans won't help. In particular, Bob will just call the pan with more coins as heavier; this won't give any information. Therefore all subsequent "weighings" refer to weighings of the same number of coins. Odd $N$ loses. Bob simply declares all weighings to be balanced, thus removing all of the weighed coins from play (since two balanced pans must have genuine coins on both; there aren't enough fake coins to cause otherwise). At the end, Alice is left with one coin that must be fake, but since she doesn't know whether it's heavier or lighter, she loses. $N = 2$ also clearly loses; Alice's only possible weighing is 1 versus 1, and she will never know whether the fake coin is the heavier one or the lighter one. Even $N \ge 4$ wins. Alice divides the coins in half and compares one against the other. Bob is forced to tell that one side is heavier. Now weigh one heavy coin against another heavy coin. If Bob ever tells one of them to be heavier than the other, then Alice wins since she immediately knows which one is the fake coin (the heavier one). If not, Alice keeps doing this until all except probably one heavy coin are out. Do similarly with the lighter coins, but now leave two or three lighter coins instead. If $N \equiv 0 \pmod 4$, we will be left with two lighter coins; just compare them and find the fake coin (the lighter one). If $N \equiv 2 \pmod 4$, we will be left with one heavier coin $A$ and three lighter coins $X,Y,Z$. Compare $XY$ against $AZ$. If $XY$ is heavier, then $Z$ is the fake coin (which is lighter); if $AZ$ is heavier, now compare $X$ against $Y$ and the outcome decides the fake coin (the lighter one if different, or $A$ being heavier if equal). So all even $N \ge 4$ allows the goal to be achieved. EDIT: Sniped

So, it is easy to see that N=2 and N=3 don't work. Now, let N be the smallest odd number for wich we can determine the fake coin (and if it's lighter or heavier). If the fake is lighter than two genuine, there is no point to weight two different amounts of coins in each plate, because the one with more coins will always be heavier. So we will weight an even total amount of coins in the first measuring. It is possible that the two plates are balanced, wich means that the coins used are all genuine and can no longer be used. We now have smaller odd number of coins, and it will be possible to determine the fake coin -> contradiction with N being the smallest odd number possible. So odd numbers don't work. Now let N=0 mod 4. We put half the coins in each plate. One will be lighter, and one will be heavier. We now compare two that were in the same plate over and over until we get two coins with different weights. If they were in the heavier plate, the heavier of the two will be the fake; if they were in the lighter plate, the lighter of the two will be the fake.

Now, let N=2 mod 4. We put half the coins in each plate. One will be heavier and one will be lighter. We now compare two coins at the time that were in the lighter plate. If at one time, one is lighter than the other, it will be a fake. If not, it will remain 1 coin from the lighter plate and all from the heavier. We put the one from the lighter (A) plate and one from the heavier (B) in the same plate, and compare them with two from the heavier (C, D). If they balance, we just procede like we would in case N=0 mod 4, by comparing two at the time. If AB is heavier, it is easy to see that B is fake and heavier. If AB is lighter, or A is fake and lighter, or C is fake and heavier, or D is fake and heavier. We put B to the side and compare C and D. If they balance, A is fake (and lighter). If they don't, the heavier is fake (and heavier). So it works for and only for N even and different than 2.

Apologies for reviving, but isn't $N=4k+1$ possible for all $k\in \mathbb{Z^+}$? If we place $2k$ coins in one side and $2k$ on the other, we either have that they balance, of which means that they are all genuine and so we throw them out to have $1$ coin left, and if they don't balance then the $1$ coin remaining is real and so we throw that coin out. We then have the $N=4k$ scenario which is quite easy to prove right because we can split them into $k$ groups of $4$, and weigh each pair one by one and subsequently throw then out to eventually obtain either $2$ piles of $4$ with one of them containing the fake coin, or one pile with the fake coin. In either case we can pair them off to distinguish the weight of the fake coin and isolate it. Am I missing something?

You need to determine whether the fake coin is heavier or lighter. If the two pans balance, you're left with the single fake coin, but you don't know whether it's heavier or lighter.

Am I misunderstanding the wording of the problem? Cuz for odd numbers, $N=2^kx+1,$ where $x$ is odd. I randomly separated the $N$ coins into $2^k$ piles, all of which have $x$ coins except the last pile (order is only a formality here), which has $x+1$. For$ x=1$: If $ k=1$ then it was shown that solving the problem is impossible. For $k \ge 2,$ we may resolve it in a manner similar to the one below. $x \ge 3$ I will now apply the sorting procedure on each of the piles. Assume the fake coin is in the last pile. I will apply the operation of sorting on each pile until I am left with either 1 coin in the first $x-1$ piles. In the last pile, I begin by randomly choosing two and sorting them, if I encounter two that are equal, as per the rule, I discard them. If I encounter 2 that are different, this means I have come across the fake coin and a genuine coin. I sort out the rest and discard them, only left with my fake coin and one genuine coin in the last pile. Now since I do not know for certain which is genuine and which is fake, I did not discard these. I pick one randomly from these two and compare it with the coin from the first pile. Had I picked the genuine coin, they will be equal, and I would have determined which is the fake coin. I then weigh the fake coin with a genuine coin and determine which is heavier. The case for the fake coin not being in the last pile can be resolved similarly. Either way, can anyone point out which part did I misunderstand lol?

Try this way: If n=2k.Divide all the coins into two parts,equal in number. Then there must be an obvious difference. Record the result. Choose one side,and take two coins off,and add one coin from another side to this side. Then If the difference disappears,there must be a fake coin in the two coins. According to that"obvious difference" ,the weight of the fake coin can be known. If the difference exchanges,the added coin must be fake. According to that"obvious difference", ,the weight of the fake coin can be known. If the difference remains,repeat the process. The most extreme condition will be:two coins on one side,two on the other side. Give both sides a compare,and it's easy to know. If n=2k+1,no matter how you divide the coins,there must be a third part,whose number is 2m+1 Consider the most extreme condition:the fake coin is in the thrid part forever,and at last you have no other coins to use(the most extreme) The condition could exist,so you can't identify it for sure. What's more,it's obviously impossible to identify the two coins if there are only two. So it's n=2k n>2.

Yeah but I mean where is the flaw in my argument? I'm sure im missing sth tho

achen29 wrote: Am I misunderstanding the wording of the problem? Cuz for odd numbers, $N=2^kx+1,$ where $x$ is odd. I randomly separated the $N$ coins into $2^k$ piles, all of which have $x$ coins except the last pile (order is only a formality here), which has $x+1$. For$ x=1$: If $ k=1$ then it was shown that solving the problem is impossible. For $k \ge 2,$ we may resolve it in a manner similar to the one below. $x \ge 3$ I will now apply the sorting procedure on each of the piles. Assume the fake coin is in the last pile. I will apply the operation of sorting on each pile until I am left with either 1 coin in the first $x-1$ piles. In the last pile, I begin by randomly choosing two and sorting them, if I encounter two that are equal, as per the rule, I discard them. If I encounter 2 that are different, this means I have come across the fake coin and a genuine coin. I sort out the rest and discard them, only left with my fake coin and one genuine coin in the last pile. Now since I do not know for certain which is genuine and which is fake, I did not discard these. I pick one randomly from these two and compare it with the coin from the first pile. Had I picked the genuine coin, they will be equal, and I would have determined which is the fake coin. I then weigh the fake coin with a genuine coin and determine which is heavier. The case for the fake coin not being in the last pile can be resolved similarly. Either way, can anyone point out which part did I misunderstand lol? Could you think in this way:once you have a difference betwween just two coins,you immediately know the rest are true and abondon them.

Maybe I shall say:a difference between just two coins means a shut down on all the process,for you immediately know the rest and abondon them.

Davi Medeiros wrote: This problem seems to be a little confuse, but i think that we must find all $N$ such that, for any wheights of the $N-1$ genuine coins, and for any wheight of the fake coin, one can find the fake coin, and whether it is lighter or heavier than a genuine coin. First, it's easy to see that $N=2,3$ are not solutions, because you can't say which coin is false, for $N=2$, and when you can say which coin is false for $N=3$, you find out that the two other coins are genuine, and then you can't use then to determine if the fake coin is lighter or heavier. Now, we'll prove that for $N=2n+1$, with $n$ a positive integer, it's impossible to find the fake coin and its wheight compared with the other coins. We'll prove this by induction on $n$. The initial case $n=1$ is already solved. Now, suppose that we have $2n+1$ coins, and the weights are distributed in such a way that when we put $a$ coins in a fan of the balance and $b$ coins in the another, with $a>b$, then the fan with $a$ coins will go down. So, with this configuration of wheights, the only useful move is to put a equal number of coins in each fan. Now, suppose that we put $c<n$ coins in each fan, and suppose that we got equilibrium. Then, all of the $2c$ coins on the balance are genuine, and now we must operate with $2(n-c)+1$ coins in order to discover what we want about the fake coin, but it is impossible by hypothesis. So, we must put first $n$ coins on each fan. If we get the equilibrium, then the only coin outside the balance is the fake coin. However, we can't determine if it is heavier or lighter, because all the $2n$ genuine coins are gone. Thus, we proved that for all $N$ odd it may be impossible to achieve the goal. Next, we'll prove that for every $N=2n+2$, $n$ positive integer, is solution, by induction on $n$. The first case ($N=4$) is proved as follows: Let $a,b,c,d$ be the four coins. Put $a,b$ in the first fan, and $c,d$ on the second. The balance'll be cleary unbalanced. Suppose that the fan with $a,b$ went up. Now, we remove all the coins and we put $a$ on a fan and $b$ on another. If the balance is unbalanced, then the false coin is $a$ or $b$, which impies that the fake coin is ligther, since the fan with $a,b$ went up on the fist wheight. On the second wheight, if $a$ went up, the $a$ is the fake coin, and it is lighter than the others. Now, suppose that the wheight of $a$ equals to $b$. Then, $a$ and $b$ are genuine coins (so we can't use then anymore), and the fake coin is $c$ or $d$, and it is heavier, because the fan with $c,d$ went down on the first wheight. Now, put $c$ on a fan and $d$ on another, and suppose that $c$ went down. Then, $c$ is the fake coin, and it is heavier than the others. It solves the case $n=1$. Now, suppose that we have $2n+2$ coins $a_1, a_2, \dots a_{2n+2}$. Put $a_1, \dots a_{n+1}$ on a fan and $a_{n+2}, \dots a_{2n+2}$ on another. Clearly, the balance'll be unbalanced, and we'll suppose that the fan with $a_{n+2}, \dots a_{2n+2}$ went up. Now, compare $a_{2n+1}$ and $a_{2n+2}$. If their weights are equal, they're genuine, and then we can operate only with $a_1, a_2, \dots a_{2n}$, and we can find the fake coin by hypothesis. If, however, $a_{2n+1}$ and $a_{2n+2}$ have different wheights (let us suppose without loss of generality a_{2n+1} lighter), then we conclude that the fake coin is on $a_{n+2}, \dots a_{2n+2}$, and so it is lighter, since the corresponding fan went up. Then, a_{2n+1} is the fake coin and it is lighter the the other. So, by induction, we proved that for all $N$ even, $N>2$, one can always achieve the goal. Finnaly, the answer is $N=2n+2$, $n \in \mathbb{N}$. May I come up with an extreme condition: The number of the coins on each pan is 2k+1,and you compared all the first 2k coins only to find ,then what will you do? You will constantly compare the coin only from the other pan,for you won't know the weight of the fake coin if you compare the coin left with coin from the other pan when resulting in inequilibrium. And,if the condition is the same with before?You know the fake coin is between the two left,but no other information.

Karsa wrote: Could you think in this way:once you have a difference betwween just two coins,you immediately know the rest are true and abondon them. Oh indeed makes sense. Missed this part. Thanks!