Sunday Times Teaser 3121 – Top Marks

by BRG on July 15, 2022

by Howard Williams

Published Sunday July 17 2022 (link)

A teacher is preparing her end of term class test. After the test she will arrive at each pupil’s score by giving a fixed number of marks for a correct answer, no marks if a question is not attempted, and deducting a mark for each incorrect answer. The computer program she uses to prepare parents’ reports can only accept tests with the number of possible test scores (including negative scores) equal to 100.

She has worked out all possible combinations of the number of questions asked and marks awarded for a correct answer that satisfy this requirement, and has chosen the one that allows the highest possible score for a pupil.

What is that highest possible score?

From → Uncategorized

3 Comments Leave one →

Brian Gladman permalink


# for storing the maximum mark and the associated data
maxm, qm = 0, ()

# consider the possible mark (m) for a correct answer  
for m in range(1, 21):
  n, ln = 0, 0
  # continue while the number of different results is not greater than 100
  while ln <= 100:    
    # consider the possible number of questions (n)
    n += 1
    # consider the possible numbers of right and wrong answers (noting 
    # that r + w <= n), collecting the different resulting test marks
    sc = set(m * r - w for r in range(n + 1) for w in range(n - r + 1))

    # there must be 100 different possible test marks
    ln = len(sc)
    if ln == 100:
      # save the naximum mark and the associated data
      mx = max(sc)
      if mx > maxm:
        maxm, qm = mx, (n, m)
        print(f"{m=} {n=} -> {mx:3}")
  
print(f"Maximum mark {maxm} ({qm[1]} marks for each of {qm[0]} questions).")

# for storing the maximum mark and the associated data

maxm, qm = 0, ()

# consider the possible mark (m) for a correct answer

for m in range(1, 21):

n, ln = 0, 0

# continue while the number of different results is not greater than 100

while ln <= 100:

# consider the possible number of questions (n)

n += 1

# consider the possible numbers of right and wrong answers (noting

# that r + w <= n), collecting the different resulting test marks

sc = set(m * r - w for r in range(n + 1) for w in range(n - r + 1))

# there must be 100 different possible test marks

ln = len(sc)

if ln == 100:

# save the naximum mark and the associated data

mx = max(sc)

if mx > maxm:

maxm, qm = mx, (n, m)

print(f"{m=} {n=} -> {mx:3}")

print(f"Maximum mark {maxm} ({qm[1]} marks for each of {qm[0]} questions).")

There is a faster method found by Frits (and then analysed by Jim Randell here) which shows that, of the numbers between \(-n\) and \(m.n\) inclusive, \(m(m-1)/2\) are not possible when \(n>=m\). The missing values are illustrated here for \(n=15\) and \(m=7\):


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|||||||||||||||||||||||||||||||||||||| ||||||  |||||   ||||    |||     ||      |

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

|||||||||||||||||||||||||||||||||||||| |||||| ||||| |||| ||| || |

This gives the solution:


# for storing the maximum mark and the associated data
maxm, qm = 0, ()

# consider the possible mark (m) for a correct answer  
for m in range(1, 21):
  n, ln = m - 1, 0
  # continue while the number of different results is not greater than 100
  while ln <= 100:    
    # consider the possible number of questions (n)
    n += 1
    # the number of different exam results
    ln = n + 1 + m * n - m * (m - 1) // 2
    if ln == 100:
      # save the naximum mark and the associated data
      mx = m * n
      if mx > maxm:
        maxm, qm = mx, (n, m)
        print(f"{m=} {n=} -> {mx:3}")
  
print(f"Maximum mark {maxm} ({qm[1]} marks for each of {qm[0]} questions).")

# for storing the maximum mark and the associated data

maxm, qm = 0, ()

# consider the possible mark (m) for a correct answer

for m in range(1, 21):

n, ln = m - 1, 0

# continue while the number of different results is not greater than 100

while ln <= 100:

# consider the possible number of questions (n)

n += 1

# the number of different exam results

ln = n + 1 + m * n - m * (m - 1) // 2

if ln == 100:

# save the naximum mark and the associated data

mx = m * n

if mx > maxm:

maxm, qm = mx, (n, m)

print(f"{m=} {n=} -> {mx:3}")

print(f"Maximum mark {maxm} ({qm[1]} marks for each of {qm[0]} questions).")

Erling Torkildsen permalink

Brian,

Why is number of questions (nq) and possible mark (m) limited to 20?
My own program work much like yours and yields a hit (but not maximum) for nq = 21 (and m = 4)..

Reply
- Brian Gladman permalink
  
  Yes, its a typo, the limit on nq should be higher (I intend to change it to speed it up shortly).
  
  Reply

Sunday Times Teaser 3121 – Top Marks

by Howard Williams

Published Sunday July 17 2022 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta