Liar, Liar, Pants on Fire!

First we have the case where all of them are liars, in this case none of them can say the number 0

((M + N - 1)!)/((M-1)!(N)!)

We first have M = N = 5

There are 126 mini-sets for 5 liars

Now we only have to worry with the cases that the 0 appears:

For no liars there is no mini-set with 0

For 1 liar there is only 1 mini-set with 0 (0, 4, 4, 4, 4)

For 2 liars there are 5 mini-sets with 0 (0, 3, 3, 3, a) and "a" can be any integer from 0 to 5 excluding the number 3

For 3 liars there are some mini-sets with 0 (0, 2, 2, a, b) and "a, b" can be any integer from 0 to 5 excluding the number 2, but being careful with the permutation, so we can use the same way that we used before on the case where there are 5 liars: M = 5; N = 2 -> there are 15 mini-sets

For 4 liars we will use the same method (0, 1, a, b, c) M = 5; N = 3 -> there are 35 mini-sets

The total number is: 1+5+15+35+126 = 182

Now we have to analize the cases that we counted twice, that means the cases that can be mistaken with different numbers of liars, everyone of these repeated mini-sets have the 0: (0, 1, 3, 3, 3) -> can have 2 or 4 liars

(0, 1, 2, 2, 0) -> (0, 1, 2, 2, 3) -> can have 3 or 4 liars (0, 1, 2, 2, 4) -> (0, 1, 2, 2, 5) ->

And these are all the cases that we counted twice, so the answer must be 182-5 = 177

I should let you know I am not a very smart student, but a teacher in the UK. This may well mean it is more in the spirit of things to get a solution from someone else. Nor does it feel like the most elegant of solutions!

Consider the case where all 5 tell lies. In which case, all 5 will be able to say any number apart from 0. To work out how many different ways there are to choose r numbers from n numbers, with repeats allowed but order not important, it may be helpful to visualise n numbered boxes, each separated by a partition. Including the outside partitions, these n boxes will have n+1 partitions. Selecting r numbers becomes equivalent to putting r balls in these n boxes. If we represent a partition by a 1 and a ball by a 0, we can see we can represent each choice by a string of n+1 1's and r 0's, with the beginning and ending digit fixed at 1. For example, 10010110101 would represent two 1’s, one 2, zero 3’s,one 4 and one 5. The number of ways of ordering the remaining n-1 1's and r 0's is clearly n-1+r C r . Thus choosing 5 numbers from the digits 1 to 5 gives 9 C 5 =126. Note now that all the 126 possibilities from 5 liars include ALL possible answers that do not contain a zero. Now consider the case where 4 tell lies. In which case there must be one and only one ‘1’. The remaining 4 numbers could be anything apart from 1. However, all the possible answers are already included in the 5 liar case apart from those answers that include at least one 0 (equivalently, all those answers that do not contain precisely zero 0’s). So we need only count the multisets that include a single 1 and at least one 0. To do this, fix the first two answers (as order is not important) at 1 and 0. The remaining 3 digits can all be 0,2,3,4,5. So now we are trying to find the number of ways of choosing 3 numbers from 5. Using the reasoning given above, this is 5-1+3 C 3=7 C 3 =35. So there are 35 possible multisets when there are 4 liars, not including the multisets that are already counted in the 5 liar case. Now consider 3 liars. In this case, there must be precisely two ‘2’ s. The remaining 3 numbers can be anything apart from 2. However, only those that have at least one zero, and do not have precisely one 1 have not yet been counted. So our NEW multisets are those with 2,2,0 and either no 1’s or two 1’s. This means EITHER 2,2,0, and two numbers not including 2 or 1 OR 2,2,0,1,1. The former gives 4 possibilities when the two numbers are identical (5,5, or 4,4 or 3,3 or 0,0) and 6 possibilities when the two numbers are different (4x3/2). The latter gives just one possibility. So there are 10 new multisets arising from the 3 liar case. Now consider 2 liars. In this case, there must be precisely three ‘3’ s. The remaining two numbers can be anything but 3. However, only those that have at least one 0, do not have precisely one 1, and do not have precisely two 2’s have not yet been counted. So we need 3,3,3,0 and a digit that is neither 1 or 3. This is two more multisets. Considering the one liar case, we must have 4,4,4,4. The remaining digit can be anything, but only the one with a zero has not yet been counted, so this gives just one new case. Finally, no liars means everyone says 5; however, this has already been counted (as a possible answer by the 5 liar case, for example). So we have 126+35+10+3+2+1=177

We divide up based on number of truth tellers:

5: 55555

4: 4444?

3: 333??

2: 22???

1: 1????

0: ?????

Note: ?'s can be anything but # of truth tellers

All solutions in 1,2,3,4,5 truth tellers are accounted for in 0 except those including a 0. The 0 case has 9c4 = 126 solutions (we have to solve v+w+x+y+z=5 where v=# of 1's, w=# of 2's and so on). We are left with

4: 44440

3: 3330?

2: 220??

1: 10???

This gives us 4c4 + 5c4 + 6c4 + 7c4 = 56. But we still have repeats. Clearly, there are no repeats using the 4 case. There is one repeat using 3 case: 33301 and 10333. With the 2 case and 1 case we have 2201? where ? is not 1 or 2, giving us 4 repeats here.

Finally, we have 126+56-1-4=177, which is our answer.

Case when there are 0 truth teller, Since all are liars no one will say 0, So,No. of different possible answers=5C5 +5C4 4 +5C3 *6 +5C2 4+5C1 1 Note only digits 1,2,3,4,5 were used here

Case when there is 1 truth teller, So, there will be only one person saying 1 Note* and there must be at least one 0 to insure the sets we are making here are different from the one we made above with no 0. So, No. of different sets=5C3 + 5C2 2 +5C1 1 [0,2,3,4,5 digits were used here]

Case when there are 2 truth teller, So, there must be two 2 and at least one 0. So,No. of different sets= 4C2 + 5C1 1 [here 4C2 was used because we cannot choose 1 again there so only digits 0,3,4,5 was used there and digits 0,1,3,4,5 were used for 5C1 1 because we can choose two 1]

Case when 3 truth teller, So, there is going to be three 3 and atleast one 0 Now here digits 0,2,4,5 are only avaiable So, No. of different sets=4C1

case when 4 truth teller, only one way and that is 04444 gives different set

case when 5 truth teller, only one way and that is 55555 but this set is already counted as it is not different from the case when there was 0 truth teller and every person said 5.

Thus, Total No. of different sets= 126+35+11+4+1=177

If $k$ of the 5 men tell the truth, then there must be exactly $k$ people who answered $k$ . The other $5-k$ people could have given any answer from 0 to 5 aside from $k$ , so there are $5$ possible answers each could give. Since we are looking for the set of answers that was received, the order the answers was given is not important. Thus, we are trying to partition $5-k$ numbers into $5$ boxes. There are $\binom{(5-k) + 5 - 1}{5-1} = \binom{9-k}{4}$ ways of doing this.

Notice that some sets of answers could be received when there are different numbers of truthtellers. For example, $\{2,2,3,3,3\}$ could be received if there are $0$ , $2,$ or $3$ truth tellers. We use the Principle of Inclusion and Exclusion to count the number of distinct sets we can get.

Let $A_k$ be the set of sets of answers that can be received when there are $k$ truth tellers. As discussed above, $|A_k| = \binom{9-k}{4}$ . So $\sum |A_k| = \sum_{i=0}^{5}\binom{9 - i}{4} = 126 + 70 + 35 + 15 + 5 + 1 = 252$ .

We next calculate the size of $|A_k \cap A_j|, j < k$ . Here, we must have $k$ copies of $k$ , $j$ copies of $j$ , and $5-j-k$ of the other 4 numbers. We are now trying to partition $5-j-k$ numbers into 4 boxes, so as above, there are $\binom{5 - j - k + 4 - 1}{4 - 1} = \binom{8-j-k}{3}$ ways to do this. We will omit values of $j,k$ where $j + k > 5$ , since those have an empty intersection.
When $j = 0$ , we have $\binom{7}{3} + \binom{6}{3} + \binom{5}{3} + \binom{4}{3} + \binom{3}{3} = 35 + 20 + 10 + 4 + 1 = 70$ . When $j = 1$ , we have $\binom{5}{3} + \binom{4}{3} + \binom{3}{3} = 15$ . When $j = 2$ , we have $\binom{3}{3} = 1$ . So in total, we have $\sum |A_j \cap A_k| = 70 + 15 + 1 = 86$ .

We now calculate the size of $|A_k \cap A_j \cap A_i|, i < j < k$ . The only sets of values for $i,j,k$ that are small enough to be non-empty here are $(0,1,2),(0,1,3),(0,1,4),(0,2,3)$ . For each of $(0,1,4)$ and $(0,2,3)$ , there is exactly one set in the intersection. For $(0,1,3)$ , there are 3 such sets, since the last number in the set must be one of $2,4,5$ . For the set $0,1,2$ , there are 2 other numbers chosen from $3,4,5$ . There are 3 ways to choose the same number and 3 ways to choose different numbers, so 6 ways in total. Thus $\sum |A_i \cap A_j \cap A_k| = 1 + 1 + 3 + 6 = 11$ .

Finally, since $0+1+2+3 > 5$ , it follows that there are no sets which are in at least 4 of the $A_i$ . Hence, the contribution to PIE will be 0.

By the Principle of Inclusion and Exclusion, there are a total of $252 - 86 + 11 = 177$ such sets.

If n of them always tell the truth, then n of them will say "n" while the rest of them will say something other than "n".So a multiset of answers would consist of n elements that are each n, and (5-n) elements that are each a number other than n (which could repeat).

We need to count the number of 5-element multisets, with elements belonging to the 6-element set {0, 1, 2, 3, 4, 5}, that contain no zeros, exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.

It helps to know that the number of repeated combinations of k elements from n available elements is given by the expression (n + k - 1) choose k.

There is only one multiset with five 5's.

There are 5 multisets with exactly four 4's, none of which have five 5's.

There are (5 + 2 - 1) choose 2 = 15 multisets with exactly three 3's, none of which have exactly four 4's or five 5's.

There are (5 + 3 - 1) choose 3 = 35 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's.So this situation produces only 34 new multisets.

There are (5 + 4 - 1) choose 4 = 70 multisets with exactly one 1, exactly (4 + 2 - 1) choose 2 = 10 of which also has exactly two 2's, exactly 4 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's.None of these 70 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's.So this situation produces only 70 - 10 - 4 - 1 = 55 new multisets.

There are (5 + 5 - 1) choose 5 = 126 multisets with no zeros.We will need to repeat our previous analysis to determine how many of these multisets already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.

So if zeros are no longer allowed: There is only one multiset with five 5's. There are 4 multisets with exactly four 4's, none of which have five 5's. There are (4 + 2 - 1) choose 2 = 10 multisets with exactly three 3's, none of which have exactly four 4's or five 5's. There are (4 + 3 - 1) choose 3 = 20 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's. There are (4 + 4 - 1) choose 4 = 35 multisets with exactly one 1, exactly (3 + 2 - 1) choose 2 = 6 of which also has exactly two 2's, exactly 3 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's.None of these 35 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's.

So, of the 126 mult-sets with no zeros, 1 + 4 + 10 + (20 - 1) + (35 - 6 - 3 - 1) = 1 + 4 + 10 + 19 + 25 = 59 already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.Thus this situation produces only 126 - 59 = 67 new multisets.

Finally, the number of possible multisets is 1 + 5 + 15 + 34 + 55 + 67 = 177.

If n of them always tell the truth, then n of them will say "n" while the rest of them will say something other than "n". So a multiset of answers would consist of n elements that are each n, and (5-n) elements that are each a number other than n (which could repeat).

We need to count the number of 5-element multisets, with elements belonging to the 6-element set {0, 1, 2, 3, 4, 5}, that contain no zeros, exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.

It helps to know that the number of repeated combinations of k elements from n available elements is given by the expression (n + k - 1) choose k.

There is only one multiset with five 5's.

There are 5 multisets with exactly four 4's, none of which have five 5's.

There are (5 + 2 - 1) choose 2 = 15 multisets with exactly three 3's, none of which have exactly four 4's or five 5's.

There are (5 + 3 - 1) choose 3 = 35 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's. So this situation produces only 34 new multisets.

There are (5 + 4 - 1) choose 4 = 70 multisets with exactly one 1, exactly (4 + 2 - 1) choose 2 = 10 of which also has exactly two 2's, exactly 4 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's. None of these 70 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's. So this situation produces only 70 - 10 - 4 - 1 = 55 new multisets.

There are (5 + 5 - 1) choose 5 = 126 multisets with no zeros. We will need to repeat our previous analysis to determine how many of these multisets already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.

So if zeros are no longer allowed: There is only one multiset with five 5's. There are 4 multisets with exactly four 4's, none of which have five 5's. There are (4 + 2 - 1) choose 2 = 10 multisets with exactly three 3's, none of which have exactly four 4's or five 5's. There are (4 + 3 - 1) choose 3 = 20 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's. There are (4 + 4 - 1) choose 4 = 35 multisets with exactly one 1, exactly (3 + 2 - 1) choose 2 = 6 of which also has exactly two 2's, exactly 3 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's. None of these 35 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's.

So, of the 126 mult-sets with no zeros, 1 + 4 + 10 + (20 - 1) + (35 - 6 - 3 - 1) = 1 + 4 + 10 + 19 + 25 = 59 already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's. Thus this situation produces only 126 - 59 = 67 new multisets.

Finally, the number of possible multisets is 1 + 5 + 15 + 34 + 55 + 67 = 177.

If n of them always tell the truth, then n of them will say "n" while the rest of them will say something other than "n". So a multiset of answers would consist of n elements that are each n, and (5-n) elements that are each a number other than n (which could repeat).

We need to count the number of 5-element multisets, with elements belonging to the 6-element set {0, 1, 2, 3, 4, 5}, that contain no zeros, exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.

The number of repeated combinations of k elements from n available elements is ${n + k - 1}\choose k$ .

There is only one multiset with five 5's.

There are 5 multisets with exactly four 4's, none of which have five 5's.

There are ${5 + 2 - 1}\choose 2$ = 15 multisets with exactly three 3's, none of which have exactly four 4's or five 5's.

There are ${5 + 3 - 1}\choose 3$ = 35 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's. So this situation produces only 34 new multisets.

There are ${5 + 4 - 1}\choose 4$ = 70 multisets with exactly one 1, exactly ${4 + 2 - 1}\choose 2$ = 10 of which also has exactly two 2's, exactly 4 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's. None of these 70 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's. So this situation produces only 70 - 10 - 4 - 1 = 55 new multisets.

There are ${5 + 5 - 1}\choose 5$ = 126 multisets with no zeros. We will need to repeat our previous analysis to determine how many of these multisets already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.

So if zeros are no longer allowed: There is only one multiset with five 5's. There are 4 multisets with exactly four 4's, none of which have five 5's. There are ${4 + 2 - 1}\choose 2$ = 10 multisets with exactly three 3's, none of which have exactly four 4's or five 5's. There are ${4 + 3 - 1}\choose 3$ = 20 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's. There are ${4 + 4 - 1}\choose 4$ = 35 multisets with exactly one 1, exactly ${3 + 2 - 1}\choose 2$ = 6 of which also has exactly two 2's, exactly 3 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's. None of these 35 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's.

So, of the 126 multi-sets with no zeros, 1 + 4 + 10 + (20 - 1) + (35 - 6 - 3 - 1) = 1 + 4 + 10 + 19 + 25 = 59 already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's. Thus this situation produces only 126 - 59 = 67 new multisets.

Finally, the number of possible multisets is 1 + 5 + 15 + 34 + 55 + 67 = 177.

If n of them always tell the truth, then n of them will say "n" while the rest of them will say something other than "n".So a multiset of answers would consist of n elements that are each n, and (5-n) elements that are each a number other than n (which could repeat).We need to count the number of 5-element multisets, with elements belonging to the 6-element set {0, 1, 2, 3, 4, 5}, that contain no zeros, exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.It helps to know that the number of repeated combinations of k elements from n available elements is given by the expression (n + k - 1) choose k.There is only one multiset with five 5's.There are 5 multisets with exactly four 4's, none of which have five 5's.There are (5 + 2 - 1) choose 2 = 15 multisets with exactly three 3's, none of which have exactly four 4's or five 5's.There are (5 + 3 - 1) choose 3 = 35 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's.So this situation produces only 34 new multisets.There are (5 + 4 - 1) choose 4 = 70 multisets with exactly one 1, exactly (4 + 2 - 1) choose 2 = 10 of which also has exactly two 2's, exactly 4 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's.None of these 70 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's.So this situation produces only 70 - 10 - 4 - 1 = 55 new multisets.There are (5 + 5 - 1) choose 5 = 126 multisets with no zeros.We will need to repeat our previous analysis to determine how many of these multisets already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.So if zeros are no longer allowed:There is only one multiset with five 5's.There are 4 multisets with exactly four 4's, none of which have five 5's.There are (4 + 2 - 1) choose 2 = 10 multisets with exactly three 3's, none of which have exactly four 4's or five 5's.There are (4 + 3 - 1) choose 3 = 20 multisets with exactly two 2's, exactly one of which also has three 3's but none of which have exactly four 4's or five 5's.There are (4 + 4 - 1) choose 4 = 35 multisets with exactly one 1, exactly (3 + 2 - 1) choose 2 = 6 of which also has exactly two 2's, exactly 3 of which has exactly three 3's, exactly 1 of which has exactly four 4's, and none of which have five 5's.None of these 35 multisets satisfy two or more of the following conditions: having exactly two 2's, having exactly three 3's, having exactly four 4's, having exactly five 5's.So, of the 126 mult-sets with no zeros, 1 + 4 + 10 + (20 - 1) + (35 - 6 - 3 - 1) = 1 + 4 + 10 + 19 + 25 = 59 already have exactly one 1, exactly two 2's, exactly three 3's, exactly four 4's, or exactly five 5's.Thus this situation produces only 126 - 59 = 67 new multisets.Finally, the number of possible multisets is 1 + 5 + 15 + 34 + 55 + 67 = 177.

We divide up based on number of truth tellers: 5: 55555 4: 4444? 3: 333?? 2: 22??? 1: 1???? 0: ????? Note: ?'s can be anything but # of truth tellers All solutions in 1,2,3,4,5 truth tellers are accounted for in 0 except those including a 0. The 0 case has 9c4 = 126 solutions (we have to solve v+w+x+y+z=5 where v=# of 1's, w=# of 2's and so on). We are left with 4: 44440 3: 3330? 2: 220?? 1: 10??? This gives us 4c4 + 5c4 + 6c4 + 7c4 = 56. But we still have repeats. Clearly, there are no repeats using the 4 case. There is one repeat using 3 case: 33301 and 10333. With the 2 case and 1 case we have 2201? where ? is not 1 or 2, giving us 4 repeats here. Finally, we have 126+56-1-4=177, which is our answer.