Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My friend asked me this question and I am not able to solve it even I am not getting how to think about such problem. Please provide a good method?

Given $n$ numbers, you can perform the following operation any number of times : Choose any subset of the numbers (possibly empty), none of which are $0$. Decrement the numbers in the subset by $1$, and increment the numbers not in the subset by $K$. Is it possible to perform operations such that exactly $n - 1$ numbers become $0$?

Constraints :

2 <= n <= 100

1 <= K <= 10

0 <= array element<= 1000

share|improve this question
    
What is $K$ in this context? –  Dennis Meng Sep 24 '13 at 20:09
    
I'm assuming $K$ is a given constant? Certainly not possible if $K \geq n-1$. –  Calvin Lin Sep 24 '13 at 20:26
    
@CalvinLin Possibly, but it could also be the size of the subset you choose. Hence why I asked. –  Dennis Meng Sep 24 '13 at 20:28
    
@DennisMeng Indeed, that was why I said it is not possible if $K \geq n-1$. I'm assuming it is fixed, given $n$. –  Calvin Lin Sep 24 '13 at 20:29
    
Could you make the problem clearer? I can't understand exactly what you are asking. –  innisfree Sep 24 '13 at 21:32

1 Answer 1

up vote 2 down vote accepted

Assuming that $K$ is some positive integer constant, then there exists a method iff all but one share the same remainder mod $(K+1)$.

To see why solutions exist only when $n-1$ of them share the same remainder, consider any arbitrary set of $s$ operations, and two of the numbers, $x_a$ and $x_b$.

If $x_a$ is decremented $a$ times and incremented $s-a$ times, while $x_b$ is decremented $b$ times and incremented $s-b$ times, the net change of $x_a$ is that it increased by $Ks - (K+1)a$, while $x_b$ increased by $Ks - (K+1)b$. Thus, the difference between them changed by $(K+1)(a - b)$. In other words, $x_a - x_b$ could only have changed by a multiple of $(K+1)$. If the difference between them wasn't a multiple of $(K+1)$ before, it can't be 0 now, and thus $x_a$ and $x_b$ wouldn't even be equal, much less both 0.

Now that we've established that solutions only exist when $n-1$ of them share the same remainder, I will show how to actually do it when this case arises.

Let $x_i$ be one of the numbers. The basic idea is to consider the next $(K+1)$ moves as one iteration. The aggregate result of this iteration is:

  • $x_i$ gets incremented twice and decremented $K-1$ times, for a total net increase of $2K - (K-1) = K+1$
  • All other numbers will be incremented once and decremented $K$ times, for a total net increase of $K - K = 0$.

It's not too hard to see that we can create and use such an iteration.

So, suppose $x_t$ is the "odd one out". All we do then is do the above $(K+1)$-step iteration on each of the others until they are all equal (which can be done since they all have the same remainder mod $K+1$). Once all $n-1$ are equal, just decrement them all to 0.


EDIT: Addenda

Technically, the above iteration might run into problems if one of the variables is less than $K$ (the iteration might make it go negative in the middle). To fix this, what you can do is first prime everything with small singleton decrements until all variables are at least $K$. Then, you can do the iterations as needed.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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