6
$\begingroup$

You have N numbers written in one row. One needs to put any amount of the four symbols $($, $)$, $+$, and $\times$ between them in such a way that the resulting expression is divisible by $M$.

What are $[N,M]$ pairs it is always possible to do with (independently of the given sequence of numbers)?

For example, with $N=2, M=2$ you can always do what is asked. Indeed, if you have two numbers $a$ and $b$ and at least one is even you write $a \times b$, if none is even you write $a+b$.

Improve this question
$\endgroup$
3
  • $\begingroup$ the asterix is elevated... it still means multiply right? $\endgroup$
    – kaine
    Jun 19, 2014 at 19:22
  • $\begingroup$ @kaine, yes, it does. $\endgroup$
    – klm123
    Jun 19, 2014 at 19:23
  • $\begingroup$ I may have made a mistake. The algorithm works for M=7 and M=49 but I can't show I can make a 1 in all cases. Due to the occational decreasing $N_o$ with increase $M$ I hadn't yet noticed. $\endgroup$
    – kaine
    Jun 20, 2014 at 19:32

1 Answer 1

Reset to default
5
$\begingroup$

You can always do it if $N \ge M$. Reduce all the numbers $\pmod M$. If any are zero, put multiply signs everywhere. If not, imagine putting plus signs everywhere and keeping track of the running sum. Since there are at least $M$, either one is $0 \pmod M$ or two are the same $\pmod M$. If one of the running sums is zero, put parentheses around that addition and multiply all the rest of the numbers. If two of the running sums are the same, start after the first one and go to the end of the second. The sum of that interval will be $0 \pmod M$. Multiply by all the other numbers.

If $M$ is composite and $N$ is at least the sum of the prime factors of $M$ (counting multiplicity) you can succeed. For example, let $M=12, N=7$. We have shown that the first three elements can contribute a factor $3$ and each of the pairs of the last four can contribute a factor $2$ so we can succeed.

If $N$ is at least the sum of the prime factors of $M$ you can succeed. It may be possible to succeed with fewer-I thought I had a proof that you couldn't but it fails.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I overlooked that there was no minus... Good job $\endgroup$
    – kaine
    Jun 19, 2014 at 19:37
  • $\begingroup$ I do not get about N<M. There is solution for N=6, M=9 for example. You just need to make first 3 numbers combination dividable by 3. Then second. Then put $\cdot$ in-between. $\endgroup$
    – klm123
    Jun 19, 2014 at 19:38
  • $\begingroup$ @klm123: yes, I realized it and updated. I don't know how to characterize the possibilities for $M$ composite. For the $N=6, M=9$ case, suppose the numbers $\pmod 3$ start $2,1,1$. You can get a multiple of $3$ from the first two, but that can't multiply a $3$ from the last $3$. In this case I can't find one that doesn't work, but it's not that simple. $\endgroup$
    – Ross Millikan
    Jun 19, 2014 at 19:46
  • $\begingroup$ @RossMillikan, sorry, it is still hard to understand you here. If you have numbers 2,1,1,2,1,1 you can do: (2+1)*1*(2+1)*1 = 9. $\endgroup$
    – klm123
    Jun 19, 2014 at 19:54
  • $\begingroup$ @klm123: good point. So now we can say that for $M$ greater than the sum of a factorization of $N$ we can do it. I'll put that in. It might still be possible to do better. $\endgroup$
    – Ross Millikan
    Jun 19, 2014 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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