2
$\begingroup$

Alice and Bob play a game with first $N$ positive numbers. Out of these $N$ integers some $K$ integers are missing. So both decided to play with remaining $N-K$ integers and in this game Alice wants Bob to win the game.

Game is as follow :

In $X$th move, a player can choose some numbers out of all the numbers available such that chosen numbers sum upto $X$. After the move, chosen numbers are placed back on the table. The player who is not able to make a move loses.

Given that both players play optimally and Alice decides who should go first we need to find who should take the first turn so that Bob wins the game.

Example : Let $N=5$ and $K=2$ and let numbers that are missing are : $\{3,5\}$ so the left out numbers are : $\{1,2,4\}$. Now if Bob plays first then there is always a chance for Bob to win.

Explanation :

Bob can choose {1} to make 1.
Alice can choose {2} to make 2.
Bob can choose {1,2} to make 3.
Alice can choose {4} to make 4.
Bob can choose {1,4} to make 5.
Alice can choose {2,4} to make 6.
Bob can choose {1,2,4} to make 7.
Alice cannot make 8 out of the numbers on the table.
So, Alice loses and Bob wins.
$\endgroup$
  • 1
    $\begingroup$ So what is your actual question? It looks like you have the solution... $\endgroup$ – Michal Paszkiewicz Jan 2 '15 at 10:53
  • $\begingroup$ @MichalPaszkiewicz Question is I need to find solution for given N,K and given values of K who should start the game that is answer would be Alice or Bob depending on values of N,K and array of missing integers $\endgroup$ – prtyush Jan 2 '15 at 11:02
  • $\begingroup$ @prtyush so you're looking for the first $n \in \mathbb{N}$ that can't be formed as a sum of numbers from N. If $n$ is odd, Alice should start, if it is even, Bob should start. $\endgroup$ – Ronald Jan 2 '15 at 11:08
  • $\begingroup$ @Ronald But had you noticed that some numbers are missing ??Than can you proof that your assumption is correct for every case ? $\endgroup$ – prtyush Jan 2 '15 at 11:11
  • $\begingroup$ @Ronald Also how to find this n is main problem i guess.You have any way to find it ? $\endgroup$ – prtyush Jan 2 '15 at 11:12
3
$\begingroup$

There is really only one "move" in the game. Alice needs to decide who should go first. After that, both players are playing mechanically.

To decide who goes first, Alice finds the least X such that no subset of the available numbers adds up to X. Play will end on turn X, and Alice wants to be the one whose turn that is. So, if X is odd, Alice plays first; otherwise she lets Bob play first.

To easily determine X, Alice uses a Sieve. You're probably familiar with the Sieve of Eratosthenes, used to find primes. Same idea, but with different rules for a different purpose.

Alice writes down the numbers from 0 to the sum of all the numbers on the table, and crosses off 0. Then she takes numbers from the table, one at a time, without replacement. When she takes off the number Y, she crosses off every number that is Y plus some previously-crossed off number. When she has done this for every number on the table, the smallest un-crossed-off number is X.

Notice that this works even if the numbers on the table are not all distinct.

It even works if some of them are negative or zero, except that then Alice's initial list runs from the sum of the negative numbers thru the sum of the positive numbers, and X is the least positive un-crossed-off number.


Improved solution

Assume the numbers on the table are distinct positive integers.

If there were no missing numbers, any sum up to $S(N) = N(N+1)/2$ could easily be gotten, and X would be $S(N) = 1$.

But there are missing numbers. Let's start with an empty table, add numbers to it in increasing order, and after placing each number $n$ compute $S(n)$ = sum of all numbers on the table up to $n$. The question is, is it still true that a player could get any sum up to $S(n)$ from these numbers, assuming it was true for $S(n-1)$ before placing $n$.

Well, if $n \le S(n-1)+1$, then the answer is clearly yes. You could already get any sum up to $S(n-1)$ without using $n$. To get a sum $s$ where $S(n-1) \lt s \le S(n)$, combine $n$ with a combination summing to $s - n$ from the smaller numbers.

Conversely, if $n \gt S(n-1)+1$, then the answer is no. The sum $S(n-1)+1$ is unachievable without using $n$, because it exceeds the sum of the other numbers, and is also unachievable using $n$, because $n$ by itself is already too large.

And that leads to an obvious $O(N)$ algorithm to find X

X = 1
for n from 1 to N
    break if n > X
    X += n unless n is one of the missing numbers
end
return X

(I assume it's obvious how to do unless n is one of the missing numbers in constant time, assuming they are given to us in ascending order.)

But if $K$ is much smaller than $N$ we can do better. Suppose we're given the missing numbers in ascending order. Then

MSUM = 0
for each missing number m
    MSUM += m
    X = m * (m + 1)/2 - MSUM + 1
    return X if m >= X
end
return N * (N + 1)/2 - MSUM + 1

This runs in time $O(K)$.

$\endgroup$
  • $\begingroup$ Can you provide some psuedocode or example to make it more understandable that how are you finding X ? $\endgroup$ – prtyush Jan 2 '15 at 11:20
  • $\begingroup$ Also i need a faster way as N can go upto 10^9. and K is 0 ≤ K ≤ min(10^5, N) $\endgroup$ – prtyush Jan 2 '15 at 11:23
  • $\begingroup$ Uh, I thought I just did (give you the pseudo code). As to scaling nicely to large problems, you do realize that the Knapsack problem is reducible to this one, and Knapsack is NP-complete, right? $\endgroup$ – ganbustein Jan 2 '15 at 11:23
  • $\begingroup$ But looping over upto sum of numbers can be very time consuming.Isn't it ? $\endgroup$ – prtyush Jan 2 '15 at 11:25
  • 2
    $\begingroup$ Please edit your question to make clear ALL the requirements. Don't make us play whack-a-mole trying to answer a question you haven't asked yet. $\endgroup$ – ganbustein Jan 2 '15 at 11:47
1
$\begingroup$

I have made a program that gets the solution for this problem to help you out a bit.

Have a look:

http://www.michalpaszkiewicz.co.uk/maths/game-theory/number-sum-game.html

$\endgroup$
  • $\begingroup$ Also Had you checked it for N upto 10^9 ?How much time it take to calculate $\endgroup$ – prtyush Jan 2 '15 at 14:21
  • $\begingroup$ They are, you have to set your N and press 'Generate'. I have removed the max limit, but be aware that for big N, this code will be incredibly slow, as the amount of combinations is a very large amount. Expect your browser to hang. $\endgroup$ – Michal Paszkiewicz Jan 2 '15 at 14:26
  • $\begingroup$ Then how to do it faster for larger N ? $\endgroup$ – prtyush Jan 2 '15 at 14:30
  • $\begingroup$ Rewrite the code and run it on your computer, not in a browser, preferably with multiple threads. $\endgroup$ – Michal Paszkiewicz Jan 2 '15 at 14:33

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.