8
$\begingroup$

If only the four basic operations, concatenation and parenthesis are allowed, the largest number which can be obtained from $2$ $0$ $2$ $0$ is... $2020$ :-) (If exponentials were allowed, $20^{20}$ would be much higher, of course). But what is the smallest number which can be obtained?

Clarifications (note that many answers were written before these were added):

  • The numbers 2, 0, 2, 0 must be used in that order.
  • None may be omitted.
  • The "four basic operations" do not include unary + (which would be a no-op in any case) or unary - (which would e.g. allow -2020 as an answer).
  • "Smallest" means "most negative", not "closest to zero".
  • Concatenation may only be applied to literal digits.
  • Exponentiation is not allowed, even though it is written without any explicit operators.
  • Inserting decimal points is not allowed.
$\endgroup$
1
  • 1
    $\begingroup$ You may also want to disallow division by zero as undefined. $\endgroup$
    – Ben
    Dec 18, 2019 at 9:13

5 Answers 5

17
$\begingroup$

If only addition ($+$), subtraction ($−$), multiplication ($\times$) and division ($/$), without unary minus, then

$2 \times ( 0 - 20) = -40$

$\endgroup$
0
27
$\begingroup$

With only 4 digits combined with binary operators, we can only have three combining operations, hence only five possible parsing trees:

parsing trees

The digits are the dark purple nodes. The operations are the bright yellow nodes. Representing that as a parsing tree makes parenthesis unnecessary (they could be derived from them).

How many possible parse trees we have?

  • We have $5$ possible topologies of parsing trees.

  • There are $5$ possible operators ($+$, $-$, $\times$, $\div$ and concatenation). They are assignable independently to each bright yellow node, so we $5^3$ possibilities for them.

  • There are $6$ ways which we can choose $2$ of the $4$ dark purple nodes and assign $0$ to them: 1st and 2nd; 1st and 3rd; 1st and 4th; 2nd and 3rd; 2nd and 4th; 3rd and 4th. However, since the digits have to stay at the same order, there is only one way.

So this gives a total of:

$5 \times 5^3 = 625$ possible parsing trees.

So, what about brute-forcing all those possibilities (it is not a very big number) and find out what is the smallest number (and also the largest also). This is something that a computer can do, so let's go with Python:

from dataclasses import dataclass
from enum import Enum
from typing import Callable, Dict, Generic, List, TypeVar, Union

number = Union[int, float]

def normalize(a: number) -> number:
    try:
        return int(a)
    except Exception:
        return a

class Op:
    def op(self) -> number:
        raise Exception("Should override")

    def __str__(self):
        return "Junk"

class Num(Op):
    def __init__(self, a: number) -> None:
        self.__a = a

    def op(self) -> number:
        return self.__a

    def __str__(self):
        return str(self.__a)

class Concat(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        a: number = self.__a.op()
        b: number = self.__b.op()
        if int(a) == float(a): a = int(a)
        if int(b) == float(b): b = int(b)
        x: str = str(a) + str(b)
        try:
            return int(x)
        except Exception:
            return float(x)

    def __str__(self):
        return f"({self.__a} c {self.__b})"

class Add(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        return normalize(self.__a.op() + self.__b.op())

    def __str__(self):
        return f"({self.__a} + {self.__b})"

class Sub(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        return normalize(self.__a.op() - self.__b.op())

    def __str__(self):
        return f"({self.__a} - {self.__b})"

class Times(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        return normalize(self.__a.op() * self.__b.op())

    def __str__(self):
        return f"({self.__a} * {self.__b})"

class Div(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        return normalize(self.__a.op() / self.__b.op())

    def __str__(self):
        return f"({self.__a} / {self.__b})"

# Not currently used. But I'll left it here if you want to play with it.
class Pow(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        return normalize(self.__a.op() ** self.__b.op())

    def __str__(self):
        return f"({self.__a} ^ {self.__b})"

# Not currently used. But I'll left it here if you want to play with it.
class UnaryMinus(Op):
    def __init__(self, a: Op) -> None:
        self.__a = a

    def op(self) -> number:
        return -self.__a.op()

    def __str__(self):
        return f"-{self.__a}"

# Not currently used. But I'll left it here if you want to play with it.
class Dot(Op):
    def __init__(self, a: Op, b: Op) -> None:
        self.__a = a
        self.__b = b

    def op(self) -> number:
        a: number = self.__a.op()
        b: number = self.__b.op()
        if int(a) == float(a): a = int(a)
        if int(b) == float(b): b = int(b)
        x: str = str(a) + '.' + str(b)
        return float(x)

    def __str__(self):
        return f"({self.__a} d {self.__b})"

def combine(op: str, op1: Op, op2: Op) -> Op:
    if len(op) == 2: return UnaryMinus(combine(op[1], op1, op2))
    if op == '+': return Add(op1, op2)
    if op == '-': return Sub(op1, op2)
    if op == '*': return Times(op1, op2)
    if op == '/': return Div(op1, op2)
    if op == 'c': return Concat(op1, op2)
    if op == '^': return Pow(op1, op2)
    if op == 'd': return Dot(op1, op2)
    raise Exception("WTF!?")

def join(p: str, a: int, b: int, c: int, d: int, x: str, y: str, z: str) -> Op:
    na: Num = Num(a)
    nb: Num = Num(b)
    nc: Num = Num(c)
    nd: Num = Num(d)
    if p == 'balanced': return combine(z, combine(x, na, nb), combine(y, nc, nd))
    if p == 'lefty': return combine(z, combine(y, combine(x, na, nb), nc), nd)
    if p == 'righty': return combine(x, na, combine(y, nb, combine(z, nc, nd)))
    if p == 'zigzag': return combine(z, na, combine(y, combine(x, nb, nc), nd))
    if p == 'zagzig': return combine(z, combine(y, na, combine(x, nb, nc)), nd)
    raise Exception("WTF!?")

def do_it_all() -> None:

    nums_a: List[List[int]] = [[2, 0, 2, 0]]

    # Not currently used. This is if we would allow to change the positions of the numbers.
    nums_b: List[List[int]] = [
        [0, 0, 2, 2], [0, 2, 0, 2], [0, 2, 2, 0], [2, 0, 0, 2], [2, 0, 2, 0], [2, 2, 0, 0],
    ]

    # Not currently used. This is if we would allow to change both the positions and the sign of the numbers.
    nums_c: List[List[int]] = [
        [0, 0, 2, 2], [0, 2, 0, 2], [0, 2, 2, 0], [2, 0, 0, 2], [2, 0, 2, 0], [2, 2, 0, 0],
        [0, 0, -2, 2], [0, -2, 0, 2], [0, -2, 2, 0], [-2, 0, 0, 2], [-2, 0, 2, 0], [-2, 2, 0, 0],
        [0, 0, 2, -2], [0, 2, 0, -2], [0, 2, -2, 0], [2, 0, 0, -2], [2, 0, -2, 0], [2, -2, 0, 0],
        [0, 0, -2, -2], [0, -2, 0, -2], [0, -2, -2, 0], [-2, 0, 0, -2], [-2, 0, -2, 0], [-2, -2, 0, 0],
    ]

    trees: List[str] = ['balanced', 'lefty', 'righty', 'zigzag', 'zagzig']

    ops_simple: List[str] = ['+', '-', '*', '/', 'c']
    ops_complex: List[str] = ['+', '-', '*', '/', 'c', 'd', '^', 'u+', 'u-', 'u*', 'u/', 'uc', 'u^', 'ud']

    max: number = -99999.9999
    max_op: Op = Op()
    min: number = 99999.9999
    min_op: Op = Op()

    nums: List[List[int]] = nums_a # Change to nums_b or nums_c if you want to allow changes in the number position or in the number signs.
    ops: List[str] = ops_simple    # Change to ops_complex to allow exponentiation, concatenation with dot and unary minus.
    out: Dict[str, number] = {}

    for p in trees:
        for a in nums:
            for x in ops:
                for y in ops:
                    for z in ops:
                        t: Op = join(p, a[0], a[1], a[2], a[3], x, y, z)
                        try:
                            n: number = t.op()
                            s: str = str(n)
                            print(str(t) + ": " + s)
                            out[s] = out.get(s, 0) + 1
                            if n < min:
                                min = n
                                min_op = t
                            if n > max:
                                max = n
                                max_op = t
                        except Exception as fuuuu:
                            xxx = str(fuuuu)
                            print(str(t) + f": Ops! - {xxx}")
                            out[xxx] = out.get(xxx, 0) + 1

    print(f"Min: {min} = {min_op}")
    print(f"Max: {max} = {max_op}")
    print(out)

do_it_all()

The final output is:

The smallest possible number is $-40$ produced with $(2 \times (0 - (2 \; c \; 0)))$ (where $c$ denotes concatenation). The largest is $2020$.

And since this is a brute-force program exhausting all the possible search space, this gives a proof that there is no better solution.

Note that it should be reasonably easy to change this program to allow unary minus, to allow changing the order of the digits, to allow exponentiation or to allow decimal points. In fact, it is only a two lines change (see the comments in the code). Allowing all of those, the results are:

$$\small{\text{min} = -1606938044258990275541962092341162602522202993782792835301376 = -(2^{200})}$$ $$\small{\text{max} = 1606938044258990275541962092341162602522202993782792835301376 = 2^{200}}$$

More, due to popular demand, the code also shows the distribution of the possible answers. Here is the results:

"division by zero" is the result of 202 parse trees.
The number 0 is the result of 128 parse trees.
The number 2 is the result of 62 parse trees.
The number 4 is the result of 46 parse trees.
The number 20 is the result of 37 parse trees.
The number 22 is the result of 32 parse trees.
The number 1 is the result of 21 parse trees.
The number 40 is the result of 20 parse trees.
The number 220 is the result of 11 parse trees.
"could not convert string to float: '2-2'" is the result of 9 parse trees.
The number -18 is the result of 8 parse trees.
The number 10 is the result of 8 parse trees.
The number -4 is the result of 6 parse trees.
The number -1 is the result of 6 parse trees.
The number -2 is the result of 4 parse trees.
The number 18 is the result of 4 parse trees.
The number 202 is the result of 4 parse trees.
The number -40 is the result of 3 parse trees.
The number 200 is the result of 3 parse trees.
The number -20 is the result of 2 parse trees.
The number 400 is the result of 2 parse trees.
The number 2020 is the result of 2 parse trees.
"could not convert string to float: '2-20'" is the result of 2 parse trees.
The number -10 is the result of 1 parse tree.
The number 100 is the result of 1 parse tree.
The number 180 is the result of 1 parse tree.

$\endgroup$
8
  • 1
    $\begingroup$ Nice! It would be cool to see a distribution of all the possible answers. $\endgroup$ Dec 16, 2019 at 21:45
  • $\begingroup$ @chmod777j What you say is the distribution of the 625 possible answers? $\endgroup$ Dec 16, 2019 at 22:33
  • 8
    $\begingroup$ Yeah, like a frequency distribution of the 625 answers in buckets from -40 to 2020 $\endgroup$ Dec 16, 2019 at 23:30
  • $\begingroup$ @chmod777j It looks like the code already prints each result print(str(t) + ": " + str(n)) so it'd be a matter of someone with the right libraries running it and dumping all the output. $\endgroup$ Dec 18, 2019 at 13:18
  • 1
    $\begingroup$ Pretty sure the green check should go here since it proves what the answer is. $\endgroup$ Dec 18, 2019 at 17:56
15
$\begingroup$

How about:

$-(2020) = -2020$

That seems to be as small as we can go.

If we can't use operations outside of the digits, then my answer would be:

$2(0) - 20 = -20$

$\endgroup$
1
  • $\begingroup$ unary minus is not a basic operation :-) $\endgroup$
    – mau
    Dec 16, 2019 at 18:52
11
$\begingroup$

Well, it's not an answer in strict sense of the word.

$$\frac{-202}{+0}=-\infty\ \mathrm{(we\ REALLY\ cannot\ go\ smaller)}$$ (Note that the $f(+0)$ is just a shorthand notation of the one-sided limit $\lim\limits_{x\to0+0}{f(x)}$, which is used at least in Russian - as a variation, you can use $0+$ instead of $+0$.)

$\endgroup$
3
  • 1
    $\begingroup$ unary minus isn't allowed. I'd suggest 2*0-2/0 instead, as answered by Ben. $\endgroup$ Dec 17, 2019 at 21:22
  • $\begingroup$ Since the infinity of irrational numbers is larger than the infinity of integers we can go smaller with -2sqrt(02)/0. $\endgroup$ Dec 18, 2019 at 11:46
  • $\begingroup$ The "infinity" implied by division by zero is not a cardinal number in any meaningful sense, so your idea there is categorically incorrect. $\endgroup$ Dec 18, 2019 at 17:54
2
$\begingroup$

Smallest (most negative) is:

2 × 0 − 2 / 0 = −∞

$\endgroup$
3
  • 2
    $\begingroup$ Division by zero is not defined in ordinary arithmetic; in particular, it doesn't result in "infinity". You might be thinking of the projectively extended reals, but in that space infinity is not greater than or less than real numbers, so it wouldn't be "the most negative". $\endgroup$
    – Sneftel
    Dec 17, 2019 at 10:19
  • 2
    $\begingroup$ @Sneftel The great thing about mathematics is there are so many to choose from. Obviously you've heard of the affinely extended real line, which is generally what is (implicitly) taught in high school, where students are indeed told that -1/0 = -inf based on the limit. $\endgroup$
    – Ben
    Dec 17, 2019 at 12:46
  • $\begingroup$ @Ben Its limit may be -∞, or it may tend to -∞, but you know it just isn't "equal to -∞". $\endgroup$
    – ccjmne
    Dec 17, 2019 at 18:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.