# Combinatorics - 2023 students who belong to either one of two categories

Suppose we have 2023 students. Each student can either be lying or telling the truth. We know that each student knows which category (lying or telling the truth) they belong to, and that each student knows what category the other students belong to. We also know that all 2023 students can be put in a column so that each student, except the first one, can say "I'm placed behind a student who is lying". Keeping this in mind, how many columns of 2023 students can be created in this way?

This is an exercise I found online and I am kind of confused by the question. Does this mean that all 2023 students are lying? If so, how many columns can we make.

• I agree the statement is unclear. On its face it seems like you need the first person to be a liar (so the second one can make the desired claim), but if the first person is a liar, then everybody else is "behind" a liar since they are all behind the first person. But perhaps something else is meant.
– lulu
Commented Feb 5, 2023 at 13:01
• Or if "behind" means "immediately behind" then everyone must be a liar except possibly for the last person.
– lulu
Commented Feb 5, 2023 at 13:03
• @lulu I think behind does mean "immediately behind" Commented Feb 5, 2023 at 13:05
• @lulu yes, I think that "behind" means "immediately behind", as in "the first person in front of me is a liar" Commented Feb 5, 2023 at 13:06
• @mrtechtroid Maybe, who knows? But if so then everyone (but the last person) is forced.
– lulu
Commented Feb 5, 2023 at 13:06

As discussed in the comments, “behind” is probably intended to mean “immediately behind”.

For a student $$S$$ to be able to say this, they and the student $$R$$ in front of them must be of different kinds. If they both tell the truth or if they both lie, $$S$$ cannot say that $$R$$ lies; whereas if one tells the truth and the other lies, they can. Thus, all arrangements are valid in which liars and truth-tellers alternate. Since $$2023$$ is odd, we have to start with the type of students which there are more of. So the sequence of types is fixed, and all we can do is permute the students of each type among each other, which yields $$1012!\cdot1011!$$ different arrangements.

Thanks to @D S for pointing out that I’d originally misinterpreted the question in two respects.

• don't you think that since $2023$ is odd, so, if we have once made a column, it tells us that students are divided into 1012 and 1011? So, the column starts with a student of group 1012. You cannot start with a student of 1011, can you?
– D S
Commented Feb 5, 2023 at 13:14
• or does the question mean we can permute the groups?
– D S
Commented Feb 5, 2023 at 13:14
• what I mean in the 1st comment was that if there are $1012$ liars in the first case, then there cannot be $1011$ liars in the next case, i.e, all columns must start with a liar
– D S
Commented Feb 5, 2023 at 13:16
• @DS: I agree; I've edited the answer accordingly. Commented Feb 5, 2023 at 13:18
• what about my second question? maybe the answer is $1012!\cdot 1011!$?
– D S
Commented Feb 5, 2023 at 13:19