I have a number theory question that I think I'm supposed to apply the pigeonhole principle to. I've figured out the correct answer just with logic, but I feel like there is a more formal way to do it that I can actually show my work for.
Ten inhabitants of an island populated by knights, who never lie, and knaves, who always lie, were given ten different numbers between 1 and 10.
- When asked "Is your number divisible by 2?" 3 people said yes
- When asked "Is your number divisible by 4?" 6 people replied yes
- When asked "Is your number divisible by 5?" 2 people replied yes
How many of the ten are knaves and which numbers were given to them?
EDIT: My solution:
The incorrect numbers of people with the numbers in statements 1 and 2 imply that there are some amount of knaves. Looking at statement 3, the only way 2 people replied yes is if there are no knaves, 2 knaves, or 4 knaves. Statment 2 implies that there must be, at fewest, 4 knaves (as if the knights had both 4 and 8). Therefore, there are 4 knaves total. Statement 2 shows us that, because there are 4 knaves, they must not have 4 and 8 and we know two knaves have 5 and 10 from statement 3. This means that, for statement 1 to be true, the other two knaves must have even numbers, 2 and 6 in this case. Therefore, we know that there are 4 knaves with 2, 5, 6, and 10 and 6 knights with 1, 3, 4, 7, 8, and 9.
Less elegant, but more formal, alternative approach:
Let $~A,B,~$ and $~C~$ denote the sets $~\{2,4,6,8,10\}, ~\{4,8\},~$ and $~\{5,10\},~$ respectively.
Let $~L~$ denote the number of liars.
For $~k \in ~\{A,B,C\}~$ let $~T_k,~L_k~$ denote the number of truth-tellers and liars assigned to set $~k,~$ respectively.
Note that someone will answer yes to a divisibility question if and only if either :
So, from the data:
$T_A + F_A = 5, ~T_A + (L - F_A) = 3 \implies $
$T_A = 4 - (L/2), ~F_A = 1 + (L/2).$
$T_B + F_B = 2, ~T_B + (L - F_B) = 6 \implies $
$T_B = 4 - (L/2), ~F_B = -2 + (L/2).$
$T_C + F_C = 2, ~T_B + (L - F_C) = 2 \implies $
$T_C = 2 - (L/2), ~F_C = (L/2).$
At this point, there are three possibilities, for the value of $T_B$:
$T_B = 0 \implies L = 8.$
$T_B = 1 \implies L = 6.$
$T_B = 2 \implies L = 4.$
The first two possibilities above can be ruled out, because they would each cause more than $2$ Liars to not be assigned to set $C$. This would yield a contradiction, because only $2$ people said $\color{red}{\text{yes}}$ to the divisibility by $5$ question.
Therefore, you now know that $L = 4$ and two of the $4$ liars were assigned to set $C = \{5,10\}.$
Further, you know that $T_A = T_B = 2.$ This implies that two of the truth-tellers were assigned to set $B = \{4,8\}$ and none of the truth-tellers were assigned to $A \cap (\neg B) = \{2,6,10\}.$
Therefore, since there were only $~4~$ liars, they must have been assigned to $\{5,10\} \cup \{2,6,10\} = \{2,5,6,10\}.$