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?
