Proving you *can't* make $2011$ out of $1,2,3,4$: nice twist on the usual

An undergraduate was telling me about a puzzle he'd found: the idea was to make $2011$ out of the numbers $1, 2, 3, 4, \ldots, n$ with the following rules/constraints: the numbers must stay in order, and you can only use $+$, $-$, $\times$, $/$, ^ and $!$. In words, "plus minus times divide, exponentiation and factorial". The game was to construct $2011$ with $n$ as small as possible.

To my amazement, he had managed to do $n=5$: indeed

$$((1+2)!)!+(3!)^4-5=2011.$$

He now wanted to solve the puzzle completely by proving that $n=1,2,3,4$ are impossible.

So there's where it gets interesting. My first thought was "computer search -- done". But it's not as easy as that, because factorial is only a unary operator. For example one has to rule out any possible amazing cancellations between very large numbers, e.g. one has to check

$$(1+2)!!!!!!!!!!!!!-3^{(4!!!!!!!!!!!)} \neq 2011.$$

This one in particular is not hard to rule out, because, for example, the left hand side is a multiple of $3$ and the right hand side isn't. In general, this approach can perhaps be used to bound the number of factorials that can occur in any presentation of $2011$ using $1, 2, 3, 4$ only -- but making this rigorous seemed a bit delicate and I wondered if I was missing something. Anyone any ideas?

EDIT: Ron Maimon's heroic attempt to deal with the problem by brute force has led him to the interesting case of $2011=(1+2)!!!...!!!/(3!!!...!!!/4!!!!...!!!)$, which seems to be tougher to rule out than the others: the game here is to prove that $2011$ cannot be written as $3!!!...!!!*4!!!!...!!!/3!!!!...!!!$ for any choices of numbers of factorials.

EDIT: Size considerations seem to deal with the above case. Ultimately it seems that the question I asked can be answered using a rather lengthy, but finite(!), procedure. Thanks Ron for your efforts.

Solution 1:

This is simple enough to do by hand, although there are many cases. First, dispose of the case n=1, since 1 is a fixed point for factorials. The case n=2, is similarly trivial, since 2 is also a fixed point for factorials and 2011 is not a factorial.

I will come back to n=3 later, first I will discuss the problem of n=4.

Binary operations make a parse-tree, so that the binary operations you perform give a skeleton upon which you can add factorials. There are exactly five binary trees on 4 nodes, which I list below:

• pairing: ((12)(34))
• forward: (((12)3)4)
• backward: (1(2(34)))
• center-left: ((1(23))4)
• center-right: (1((23)4))

These five parenthizations define the five ways to apply binary operations to the leaves 1,2,3,4. The factorials can come on the three leaf, producing 6,720,etc, on the four leaf, producing 24, etc, or on one of the three parenthesized intermediate quantities.

There can be no factorial applied to the top node, since 2011 is not a factorial. For each case, there are exactly four nodes on each tree where you can apply factorial--- on 3, on 4, and on the two intermediate nodes.

Three quantities cannot do it

In order to deal with n=4, one has to methodically deal with n=3. In this case, there are only 2 different parenthizations

• left: (1(23))
• right: ((12)3)

Factorial is only allowed on 3, and on the value of the inner parenthesis. The outer quantity can't get a factorial, since 2011 is not a factorial.

Now notice: the operation involving 1 is either +,-,*,/,^. The last operation produces 1, reducing the problem size to binary, the divide operation produces nonsense, and the * operator just removes the 1 node. So the only possibility is +/- (EDIT: if you expand the domain to rational numbers, so that you can make 1/(2*3!!!) in intermediate stages, there are many new cases)

This means that, the answer 2011 is either produced from left, in which case 2010 is written using (23), or right, in which case 2011 is written using (33). Both of these are binary and trivially impossible.

This disposes of n=3

Four quantities mostly reduce to three

Again, four quantities reduce to 3 when you consider the binary operation involving 1. If this operation is not + or -, it must kill the node (EDIT: excluding rational number operations), thereby reducing the tree to 3,2, or 1 objects.

The remaining possiblity is that 1 adds to a quantity. This produces the following three-quantity problems:

• ((3 3) 4) make 2011
• (3(3 4)) make 2011
• (2(3 4)) make 2010 or 2011
• ((2 3) 4) make 2010 or 2011

and exactly one true four-quantity problem * ((1 + (23)) 4)

The true four-quantity problem has 15 possible operation combinations and 4 places to put factorials. I will first dispense with the three-quantity cases.

2 3 4 or 3 3 4 don't make 2011

The top node making 2011 can't be ^, because 2011 is not a power. It can't be * because 2011 is prime. This leaves +,-,/. I will call A_n the n-fold factorial iteration:

• (3_n + 3_m)_k + 4_l
• (3_m - 3_n)_k + 4_l
• (3_m * 3_n)_k + 4_l
• (3_m / 3_n)_k + 4_l

• (3_m ^ 3_n)_k + 4_l

• (3_n + 3_m)_k - 4_l

• (3_m - 3_n)_k - 4_l
• (3_m * 3_n)_k - 4_l
• (3_m / 3_n)_k - 4_l
• (3_m ^ 3_n)_k - 4_l

For k>0, these cannot be 2011 for parity reasons. For k=0, the products/quotients are excluded for parity reasons (since 3_m and 3_n are never different by 1, their quotient is always even or equal to 1--- 1 is excluded because 2010 is not an iterated factorial of 4, exponentiation case is excluded by divisibility by 3 for l>0 and by the fact that 2015 and 2007 are not powers for l=0). This leaves

• 3_n + 3_m - 4_l
• 3_n - 3_m + 4_l
• 3_n - 3_m - 4_l

(the all plus case is excluded by size bounds and a finite search). It is impossible for both n,m to be bigger than 1, or else the sum is even. So exactly one of n or m is 1. Then reducing modulo 6 gives 3 for l>1 n>1 and 2011 is 1 modulo 6.

The case where the first 3 is replaced by 2 is handled exactly the same.

• (3_n + 3_m)_k / 4_l
• (3_m - 3_n)_k / 4_l
• (3_m * 3_n)_k / 4_l
• (3_m / 3_n)_k / 4_l
• (3_m ^ 3_n)_k / 4_l

This cannot be 2011 for k>0 for primeness reasons (2011 is not the ratio of two factorials other than 2011!/2010! and (33) does not make 8044). This leaves the k=0 cases:

EDIT: I skipped these nontrivial cases too.

• (3_n + 3_m) = 2011 4_l
• (3_m - 3_n) = 2011 4_l
• (3_m * 3_n) = 2011 4_l : UNRESOLVED
• 3_m = 2011 4_l 3_l
• (3_m ^ 3_n) = 2011 4_l

The case A!= 2011 B! C! is resolved in the next section, and this takes care of 3_m = 2011 4_l 3_l. The case 3_m^3^n is resolved by noting that the right side factorial must be sufficiently bigger than the left side factorial to include a new prime. A! + B! = 2011 C! requires A>C and B>C and WLOG A>B, so that, dividing, you get C(C+1)...(C+(A-C)) + C(C+1)..(C+(B-C)) = 2011, which requires by primeness C=B or C=B-1 but 3_k and 4_m can never be exactly equal by one-oneness of factorial, and they can't differ by 1, except at m=0 k=0, because they are always both even.

The case 3_m * 3_n = 2011 4_l is unresolved, and is similar to the other unresolved case below.

next there is (3(34)). In this case, the top node again cannot be * or ^ because 2011 is not a power or a product.

EDIT: MORE (3(34))

So there are another 15 cases (before, I wrote them down, but didn't work them out.)

• 3_l + (3_m + 4_n)_p :

The inside of the paren is at least 7, 7! is 5040, too big, so p=0. The quantities 3_l+3_m is even unless exactly one of l or m is zero, so you have 3 +3_m + 4_n , which is a finite search to pass through 2011.

• 3_l + (3_m - 4_n)_p

The inside of the paren cannot be negative, and if it is positive, m must be at least 1, so that the second term is even. This means the first term must be odd, so l=0. This makes 3 + (3_m - 4_n)_p = 2011, and 2008 is not a factorial, so p=0. So you want the difference of 3_m and 4_n to be 2008, which is impossible if n>0 because 2008 isn't 0 mod 3. So 2004 must be 3_m, which is impossible.

• 3_l + (3_m * 4_n)_p

2011 is 1 mod 3, and this is zero mod 3.

• 3_l + (3_m / 4_n)_p

The question of how to interpret quotients arises here--- I will interpret it as the integer part. So the inner argument of the paren can be 0 or 1 (3/4 and 6/4), making 3_l 2010 or 2011, impossible. So the inner part of the paren is not 0 or 1. The ratio of two factorials which is bigger than 2 is itself an integer, so you get the sum of two factorials, which is even unless l=0 or p=0.

If l=0, you have a factorial which gives 2008, which, since 2008 is not factorial, gives p=0, and 2008 is a ratio of factorials which is impossible, because it doesn't factor into the product of consecutive numbers.

This leaves p=0, l nonzero. (3_l - 2011) * 4_n + 3_m = 0, which by signs requires that 3_l<2011, so that l is 1,2,3. and this is the two cases:

• (6 - 2011) * 4_n + 3_m = 0
• (720 - 2011) * 4_n + 3_m = 0

Both these equations are impossible because the nontrivial coefficient, 2005 and 291, cannot be the ration of two factorials, since neither is a product of consecutive numbers.

• 3_l + (3_m ^ 4_n)_p

This is zero mod 3, and 2011 is not.

• 3_l - (3_m + 4_n)_p

This is zero mod 3 unless n=0 and p=0. 3_l - 3_m + 4 = 2011, meaning that the difference of 2 iterated factorials of 3 needs to be 2007, which is odd, so this is impossible.

• 3_l - (3_m - 4_n)_p

This is zero mod 3 unless n=0 and p=0, 3_l - 3_m - 4 = 2011 so that the difference of 2 iterated factorials of 3 needs to be 2015, which is not zero mod 3, so done.

• 3_l - (3_m * 4_n)_p

This quantity is zero mod 3, unlike 2011.

• 3_l - (3_m / 4_n)_p

These two quantities will both be even unless p=0, l=0, or the quantity in the parentheses is 1. l=0 is excluded since the result is less than 3, and if the quantity in parens is 1, then 3_l must be 2010, not possible. So this requires p=0, and this becomes the diophantine equations

• 3_m = (3_l- 2011)4_n

In this case, 3_l must be bigger than 2011, so that l>2. 3_m/4_n is a ratio of two factorials, so it becomes

(A!/(B!(A-B)!))*(A-B)! = (3_l - 2011)

The left side is even in any nontrivial case, and the right side is odd, ruling this out by parity.

• 3_l - (3_m ^ 4^n)_p

This is zero mod 3, so not 2011.

• 3_l / (3_m + 4_n)_p
• 3_l / (3_m - 4_n)_p
• 3_l / (3_m * 4_n)_p
• 3_l / (3_m / 4_n)_p
• 3_l / (3_m ^ 4_n)_p

The quotient of two nontrivial factorials is always a product of consecutive numbers, so it cannot be 2011 unless the top is 2011! and the bottom is 2010!. 3_l is never 2011. You can conclude that either l=0 or p=0. l=0 is impossible, since the result would be smaller than 3, so p=0 for all the above. This gives the following 4 diophantine equations

• 3_l = 2011*(3_m + 4_n)
• 3_l = 2011*(3_m - 4_n)
• 3_l = 2011*(3_m * 4_n)
• 3_l = 2011*(3_m ^ 4_n)
• 3_l = 2011*(3_m / 4_n)

For the first four cases, l must be bigger than 3 because 3!!!=720! which does not have a factor of 2011. So these are all big nontrivial factorials.

Consider a more general form of the sum equation, the first case equation above:

• A! = 2011 (B!+C!)

Without loss of generality A>B>C, so dividing by C! gives A!/C! = 2011(B!/C!+1) where the quantities A!/C! and B!/C! are products of consecutive integers, at least one of which is even, because A is not equal to B, and both are even unless B=C+1. So B=C+1, and you get A!/C! = 2011(C+1), or A!=2011(C+1)! which is impossible because 2011 is not a product of consecutive integers. The same thing rules out the minus sign case.

• A! = 2011 B! C!

Again, WLOG, B>C, this can be rewritten:

• (A!/B!(A-B)!) ( (A-B)!/C!(A-B-C)!) (A-B-C)! = 2011

where everything is expressed in terms of the multiplicatively more fundamental binomial coefficients. This requires that each factor is either 1 or 2011, which requires either A=B+C or A=B+C+1, since the last factor can't equal 2011 under any circumstances. In both cases, the two combinatorial coefficients become one, and the result is that C=1 or 0 and B=2010 while A=2011, giving the two trivial solutions 2011! = 2011 * 2010! 1! and 2011! = 2011 2010! 0!, and no others (these trivial solutions don't work, they don't have C>4 for one). Done.

• A! = 2011 B!^C!

Where C>4. Since C>4, and for B bigger than 2, (B!)^4> (2B)! (easy to prove using Stirling's formula), you can conclude that A>2B, so that there is a new prime between B and 2B which is contained in A! which is not contained on the right side, done. This also works when C is 3, so it resolves the parallel case for (33)4 above.

The final case to consider is the quotient of the quotient, which rearranges into

• 3_l * 4_n = 2011 * 3_m

here, either l is bigger than 3, or else n is bigger than 2, in order for one of the two objects on the left to have a factor of 2011, so these are big factorials again. The general form

• A! B! = 2011 C!

for large A, B, and C, WLOG A

• 2011 ((A+B)!/A!B!) = (A+B)(A+B-1)..(A+B-y+1)

In this formula, A and C are both factorial iterates of 3, while B is a factorial iterate of 4. This means that C is either equal to A (which doesn't work) or enormously bigger than A, being at least A!. To make the size of the right and left hand side equal, B must be about the same size as C.

The LHS is B^A/A!, while the right hand side is B^y, so to match, A and y have to be of the same order.

Now the right hand side is divisible by y!, while the left hand side cannot be divisible by something as big as A!. This is a property of Pascal's triangle, that ((A+B)!/A!B!) is not divisible again by A!. The reason is a simple prime counting:

The number of powers of 2 in N! is N/2 + N/4 + N/8 + N/16... + N/(2^(log_2(N))) where division means floor division. This is asymptotic to N, and this means that the number of powers of 2 just cancel between numerator and denominator when A+B=C. If you want y! to factor into the resulting element of Pascal's triangle, you need extra powers of 2 in C!, an amount about equal to 2A+B. There shouldn't be this many powers of 2 in (C!). The same holds for powers of 3, or of any other prime less than A.

So it should be impossible to satisfy the equation based just on prime-power counting, but this argument doesn't prove it, because B is so enormous compared to A, the error in the power of two estimate for ((A+B)!) is naively bigger than A. But there are odd entries in Pascal's triangle arbitrarily far out, especially near the left edge, so there must be better bounds on the prime powers occuring in Pascal's triangle than what I gave. I am sure that y! can't go into the Pascal triangle entry for large y, but I can't give a solid argument. So I will leave it as unresolved for now.

I am surprised that this case is so much more difficult than the other cases, because it is relatively obvious that purely multiplicative stuff cannot work, that you need additive stuff.

anyway: UNRESOLVED. But the above sketch might resolve it if made precise.

EDIT (2 (3 4)) doesn't make 2011 (for completeness sake)

I neglected to work out the 2(34) cases to make 2011. The top node cannot be * or ^, since 2011 is not prime or a power, and it can't be - or /, because 2011 is bigger than 2.

• 2 + (3_m + 4_n)_p
• 2 + (3_m - 4_n)_p
• 2 + (3_m * 4_n)_p
• 2 + (3_m / 4_n)_p
• 2 + (3_m ^ 4_n)_p

p>0 is excluded because 2009 is not a factorial. 3_m + 4_n, 3_m - 4_n doesn't work for m>0 because of parity, so m=0, and so done. The power case 3_m^4_n is excluded because 2009 is not a power. (3_m *4_n) is zero mod 3, and 2009 is not, so the only case is 3_m=2009 4_m, which is of the form

• A! = 2009 B!

or (A!/B!(A-B)!)(A-B)! = 2009 which is excluded by parity unless A=B+1, when you get the trivial solution 2009! = 2009*2008!, which doesn't match iterated factorials of 3 and 4.

For the sake of allowing fractions, I will consider the only reasonable division process

• 2/(3_m/4_m) = 2*4_m/3_m = 2011

this is an even integer when the numerator is bigger than the denominator, namely 2( A!/(B!(A-B)!))(A-B)!, so excluded.

2 3 4 doesn't make 2010

Now 2010 = 2 * 3 * 5 * 67. The decomposition into ((23)4) can only get factorials on 3 and 4.

• (2+3_m)_n +4_p
• (2-3_m)_n +4_p
• (2*3_m)_n +4_p
• (2/3_m)_n +4_p

• (2^3_m)_n +4_p

• (2+3_m)_n -4_p

• (2-3_m)_n -4_p
• (2*3_m)_n -4_p
• (2/3_m)_n -4_p
• (2^3_m)_n -4_p

for these cases, it is enough to note that 2010 is not divisible by 4, so that n=0 or n=1, or the argument of the factorial is 1, and a tedious enumeration exhausts these.

• (2+3_m)_n *4_p
• (2-3_m)_n *4_p
• (2*3_m)_n *4_p
• (2/3_m)_n *4_p
• (2^3_m)_n *4_p

2010 is not divisible by 4, so these are ruled out.

• (2+3_m)_n /4_p
• (2-3_m)_n /4_p
• (2*3_m)_n /4_p
• (2/3_m)_n /4_p
• (2^3_m)_n /4_p

These give the relation 2010 4^p = (2*3_n)_m. Looking at it modulo 7 and 67 forbids this equation from holding for any m,n.

• (2+3_m)_n ^4_p
• (2-3_m)_n ^4_p
• (2*3_m)_n ^4_p
• (2/3_m)_n ^4_p
• (2^3_m)_n ^4_p

2010 is not a power.

((1+(23))4) doesn't make 2011

There are 15 cases, since the top node cannot be * by primeness, and cannot be ^ since 2011 is not a power:

• (1+(2+3_l)_m)_n + 4_p
• (1+(2-3_l)_m)_n + 4_p
• (1+(2*3_l)_m)_n + 4_p
• (1+(2/3_l)_m)_n + 4_p

• (1+(2^3_l)_m)_n + 4_p

• (1+(2+3_l)_m)_n - 4_p

• (1+(2-3_l)_m)_n - 4_p
• (1+(2*3_l)_m)_n - 4_p
• (1+(2/3_l)_m)_n - 4_p
• (1+(2^3_l)_m)_n - 4_p

n=0 by parity. This reduces the problem by associativity into 2,3,4 making 2010.

• (1+(2+3_l)_m)_n / 4_p
• (1+(2-3_l)_m)_n / 4_p
• (1+(2*3_l)_m)_n / 4_p
• (1+(2/3_l)_m)_n / 4_p
• (1+(2^3_l)_m)_n / 4_p

These are the only truly new cases. In this case, you get 2011*4_p = (1 + (something))_n which is forbidden by looking modulo 2011.

It is very likely that your friend did a search of this sort for the case n=5 to find the special solution.

Solution 2:

If square roots and percentages (and unary minus) are permitted, then there are a number of solutions, the simplest probably being

$$2011 = (-1 + (2 + 3!)!\%) \div \sqrt{4\%}$$

Many years ago, I wrote a simple Windows program called $200$ Up (link to Dropbox folder) for solving problems like these:

$\hspace{1.75in}$

The domain of calculation is $\mathbb{Z}/d$ for some specified denominator $d\in\mathbb{N}$ (and with limits on the magnitude of the numerator).

Note that, in the image above, the solution for 2018 is

$$ \large 2018 \;\;=\;\; \big( \sqrt[\sqrt{\cdot \dot{1}}]{\Large 2} \; + \; 3!!\%\% \big) \; \div \; \cdot 4\%. $$