5

Mark with T or F all the below statements in such a way that they do not contradict with each other:

  1. At most $1$ statement is true

  2. At most $1$ statement is false

  3. At most $2$ statements are true

  4. At most $2$ statements are false

  5. At most $3$ statements are true

  6. At most $3$ statements are false

  7. At most $4$ statements are true

  8. At most $4$ statements are false

  9. At most $5$ statements are true

  10. At most $5$ statements are false

We have a total of $10$ statements. If we mark the $1^{\mathrm{st}}$ with T, it means all others must be false. But this contradicts with the 2nd. We can safely mark the last $2$ as True. But if we say, for example, at most $5$ statements are true, can it be also correct that "at most $3$ (or $2$ or $4$, etc.) statements are true"? At most $5$ statements are true means at least $5$ statements are false, which is OK in combination with the $10^{\mathrm{th}}$, right?

But if we say "at most $1$ statement is true", it means "at minimum $9$ statements are false". But if "at minimum $9$ statements are false", doesn't it mean also that "at minimum $7$ statements are false" for example?

How can we combine them all together?

I am completely stuck!

Nika
  • 727
Nhung Huyen
  • 369
  • 2
  • 12
  • Well, why not just try some cases and think about the implications? One trick that sometimes works: Assign values $T,F$ however you like, then evaluate each statement (reassigning according to whatever was true or false in your last iteration). If there is a consistent assignment it would be a fixed point for this operation. – lulu Feb 14 '18 at 15:17
  • Note: somethings are clear. The first two statements can't both be true for example. More broadly, the number of true statements plus the number of false statements has to be $10$. That should help a lot. – lulu Feb 14 '18 at 15:19
  • Dear Lulu, thank you for your comment. Obviously I have tried lots of combinations (I can't post them all here); I have been struggling with this problem for about a month now. – Nhung Huyen Feb 14 '18 at 15:20
  • Well, have you tried my algorithm? Easy to automate...let a computer try to find a fixed point. – lulu Feb 14 '18 at 15:22
  • I just tried it....found a fixed point almost instantly. $(0,0,0,0,1,0,1,0,1,0)$ where $1$ means True and $0$ means False. It's a good technique! You have to play with the seed (there are non-trivial cycles) and of course there might be more than one fixed point or some fixed points might be "repulsive". But still. – lulu Feb 14 '18 at 15:25
  • A nice one! What is this algorithm that you mention? And the fixed point? – Carlos Lopez Feb 14 '18 at 15:34
  • @CarlosLopez Assign T/F however you like. Say you assign all True (obviously wrong, but whatever). Now check your assignment against the definition. In this case, you'd get that all the odd numbered questions were False and all the even ones were True. Iterate again. Any correct assignment would have to be a fixed point. As it happens, this seed leads to a non-trivial cycle. But the second seed I tried (generated randomly) worked perfectly. – lulu Feb 14 '18 at 15:36
  • Worth remarking: In my view, the dynamic computer search is actually a better approach than pure logic, as you can scale the program to huge arrays of questions. In this case, however, pure logic isn't hard: divide the questions into Even/Odd. Note that after the first true Even (or Odd) question, all subsequent questions of the same Parity are also true. That reduces the list to something that could easily be searched with pencil and paper. – lulu Feb 14 '18 at 17:19
  • @lulu : Hello! I have two questions: How do you identify the first true even (or odd)? Second: Why is it that all subsequent are also true? I have seen also Noah's hint below but I don't quite understand. Nhung, that's a nice puzzle! – Samuel Feb 14 '18 at 17:31
  • @Samuel Well, say question $5$ is true. Reading the question we learn that at most $3$ questions are true. But, given that, then of course at most $4$ questions are true, so question $7$ is true. Similarly $9$ is true, and so on. At this point I proposed a simple search (as there are so few ways to specify the first true Odd and Even questions) but I am sure a little thinking could narrow the search (possibly down to $1$). – lulu Feb 14 '18 at 17:36
  • @Samuel To apply logic: if question $3$ were true, then questions $3,5,7,9$ would be true which would be $4$ true questions at least, in contradiction of the statement of question $3$. Thus we know that questions $1,3$ are false. And so on. – lulu Feb 14 '18 at 17:38

1 Answers1

1

If we mark the 1st with T, it means all others must be false. But this contradicts with the 2nd. We can safely mark the last 2 as True.

I don't understand your reasoning here. Why are you sure you can safely mark 2 as "true?" You've just argued that 2 is false if 1 is true, so you need to be sure that 1 is false ...

(Now, 1 is in fact guaranteed to be false, but you haven't argued that yet.)

if we say, for example, at most 5 statements are true, can it be also correct that "at most 3 statements are true"?

Sure - maybe exactly 3 statements are true.

As a hint to get started, based on the two comments above:

Can you show that if the statement "at most $n$ statements are true" (resp. false) is true, then the statement "at most $k$ statements are true" (resp. false) is also true if $k>n$?

E.g. if 1 is true, then 3 has to be true as well, etc. This lets you rule out a bunch of statements right off the bat.

Another hint:

Try to solve a simpler case - say, what if you had only statements 1-4? What about 1-6?

Noah Schweber
  • 245,398
  • Thank you all guys, I think I am starting to understand! I still haven't found a "mathematical" way to prove Noah's statement above - I understand it by intuition only. – Nhung Huyen Feb 15 '18 at 10:17