Total number of distinct possible marks for given number of questions and marks (ZIO 2023 Q1)

Question

Q. There is an exam with N problems. For each problem, a participant can either choose to answer the problem, or skip the problem. If the participant chooses to answer the problem and gets it correct, the participant is awarded X points. If the participant chooses to answer the problem but answers it incorrectly, 1 point is deducted from their score. If the participant skipped the problem, there is no change to their score. For each of the following values of N and X, compute the number of distinct scores the participant could obtain in the exam:

(a) N = 7, X = 4 (sol: 30)

(b) N = 15, X = 18 (sol: 136)

(c) N = 30, X = 20 (sol: 441)

I have made a formula for solving this question, which is $\frac{(N+1)(N+2)}{2}-\frac{(N-X)(N+1-X)}{2}$, and for $X >=N, N-X$ will be considered $0$

I made this formula by observing certain patterns, and its giving me the required solution.
I am still not satisfied with this formula

Can you guys please point out any mistakes, and also share more elegant solutions if you have?

Thank you

Answer 1

First, we simplify the problem slightly by adding 1 to each problem score

• 0 if answered incorrectly
• 1 if left blank
• $X+1$ if answered correctly This doesn't affect the count of distinct scores.

Second, a total score $S$ can be obtained, if there exists non-negative integers $a, b, c$ such that $b + c(X+1) = S$, $a+b+c= N$. This suggests that we consider setting $ c = \lfloor \frac{S}{X+1} \rfloor$. Let's explore this in more detail.

Third, we consider the case $ X \geq N$ first, where OP claims the answer is $\frac{(N+1)(N+2) } { 2}$.

• For $0 \leq S < X+1$, we require $ c = 0 $ and hence we can only get $S = 0 $ to $N$.
• For $X+1 \leq S < 2(X+1)$, we require $ c < 2$, and clearly $ c = 0$ gies us a maximum score of $ N < X+1$. Thus $ c = 1$, and hence we can only get $S =X+1$ to $X+1 + (N-1)$.
• More generally, for $r(X+1) \leq S < (r+1) (X+1)$, show that we require $ c = r$ and can only get $ S = r(X+1) $ to $r(X+1) + (N-r)$.
• Hence, the total number of scores is $(N+1) + N + \ldots + 1 = \frac{ (N+1)(N+2) } { 2 } $.

Fourth, how does the above change for $ X < N$?
A/ Looking at $ 0 \leq S < X+1$, then we can only get scores from $S = 0 $ to $X$ (as opposed to getting it up to $N$). B/ Looking at the argument for $ X+1 \leq S < 2(X+1)$, we could actually use $ c = 0$ to get a score of $ N \geq X+1$.
So, these ideas don't easily work at first.
But, what you can do is show that

• We can get scores from 0 to $sX$ for some $x$.
• From $r(X+1) \leq S < (r+1) (X+1)$, we can only get $X - (r-s) $ scores.
• Hence, the total number of scores we can get is (fill in the blank).