## Monday Math Madness #9: Winner!

We have a winner for MMM #9. It's Seb Perez-D. Congratulations! Drop me a line to arrange for your prize. And, check out Blinkdagger on Monday for their new problem.

A couple of people were confused about the deadline for submitting a solution. The deadline is 12:01 Tuesday Mountain Time, which is to say Tuesday morning. If you do a Google search for "time California" you'll know what time it currently is in California. If it's after 12:01AM the week after a contest is posted then you're late! Using an offset from GMT will get you into trouble since California changes its offset twice each year.

Below is Seb's solution, including a nice terse Matlab program to verify the answer, at the bottom.

There are 84 such numbers.

As a gentle reminder, there are 720 "well formed numbers" with non-repeating digits from 1 to 6. This comes from 6! = factorial 6 =

1x2x3x4x5x6. Only a small part are divisible by 8.Since 200 is divisible by 8, we can concentrate on the "modulus 200" numbers, i.e. the numbers from 0 to 199 which would respect the non-repeating-digits rule. It is easy to write down the list of those numbers:

0,8,16,24, etc. up to 192 (25 numbers in total).

Of those, we can take out the ones having repeated digits and the ones with digits higher than 6 or with 0. This leaves us with 8 numbers modulo 200: 16, 24, 32, 56, 64, 112, 136, 152.

Since we are working modulo 200, to find all the numbers back we have to add 200 or 400 or 600 to these 8 numbers. We take out the

non-well-formed numbers, to get 14 numbers:216, 416, 624, 432, 632, 256, 456, 264, 312, 512, 136, 536, 152, 352.

The first three digits can be all and any permutation of the three other digits. There are 3! = 1x2x3 = 6 ways of permuting these three digits, which means that any of the 14 combinations above can be found in 6 different well-formed numbers. There are thus 84 = 6x14 well formed numbers divisible by 8.

Code in Matlab to calculate the number of numbers:

t=0;P=perms(1:6);for

i=1:length(P),t=t+(mod(polyval(P(i,:),10),8)==0);end;disp(t)

Nicolas provided a C++ program to count the solutions:

#include

#include

using namespace std;int main () {

int myints[] = {1,2,3,4,5,6};

int mul, count=0;do {

mul = myints[0] * 100000 + myints[1] * 10000 + myints[2] * 1000 + myints[3] * 100 + myints[4] * 10 + myints[5] * 1;

if (mul % 8 == 0) {

count++;

cout < < mul << endl ;

}

} while ( next_permutation (myints,myints+6) );cout << count << " permutations divisible by 8" << endl;

return 0;

}

Jon Ingram provided a short Python script:

solutions = 0

for n in xrange(100000, 1000000):

nset = set(str(n))

if nset.issubset("123456") and len(nset)==6 and n%8==0:

solutions += 1

print solutions

Henno Brandsma (editor for topology atlas, http://at.yorku.ca/cgi-bin/bbqa ) provided one of those undecipherable Unix one-liners. His was a very clever command-line call to perl and piped through grep a couple of times and then to wc (word count) to count all the three digit numbers that are divisible by 8, include only the digits from 1-6, and don't repeat digits.

perl -e '$x=104; while($x < 1000){ print $x,"\n"; $x+=8 }' | grep -v '[7890]' | grep -v '\(.\).*\1' | wc -l

Once Henno counted those, he multiplied the Unix output (14) by 6 since for every unique three-digit number he found there are 3! or 6 ways to form other numbers that are still divisible by 8 and meet the constraints of the problem.

And, Heather from the 360 blog made this interesting observation:

Incidentally, since there are 6! = 720 six digits numbers that use the digits 1-6 exactly once, it means that 1 out of every 15 such numbers is divisible by 8. [I was a little surprised at that – I thought it might be 1/8 or 1/12 instead of 1/15].

Heather's comment makes me wonder, if you took numbers with more or fewer than 6 digits (still all non-repeating), what fraction of the numbers for each length would be divisible by 8? While this is not a hard extension, it might make for a nice exploration for some students.

A ReaderJuly 6th, 2008 - 01:51

I’m surpised the other correct proofs don’t even get mentioned. Why am I sending stuff in?

ScottJuly 10th, 2008 - 09:15

When I Google “time California” I get Pacific time. Is the deadline really mountain time, or really “California time”?

LeoJuly 10th, 2008 - 21:55

Could anyone help me with a similar problem?

After creating a list of 8-digit numbers using 1-8 without repeating (8!=40320), you are asked for the sum of all values divisible by 13.

No one i’ve talked to so far has been able to figure it out.

SolJuly 10th, 2008 - 22:18

@A Reader: I don’t have the time to list all correct proofs. I have made the time, though, to credit people with interesting solutions.

@Scott: The deadline is Pacific time. If I’ve ever said Mountain Time I made an error.

@Leo: I think the “13″ problem is very hard, or at least very tedious, because the rules I’ve seen for divisibility by 13 are not easy to work with for all the permutations of non-repeating 8 digit numbers. A computer program can certainly produce an answer with brute force!

LeoJuly 10th, 2008 - 23:10

It’s times like these I wish I knew more about programming. More being anything, that is.

TedJuly 14th, 2008 - 00:16

Leo, using a spreadsheet and brute force I get 3112 values summing to 156062048922.

SebJuly 25th, 2008 - 01:25

@Leo and @Ted: indeed I get 3112 using brute force with my one-liner matlab program.