In an enterprise, no two employees have jobs of the same difficulty and no two of them take the same salary. Every employee gave the following two claims: (i) Less than $12$ employees have a more difficult work; (ii) At least $30$ employees take a higher salary. Assuming that an employee either always lies or always tells the truth, find how many employees are there in the enterprise.
Problem
Source: Slovenia 1997 3rd Grade P4
Tags: logic
03.05.2021 06:47
Let there be $n$ people in the enterprise. Claim: In the top $30$ people for salary, they are all liars. Proof: Assume that there is a truth-teller in that group. Then they say "at least $30$ people have a higher salary than me" which implies that there are $30$ people above them in salary, which is a contradiction because we assumed that this is at most $29$. So the claim is proven. Then, the bottom $n-30$ people for salary all are truth tellers, because they all truthfully say that at least $30$ people have a higher salary. Since the top $30$ people in salary all lie about (i), we must have that there are at least $12$ people above the employee that works the most difficult job in the top $30$ salary. This means that there are at least $12$ people outside of the top $30$ salary, so there are at least $42$ people in total. Since the bottom $n-30$ people all tell the truth about (i), the lowest difficulty worker in that group must have at most $11$ people above them, so there are at most $12$ people in this group. Thus there is at most $42$ people in total. Since $42 \ge n\ge 42$, $n=\boxed{42}$. A construction is shown below. Consider the following leaderboard for salary and difficulty. Salary (highest to lowest): $E_{42}, E_{41}, E_{40}, \dots , E_1$. Difficulty (highest to lowest): $E_1, E_2, E_3, \dots , E_{41}, E_{42}$. $E_i$ is a truth teller for $i = 1, 2, \dots , 12$, and a liar for $i=13, 14, 15, \dots , 42$. For $i=1, 2, \dots , 12$, $E_i$ tells the truth about (i) because only $i-1 < 12$ people work a more difficult job. They tell the truth about (ii) because $42-i \ge 30$ people work a higher salary. For $i=13, 14, \dots , 42$, $E_i$ tells a lie about (i) because there are $i-1 \ge 12$ people that work a more difficult job, and they tell a lie about (ii) because there are $42-i < 30$ people that work a higher salary.