2
$\begingroup$

I have the following exercise for six-grade pupils:

Write all the integers from 1 to 1999 consecutively in any order so that each integer appears exactly once to get a number. (For example, a number like 13245...199819991997 is acceptable.) Is that number divisible by 2005?

I guess the answer is no, however I don't know how to prove it. Can some one help me? Thanks a lot!

$\endgroup$
  • 4
    $\begingroup$ Surely, to be divisible by 2005 it needs to be divisible by 5... Also, I am a bit at loss what ‘consecutively in any order’ means... $\endgroup$ – user491874 Dec 6 '17 at 5:29
  • 2
    $\begingroup$ Do you mean: "Write every number between 1 and 1999 in any order to create a single number, then determine if the resulting number can be divided by 2005."? - Math would be more difficult than I remembered it in grade 6. $\endgroup$ – Rob Dec 6 '17 at 5:39
  • $\begingroup$ As should be clear from the other comments, it should be clear that the number $123456789101112\dots 19981999$ which is formed by concatenating each integer from $1$ to $1999$ in increasing order is not divisible by $2005$ since it is not divisible by $5$ (seen by the last digit). A more interesting question is whether there exists any order in which we can concatenate the integers from $1$ to $1999$ where it does happen to be divisible by $2005$ or if every order is not divisible by $2005$. For example, is $123467\dots 199819995$ divisible by $2005$ where the first 5 is now at the end? $\endgroup$ – JMoravitz Dec 6 '17 at 6:30
  • $\begingroup$ In the original phrasing of the question "...in any order to get a number. Is that number divisible by 2005?" We have ruled out the answer of "always yes" as being incorrect, but no comment or answer yet has been able to say whether the answer to your question is "always no" or "sometimes no, sometimes yes." $\endgroup$ – JMoravitz Dec 6 '17 at 6:34
  • $\begingroup$ Hi all! Sorry for not to be precise. By ''any order'' I mean that a number like 132546....199919981997 is acceptable. $\endgroup$ – mapping Dec 6 '17 at 14:48
2
$\begingroup$

I'm guessing your asking for $1234567891011121314...1999$. This number would not be divisible by $2005$, because it would need to have a units digit of $5$.

$\endgroup$
  • 2
    $\begingroup$ Or a units digit of 0. $\endgroup$ – user491874 Dec 6 '17 at 5:55
1
$\begingroup$

I thought I would cobble together at least a brute force proof that such a number does exist.

Namely, put all numbers except for 1-8 in any order, then finish with one permutation of 1, 2, 3, 4, 6, 7, 8, finally write 5. All that it takes is to prove that all permutations of 1,2,3,4,6,7,8 with 5 added at the end go through all possible remainders when divided by 401. (There are $7!=5040$ of them, so plenty of chance for this to happen.) The following C program proves it:

#include <stdio.h>

int main(void)
{
    int flags[401] = {0};
    int a, b, c, d, e, f, g, n;

    for (a = 1; a <= 8; ++a) {
        if (a == 5) continue;
        for (b = 1; b <= 8; ++b) {
            if (b == 5 || b == a) continue;
            for (c = 1; c <= 8; ++c) {
                if (c == 5 || c == a || c == b) continue;
                for (d = 1; d <= 8; ++d) {
                    if (d == 5 || d == a || d == b || d == c) continue;
                    for (e = 1; e <= 8; ++e) {
                        if (e == 5 || e == a || e == b || e == c || e == d) continue;
                        for (f = 1; f <= 8; ++f) {
                            if (f == 5 || f == a || f == b || f == c || f == d || f == e) continue;
                            for (g = 1; g <= 8; ++g) {
                                if (g == 5 || g == a || g == b || g == c || g == d || g == e || g == f) continue;
                                n = 10000000*a + 1000000*b + 100000*c + 10000*d + 1000*e + 100*f + 10*g + 5;
                                flags[n%401] = 1;
                            }
                        }
                    }
                }
            }
        }
    }
    for (n = 0; n < 401; ++n) {
        if (!flags[n]) {
            printf("Not covered: %d\n", n);
            return 1;
        }
    }
    printf("Covered\n");
    return 0;
}

It goes through all the permutations (12346785, 12346875, ..., 87643215) and marks all remainders (mod 401) that it encounters in the meantime, and prints "Covered" if all remainders have got marked by the end. Surely enough, this program outputs "Covered".

$\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.