Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n? (NO bracket allowed!!)

Probably title is slightly ambiguous but I could not see any way of shortening the problem.

I am sure many of you have seen the problem like

$2$ $\square$ $2$ $\square$ $2$ $\square$ $2$ $\square$ $2$ $=$ $20$

something like this where between the numbers we can use some sort of operation depending on the question.

Well I think the question is motivated by this.

Let $n>2$. Given any set of $n-1$ numbers (we can swap the order) and we can only use addition, subtraction and multiplication, can we make a multiple of $n$ always?

Another way of putting it is:

Given $n-1$ elements of non-integral domain $\mathbb{Z}/n\mathbb{Z}$, can we make zero only using $+,-,\times$? Oh and by the way bracket is not allowed!!!!

I was asked this in an interview randomly and I could not figure it out and the interviewer did not know the answer either.

As people suggested I will post the 'proof' if bracket is allowed.

If bracket is allowed then this is easy. I will use the second form of the problem.

Firstly let $n>2$ and $a_1,...,a_{n-1} \in \mathbb{Z}/n\mathbb{Z}$

If any of the $a_i$ is equal to zero then we could just multiply all the $a_i$s so assume $a_i$ are all non-zero.

Also if bracket is allowed, if $a_i=a_j$, we could simply put $(a_i-a_j)$ and multiply all other elements together.

So we could assume $a_1,...,a_{n-1}$=1,...,n-1

In which case if bracket is allowed, $(1+(n-1))$ times all other elements would give the wanted answer.

But hey. NO Brackets allowed!

I have checked for small $n$s that this is possible and my intuition is that for big $n$ this should easily be possible. But I can't think of a way to show that.

Solution 1:

Edit: If $n\gt 5$, it seems we can make everything equal $0$ just using $\{-,\times\}$. That is, it seems $+$ is not needed! (This was verified for $n=6,7,8,9,10,11,12$.)

But, I do not know how to prove this.

This is a long comment, as requested.

There are only $\binom{2n-3}{n-1}$ multisets $a_1,...,a_{n-1} \in \mathbb{Z}/n\mathbb{Z}$ to consider, for given $n$.

We have $a_1,...,a_{n-1}\ne 0$, because otherwise we can multiply everything with $0$.

I have written a simple brute force search in python. I observed:

1. It seems we only need to use $2$ operations at once ($+,\times$ or $-,\times$ or $+,-$).

2. It seems we can always assume $a_1\ge a_2\ge \dots \ge a_{n-1}$.

These two observations have been verified for all $n\le12$.

Below is my (disclaimer: inefficient) python code and its output.

For all possible (decreasing) mutisets of numbers:

• It tries all $3\cdot 2^{n-2}$ ways to put two of three operations between numbers.

• If solution isn't found, it tries it again but for all permutations of numbers.

• If solution isn't found, it tries all $3^{n-2}$ ways to put three operations.

• If solution isn't found, it tries it again but for all permutations of numbers.

• If solution isn't found, it is a counter-example to the problem.

Code:

import itertools

def exprf(A,b,O):
    return ''.join([f'{A[_]}{O[b[_]]}' for _ in range(len(b))])+str(A[-1])

def solve(A,n,OP):
    k = len(OP[0])
    for o in range(k**(n-2)):
        b=[]
        while o!=0:
            o, r = divmod(o, k)
            b.append(r)
        while len(b)!=n-2:
            b.append(0)
        for op in OP:
            expr = exprf(A,b,op)
            if eval(expr)%n==0:
                return [expr, op]
    return False

for n in range(3,20):
    m = 0
    for a in itertools.combinations(range(1,2*(n-1)), n-1):
        m += 1
        A = [a[i]-i for i in range(n-2,-1,-1)]
        solved = solve(A, n, [['+','*'],['-','*'],['+','-']])
        if not solved:
            for P in itertools.permutations(A):
                solved = solve(P, n, [['+','*'],['-','*'],['+','-']])
                if solved:
                    break
            if not solved:
                solved = solve(A, n, [['*','+','-']])
                if not solved:
                    for P in itertools.permutations(A):
                        solved = solve(P, n, [['*','+','-']])
                        if solved:
                            break
                    if not solved:
                        print("COUNTER-EXAMPLE:", A)
                    else:
                      print(f"{n}: All operations and permutation needed:", solved[0])  
                else:
                    print(f"{n}: All operations needed:", solved[0])
            else:
                print(f"{n}: Permutation needed: ", solved[0])
        else:
            pass #print(solved[0])
    print(f'{n}: {m} multisets solved.')
    
    

Output:

3: 3 multisets solved.
4: 10 multisets solved.
5: 35 multisets solved.
6: 126 multisets solved.
7: 462 multisets solved.
8: 1716 multisets solved.
9: 6435 multisets solved.
10: 24310 multisets solved.
11: 92378 multisets solved.
12: 352716 multisets solved.

Btw, if "$\ge$" is changed to "$\le$" in observation 2., then

10: Permutation needed:  1*1*1*1*1*4*8-1-1

is the only observed exception to the modified observation.