Possible scores in a quiz

combinatorics

I'm really not sure how to describe this problem in summary, so I'm going to have to give you the long explanation. Hopefully this will make sense.

Imagine that you have a quiz. There are 40 questions. The first 10 each award 100 points. The next 10 each award 250 points. The next 10 are 500 points, and the last 10 are 1000 points.

So: 10 x 100, 10 x 250, 10 x 500 and 10 x 1000.

You can take the test in any order that you like, and you can submit multiple answers (assume feedback is instant), but you can only score each question once.

So, I want to work out how many possible scores could exist in this quiz.

For example, we know that it is impossible to score anything less than 100, because that's the smallest possible correct score. We also know that we can score 18,500 in total. What other scores are actually possible for a player to be on at any given point?

My first thought was to look at permutations, but that's not what we're actually looking for. Because if I were to answer the 10 challenges that award me 100 points I would have 1000 points, which is the same as if I just scored a single 1000 point challenge.

What I'm interested in is unique possible scores.

The best way that I could come up with for solving this was to brute-force it. That is, I took an array of the scores and shuffled them, then went through them in order, adding them up, recording each score with a counter against it. I then repeated this process over and over.

What I found was that if I performed enough shuffles (accounting for the fact that the code could well shuffle into a previously shuffled solution) that eventually I would get a consistent answer, which is 366.

Fantastic, there's my answer.

But how can I solve this without this brute-force solution? Is there another way to do this?

As a side note, I was curious how this would look if I were to plot the possible scores, and the number of times that each score was found while following a player's possible route through the challenges, the resulting chart looks like this:

Scores

The maximum 18,500 score is excluded, since that occurs for every player that completes the competition, regardless of the route they take through the challenges.

This isn't terribly surprising, but I do think it's quite beautiful.

Bonus question:

If we can solve how to calculate this, I would be really happy. BUT, there's an added (potential) complication, which is as follows:

The groups of challenges may be guarded by a progression mode. What I mean by that is that is that you may need to complete n% of a given group of challenges before you can proceed to the next challenges. This means that we can't just shuffle the entire array of challenges, as it will only be possible to access some later challenges after you've completed the earlier ones.

For example; consider that you can only do the easy 100 point challenges at first. You need to complete 75% of the group in order to proceed to the next series, but at that point everything is unlocked. That would mean that you would have to have scored 100, 200, 300, 400, 500, 600 700, and then 800 points. At this point your next score could be 900, 1050, 1300 or 1800.

Again, I could calculate this by testing a large number of iterations, and implementing the unlock algorithms, but I wonder if there's a way to calculate it without this brute force solution. If there is, it must surely be a smaller number of possibilities than if they're all unlocked immediately.

Brute-force code

I know I'm in the wrong community for this, but I'm mostly familiar with PHP, so I did it this way 😉

Here's the code that gave me the results as above:

<?php
$challenges = [
    100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
    250, 250, 250, 250, 250, 250, 250, 250, 250, 250,
    500, 500, 500, 500, 500, 500, 500, 500, 500, 500,
    1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
];

$permutations = [];
$scores = [];

for ($i = 0; $i < 100000; $i++) {
    shuffle($challenges);
    $key = implode('', $challenges);
    $permutations[$key] = isset($permutations[$key]) ? $permutations[$key] + 1 : 1;
    $score = 0;
    foreach ($challenges as $challenge) {
        $score += $challenge;
        $scores[$score] = isset($scores[$score]) ? $scores[$score] + 1 : 1;
    }
}

ksort($scores);

echo "\nUnique permutations generated: " . count($permutations);
echo "\nUnique scores found: " . count($scores) . "\n\n";
echo "Score\tCount\n";
foreach ($scores as $score => $count) {
    echo "{$score}\t{$count}\n";
}
echo "\n";

foreach ($permutations as $key => $count) {
    if ($count > 1) {
        echo "\nPermutation occurred {$count} times: " . $key;
    }
}

That last loop over the permutations, looking for one that appeared twice, is purely to satisfy my curiosity, and has (thus far) never resulted in any output, because the shuffles are always unique. I'm sure they wouldn't be if I looped more times.

And here you can see a run on 3V4L.org.

Thank you all for taking a look.

Best Answer

In the interest of keeping the arithmetic simpler, I'll divide all scores by 50. So you have 10 questions worth each of 2, 5, 10, and 20 points.

The maximum possible score is therefore $10 \times (2 + 5 + 10 + 20) = 10 \times 37 = 370$. (In the initial scoring that's $18500$, as you've already identified.) But you can never have 1 point or 3 points in the new scoring (50 or 150 in the initial scoring) - the only way to have an odd score is to score a 5, but then you'll already be past 3. Similarly, you can never have 1 or 3 points less than the maximum (that is, 369 or 367) because then you would have to have done all the challenges except 1 or 3 points' worth, which isn't possible. Every other score is possible.

So the possible scores are the integers from 0 to 370, except 0, 1, 3, 367, and 369 - there are $371 - 5 = 366$ of those. (I say 0 isn't allowed but 370 is because that's what your code does.)

Related Question