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?

## No comments:

## Post a Comment