To start us off, here’s a modified version of something I saw last night:
A friend chooses a number from 1 to 16, then you ask 7 true/false questions to figure out what the number is. The catch is that the friend is allowed to lie on 1 question. You can only ask questions about the value of the number, not about meta things like “have you lied yet?” but otherwise can be as complicated as you want. You don’t necessarily need to find seven questions that work, just prove that it’s possible and give a general idea of how to find them. Bonus points for determining how many numbers you can distinguish if you’re allowed q questions with t lies.
There’s a branch of math that makes this problem pretty simple, but it should be solvable without it. I also came up with a second version I don’t have an answer for:
A friend chooses 1 of n numbers, then you ask q true/false questions and your friend lies on up to t of them. You can ask about the value of the number, whether the answer to a specific question was a lie, or any logical combination of these (ex: “Is it true that the number even AND you lied on question 3 OR the number is odd AND you told the truth on question 3”). For a given q and t, what’s the largest n for which you can always determine the chosen number?