Wednesday 15 June 2011

Distracted from distraction by distraction

In which:

Distracted = Intrigued

distraction = !#MathsPuzzle

distraction = #MathsPuzzle

So (Intrigued - !#MathsPuzzle) ÷ #MathsPuzzle = the following...

...which is on a completely different subject to my few previous posts and is probably of interest to even fewer people...

This was prompted by a maths puzzle posted on twitter by Matt Parker @standupmaths.
See #MathsPuzzle if you’re into this kind of thing and fancy more. Some of us are believe it or not...

The original puzzle was as follows:

"QUICK! Make 10 using all and only {4, 6, 7, 9} and any selections from {+, −, ×, ÷, ^} with all the brackets you fancy."

Matt soon after gave his favourite answer (come on, everyone has one!):

"My favourite solution is "9+(7−6)^4" where the 4 is hidden up on a shelf, out of harm's way."

and followed up with this much more intriguing problem:

"Harder meta-#MathsPuzzle: What is the smallest number of randomly selected single digits where there must exist such a way to generate 10?"

"The meta-#MathsPuzzle could be with or without repeated digits. With has some nice cases to consider but without feels like a nicer proof."

So, the question posed is:

What is the smallest number of randomly selected distinct single digits where there must exist a way to generate 10 using the operators {+, −, ×, ÷, ^} with all the brackets you fancy?

Mmm... An everyday kind of question.  After a lunchtime’s scribbling/head scratching I posted the following:

"Five with no repetition. 2 at least will sum to 9 and am fairly sure 1 can always be got from any 3 digits left #MathsPuzzle"

Fairly soon after I realised that this was ... not quite right, though it did at least look to be possibly along the right lines of enquiry. I waited for the nerdosphere to spot my *ahem* deliberate mistakes and very gratifyingly it did – courtesy of Richard Snape @snapey1979 and Neil Jackson @neiljackson111. Brilliant!  If twitter is micro-blogging this was functioning micro peer review in action!

@snapey1979 said"think you may be right with answer not sure of logic. Take 1,2,3,5,9. can't sum to 9 and get 1 but 9/3 +5+(2/1)=10 #mathspuzzle"

@neiljackson111 said "468,479,579 don't give 1 @Our_Frank: @standupmaths and am fairly sure 1 can always be got from any 3 digits left #iknowyouvemovedonbut"

Both great contributions to work in progress and below is, I think, I hope, a more complete proof for five digits – without the limitations of 140 characters.

While mulling all this over I began to suspect that the minimum number of digits needed may well in fact be four – if only because I’d not come across a set of four digits (from an admittedly very small sample) from which I couldn’t generate 10. 

Wonderfully, in the meantime @snapey1979 chucked a computer at the problem and found that all sets of five - and then all sets of four digits will indeed generate 1.  See:

http://www.iesd.dmu.ac.uk/~cascade/mathspuzzle.txt
and
http://www.iesd.dmu.ac.uk/~cascade/mathspuzzle4.txt

I tweeted @snapey1979 to say I thought I might have a "proof" (for five digits).

He said "love to see it if you get there. Elegance trumps brute force every time :-)"


We are children of the iterative age after all and @snapey1979's "brute force" results definitely have elegance - don't they?
 
I'll leave it up to the reader to decide whether the following is elegant even in the slightest.
 
Having said that, I would genuinely love to see a "non-brute force" proof that it can be done with four digits. 

THE PROOF
In summary, it works along the following lines:

THEOREM 1: You can always generate 1 from any four distinct single digits using the operators {+, −, ×, ÷, ^} with all the brackets you fancy.

So, if your set of five digits contains a 9 you can generate 1 from the remaining 4 digits and simply add it to the 9 to get 10.

THEOREM 2: In any set of five digits which does not contain a 9 there exists at least one pair of digits that will sum to 9.

THEOREM 3: You can generate 1 from any three distinct single digits using the operators {+, −, ×, ÷, ^} with all the brackets you fancy EXCEPT the sets {4,6,8}, {4,7,9} and {5,7,9}

So, if your set of five digits doesn’t contain a 9 you can generate 9 from the sum of two of the digits and generate 1 from the remaining three digits (and add to get 10) UNLESS the remaining three digits are {4,6,8} (they can’t be {5,7,9} or {4,7,9} because the original five digit set didn’t contain a 9).

If the remaining digits are {4,6,8} the original set must have been {2,4,6,7,8} because {4,6,8} is what you’re left with after having removed two digits that sum to 9 and {2,7} is the only possibility.

4+6=10 and {2,7,8} (what we’re left with) is obviously neither {4,6,8}, {4,7,9} nor {5,7,9} so you must be able to generate 1 from {2,7,8} (to get 10*1=10). Put explicitly: (4+6)*((8-7)^2)=10

PROOF OF THEOREM 3: You can generate 1 from any three distinct single digits using the operators {+, −, ×, ÷, ^} with all the brackets you fancy EXCEPT the sets {4,6,8}, {4,7,9} and {5,7,9}

Back to front I know - but the proof of theorem 3 leads more or less directly to the proof of theorem 1...

The key fact here is that 1^n=1 for any n i.e. if you can generate 1 from a pair of digits you can generate 1 from any set of 3 digits containing that pair.

1^(y+z)=1 so if x=1 you can generate 1 regardless of the values of y and z.

If x=2:
    and y=3 then y-x=1 and (y-x)^z=1
    and y=4
        and z=5 then z-y=1 and (z-y)^x=1
        and z=6 then (z-y)/x=1
        and z=7 then (z-y)-x=1
        and z=8 then z/(x*y)=1
        and z=9 then z-(x*y)=1
    and y=5
        by similar logic if z is 6, 7 or 8 then you can generate 1
        (z differs from y by either 1,2 or 3 which either differs from x by 1 or is equal to x)
        if z=9 then (x*y)-z=1

If x=3:
    Again, using the same logic if y=4 you can generate 1
    If y=5, you can generate 1 as z=6, 7, 8 or 9 (z-y is either 1, 2, 3 or 4 and x=3)
    If y=6, you can generate 1 as z=7, 8 or 9 (similar logic to above)
    If y=7, you can generate 1 as z=8 or 9
    Etc.

If x=4:
    and y=6
        and z=8 then... I can’t see a way of generating 1.

I don’t think you can generate 1 from {4,6,8}

        If z=9 then x+y-z=1

    and y=7
        and z=9 then... I can’t see a way of generating 1.

I don’t think you can generate 1 from {4,7,9}

    and y=8 the z=9 and y-z=1

If x=5:
    and y=7
        and z=9 then... I can’t see a way of generating 1.

I don’t think you can generate 1 from {5,7,9}

    and y=8 then z=9 and z-y=1

If x=6:
    and y=8 then z=9 and z-y=1
    Etc.

So... the only sets of 3 digits from which 1 cannot be generated are:
{4,6,8}, {4,7,9} and {5,7,9}

PROOF OF THEOREM 1: You can always generate 1 from any four distinct single digits using the operators {+, −, ×, ÷, ^} with all the brackets you fancy.

Any set of four digits must contain at least one subset of three digits from which 1 can be generated. If you generate a four digit set by adding a digit to any of the three sets {4,6,8}, {4,7,9} or {5,7,9} there will inevitably exist a three digit subset of it which is none of these sets. From this three digit subset you can generate 1 (by theorem 3) and raise it to the power of the remaining digit.

PROOF OF THEOREM 2: In any set of five digits which does not contain a 9 there exists at least one pair of digits that will sum to 9.

Here are the two digit sets which sum to 9: {1,8}, {2,7}, {3,6} and {4,5}

Each pair has one odd and one even number and no digits are repeated.

If in the five digit set there are all 4 even digits then the remaining digit must be odd and will sum with one of the even digits to 9.

If in the five digit set there are 3 even digits the remaining two must be odd. There is only one odd number that will not sum with any of the even digits to 9 so one of the two must.

If in the five digit set there are 2 even digits the remaining three must be odd. There are only two odd numbers that will not sum with any of the even digits to 9 so one of the three must.

If in the five digit set there is 1 even digit the remaining four must be odd. There are only three odd numbers that will not sum with any of the even digits to 9 so one of the four must.

QED?