Marks that are impossible to obtain?

There is an exam and the marking pattern is -

0 marks - Unattempted



And total number of question is 30. Find the total marks ( in integer ) which are not possible to obtain in the exam. eg.,119 , 118 , 117 etc are the marks that I can think of. Is there any way to approach such question.

• Since the answer is simple, I would like you to mention what approach you took to arrive at the examples: 119, 118, 117, etc., and why do think that is incorrect/inefficient? Jun 8, 2021 at 6:58
• @InuyashaYagamiI just started with 1 then 2 ,....but these were possible.So I started from last. Hit and trial Jun 8, 2021 at 7:10

Let $$C(i, s)$$ be an indicator whether you can achieve a mark $$s$$ by $$i$$ questions. This means $$C(i, s) = 1$$ if there is a way to achieve a mark $$s$$ by $$i$$ questions, and $$0$$ otherwise. Clearly for $$i = 0$$ we have $$C(0, 0) = 1$$ and $$C(0, j) = 0$$ for all $$j \neq 0$$. Now the recursive formula is given by $$C(i, j) = \bigvee\limits_{k \in \{0, -1, 4\}} c(i-1, j-k)$$.
Clearly, you can implement this by iterating over all $$i \in [30]$$ and for each $$i$$ over each value $$s \in [-30, 120]$$.
However, if you want a more straightforward (mathematical) way to know whether a given mark is achievable, I would suggest you look up the extended euclidean algorithm. Specifically, the part where they put an upper and lower bound on the coefficients. Note that the sum of the coefficients, in this case, is at most $$30$$.