0
$\begingroup$

Assumption:

If the digit sum of $x ∈ ℕ ∩ [12, 100)$ is dividable by 3, it is also dividable by 12.

Examples:

  • $12 → 1+2 = 3$;
    $3 \mod 3 = 0 \Rightarrow 12 \mod 12 = 0$
  • $13 → 1+3 = 4$;
    $4 \mod 3 = 1 \Rightarrow 13 \mod 12 ≠ 0$
  • $24 → 2+4 = 6$;
    $6 \mod 3 = 0 \Rightarrow 24 \mod 12 = 0$

Assumption (more formal):

  • Let $x ∈ ℕ ∩ [12, 100)$
  • Notation used for x:
    • $a_0$ describes the first digit from the right
    • $a_1$ describes the seconds digit from the right
    • ...
    • Example: x = 32: $a_1 = 3$, $a_0 = 2$
  • $(a_1 + a_0) \mod 3 = 0 \Rightarrow (a_1 \times 10 + a_0) \mod 12 = 0$

Question

How would I start from here? I know I could pick $15$ or other numbers to disprove by example. But I'd like to imagine (for the sole purpose of exercise) finding a specific example is too difficult.

$\endgroup$
7
  • 2
    $\begingroup$ What about $x=33333$ ? $\endgroup$
    – Martin R
    Sep 21 '21 at 11:33
  • 1
    $\begingroup$ Or just $x = 33$? $\endgroup$
    – Gary
    Sep 21 '21 at 11:35
  • 2
    $\begingroup$ Digit sum divisible by $3$ only ensures that the given number is divisible by $3$. Not only large enough odd multiples of $3$ are counterexamples, also large enough numbers that are divisible by $2$ and $3$ , but not by $4$ , like $54$. Note that for disproof , a single counterexample is enough. $\endgroup$
    – Peter
    Sep 21 '21 at 11:36
  • $\begingroup$ While these are valid points, if I didn't know them how would I start to get there? $\endgroup$
    – DarkTrick
    Sep 21 '21 at 11:42
  • $\begingroup$ Thumb rule : Try to find a counterexample. If you do not find one in a reasonable time, the claim probably is true (most exercises are probably designed this way) and then try to find a proof. If this fails, you can finally try to find a non-constructive disproof. Here, it is easy to find a counterexample. $\endgroup$
    – Peter
    Sep 21 '21 at 11:55
2
$\begingroup$

Always try out enough examples to see whether or not the statement is actually provable.

$x=15$ is a counterexample: its digits sum to $6$, which is divisible by $3$, but $15$ isn't divisible by $12$.

$\endgroup$
2
  • $\begingroup$ In this case the counterexample comes very early. But what if not? How would I attack this problem then? I have a formula in mind, that shows the impossibility. $\endgroup$
    – DarkTrick
    Sep 21 '21 at 11:52
  • $\begingroup$ There is no general rule to this. Just try some values and trust your feeling. If after some examples, you see some pattern, then the suggested result may indeed be true. Else, you may want to check more values. A computer program may help in some cases. $\endgroup$
    – Zuy
    Sep 21 '21 at 12:48
0
$\begingroup$

To disprove something you need only one example that does not apply. if you want numbers >12 , 15 is the simplest . any other like 27 or 33 or 333 will do. if you want to improve your skills better prove that if the digit sum of n is dividable by 3 the number ist dividable by three .

$\endgroup$
1
  • $\begingroup$ Thank you for the suggestion, but proving for 3 will lead me to the same problem with different numbers. $\endgroup$
    – DarkTrick
    Sep 21 '21 at 12:11
0
$\begingroup$

Proving it for three write the number $a_2a_1a_0$ as $100a_2+10a_1+a_0$ and consider 10, 100, 1000 mod 3=1 so what remainder has $a_n*10^n$

$\endgroup$
0
$\begingroup$

This is how I approached the problem in the end.

Assumption:
$x∈N∩[12,100): (a_2 + a_1 + a_0) \mod3=0⇒(a_1×10+a_0)\mod12=0$

Possible values for $a_1$ and $a_0$ are:
$a_1 ∈ \{0,1,2,3,4,5,6,7,8,9\}$
$a_0 ∈ \{0,1,2,3,4,5,6,7,8,9\}$

From the assumption we know the following is valid
$(a_1 + a_0)\mod3 = 0$

This allows only the following permutations of $a_2$ to $a_0$:
$\{03,06,09,12,...,99\}$

From here we have a clear set we could to check (what other people already wrote, but I feel this explanation here has more structure.)
From here we could also try to figure out how to find a better algorithm to check all values.

Out of scope
In case we would have more digits we would have a formula like this:

$ (∑a_k \times 10^k ) \mod 12 = 0$

= $ (∑ (a_k \mod 12 ) \times (10^k \mod 12) ) \mod 12 = 0$

= $ (∑ a_k \times (10^k \mod 12) ) \mod 12 = 0$

Here $(10^k \mod 12)$ would amount to

  • $k=0 ⇒ (10^k \mod 12) = 1$
  • $k=1 ⇒ (10^k \mod 12) = 10$
  • $k=2 ⇒ (10^k \mod 12) = 4$
  • $k=3 ⇒ (10^k \mod 12) = 4$

So for testing we could use these simplified values.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.