3
$\begingroup$

Consider the set
$S := \{$ "the number of lies in the set $S$ is a multiple of $n$" $|$ $n = 1, 2, 3, ... , 120 \}$.

Question: Which elements/sentences in the set $S$ are true in every possible non-contradictory case?

Or, in other words:

Does there exist $v$ in $\{0, 1\}^{120}$ satisfying that: the $n$-th component of $v$ is $0$ if and only if the number of $0$ components in $v$ is a multiple of $n$? Which components of $v$ are $0$ if $v$ exists?

$T = \{ n$ divides $|F|: n$ in $\{1,...,120\} \}$ and $F = \{ 1,...,120 \} - T$. Solve the "set equation(s)" for $T$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Let x be the number of lies in the set (0 to 120, inclusive).

A computer scan determines that the values of x leading to a non-contradictory situation are

0 (all sentences are true) and 108 (= 2^2 * 3^3, so sentences 1 2 3 4 6 9 12 18 27 36 54 108 are true and the rest are false).

so the desired answer is

the sentences from the 108 case.

In general, for a set of any size,

0 lies is always non-contradictory, and a non-zero number of lies is non-contradictory if and only if the number plus its number of divisors (including itself) equals the size of the set. The number of the divisors is the product of (exponent + 1) over the exponents in its prime factorization. (Edited to fix the mistake that Jaap Scherphuis pointed out.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your very last sentence is not quite correct. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 24, 2022 at 11:32
  • $\begingroup$ I feel the narrative flow of the answer might be improved quite a bit by starting with the final spoiler block that describes how to find the non-contradictory cases, and only then proceeding to apply that technique. $\endgroup$
    – Bass
    Commented Dec 24, 2022 at 11:33
  • 1
    $\begingroup$ Jaap Scherphuis: Thanks, I edited it to fix that part. $\endgroup$
    – Ed Murphy
    Commented Dec 26, 2022 at 7:39