4
$\begingroup$

I go to a very fair university that likes to make sure that every student gets their best shot. One way they ensure this is by their rounding system. The rules are as follows:

  • All marks for all pieces of work are out of 100
  • Any marks that are within 1.5 of a multiple of ten can be rounded up to the nearest multiple of ten.
  • Sets of marks can be averaged to give a new mark. These new average marks can then be rounded up and averaged with other marks.
  • In the end the student gets a single mark which is formed by the repeated averaging and rounding up process.

Using this system it is possible that the final mark awarded is quite a lot of larger than the average of all the marks.

For example, if a student only gets one mark and it is 68.5, this can be rounded up to 70. This is 1.5 larger than the normal average (of only one mark).

If a student gets two marks which are 38.5 and 77, then the 38.5 can be rounded up to 40 and then the 40 and 77 can be averaged to give 58.5 which can in turn by rounded up to 60. The average of 38.5 and 77 would have been 57.75 so 60 is 2.25 larger than this average.

This question is this: for each number of pieces of work from 2 upwards, what is the largest gap that one can achieve between the normal average and this repeated rounding up average?

$\endgroup$
10
  • $\begingroup$ Are you aware of a "nice"/"clever" answer to this? $\endgroup$
    – bobble
    Commented Jan 5, 2023 at 21:28
  • $\begingroup$ @bobble For some definition of clever/nice :) $\endgroup$
    – Simd
    Commented Jan 5, 2023 at 21:36
  • $\begingroup$ Are the averaged sets weighted by how many pieces of work they contain? For instance, if you receive a 40, a 60, and an 80, can you average the first two to 50 and then average with the last to achieve a 65, or is the result still 60 because the set of the first two is weighted more heavily? $\endgroup$
    – Sneftel
    Commented Jan 5, 2023 at 21:59
  • $\begingroup$ @Sneftel no they aren't weighted. You just take plain averages. So the result in your example is 65. $\endgroup$
    – Simd
    Commented Jan 5, 2023 at 22:00
  • 1
    $\begingroup$ @KrisVanBael nothing is ever rounded down. Think of the students! $\endgroup$
    – Simd
    Commented Jan 6, 2023 at 7:09

5 Answers 5

5
$\begingroup$

Ignoring rounding, it is best to average the lowest 2; then average with the next lowest; etc. The contribution of the Nth-highest grade is then 0.5^n, while it contibutes 1/n to the normal average.
Thus a grade nust be as high as possible if 0.5^n> 1/n , and as high as possible otherwise.
Optimal solution without rounding:
grade(m) = 100 if m <= 2log(n)
grade(m) = 0 if m > 2log(n)

The effect of rounding: Rounding the lower grades upwards (to 10) does not help at all since that requires >!a total of at least 17 to allow 10 less for 1 of the high numbers.
Rounding the high numbers upwards does help - they should be at most 98.5 (for an immediate rounding to 100)

the first used one however round with 0 thus 97 can be used to get rounding to 50.
averaging does not get close enough to a multiple of 60,70,80,90 again so the optimal solution for small n is:
grade(m) = 0 for m > some critical point c
grade(m) = 97 for c
grade(m) = 98.5 m < c
moving c one up
- increases the final grade by 100 * 0.5^c
- increases the average by 98.5/n

grade(m) = 97 for the largest m < 2log(n/0.985)
grade(m) = 98.5 for smaller m
grade(m) = 0 for larger m

The 7th high/low averages move the grade within 1.5% of 100 , so 7 nonzero numbers >!are able to reach it.
To reach it we can work backwards to find what is needed.

with using Q = 98.5 and () is rounding
100 = (Q)
((Q) + 97) =
((Q)+ ((Q)+94)) =
((Q)+ (((Q)+((Q)+88))) =
((Q)+ (((Q)+((Q)+((Q)+76)))) =
((Q)+ (((Q)+((Q)+((Q)+((Q)+52))))) =
((Q)+ (((Q)+((Q)+((Q)+((Q)+((Q)+4)))))) =
((Q)+ (((Q)+((Q)+((Q)+((Q)+((Q)+(8+0)))))))

8+6Q = 599, which is the minimum needed to reach 100 with large n

so the gain is max(100 - 599/n , 100 - 97/n -(2log|n/0.985|-1)*98.5/n)
Note I corrected an earlier mistake (forgot the -1)

the switch is at
2log|n/0.985|-1 < 502/98.5 n = 0.985 * 2^(502/98.5+1) = 67.4


Final answer: (for n>2) the gain is:
100 - 599/n for n>67
100 - 97/n -(2log|n/0.985|-1)*98.5/n for 2<n<66
For n =1, 1 rounding can give +1.5. For n = 2, 2 roundings, e.g. (47,(68.5))->60, can give +2.25.
3 to 10:
{0,0,97} 50-32.333 = 17.666
{0,0,97,98.5} 75-391/8 =26.125
{0,0,0,97,98.5} 75-391/10 = 35.9
{0,0,0,0,97,98.5} 75-391/12 = 42.42
{0,0,0,0,0,97,98.5} 75-391/14 = 47.07
{0,0,0,0,0,97,98.5,98.5} 87.5-294/8 = 50.75
{0,0,0,0,0,0,97,98.5,98.5} 87.5-294/9 = 54.83
{0,0,0,0,0,0,0,97,98.5,98.5} 87.5-29.4 = 58.1

$\endgroup$
8
  • $\begingroup$ What do you get for 3,...,10 pieces of work? $\endgroup$
    – Simd
    Commented Jan 6, 2023 at 14:28
  • $\begingroup$ @Simd Added to the answer (after fixing mistake) $\endgroup$
    – Retudin
    Commented Jan 6, 2023 at 15:28
  • 1
    $\begingroup$ Jaap gives (0,0,74,98.5) with a gain of 26.875, larger than your 26.125. $\endgroup$
    – justhalf
    Commented Jan 6, 2023 at 16:34
  • $\begingroup$ Missed that; that might also work for 8,16,32.. then, since they are so 'instable', e.g. {0,0,0,0,0,28,98.5,98.5} 80-225/8 = 51.875 $\endgroup$
    – Retudin
    Commented Jan 6, 2023 at 17:12
  • $\begingroup$ I worked it out, it only works for a few more n (8, 16, and 128, and nothing else). Basically the final average will increase by 10 each time we found configuration for higher n that works. For n=128, this will give final average of 100 already, so we can't continue the pattern. So for those n, Jaap's construction is optimal, otherwise, I believe yours is optimal. (see my comment to Jaap's under Gareth's answer for details) $\endgroup$
    – justhalf
    Commented Jan 6, 2023 at 17:43
4
$\begingroup$

Partial answer (I have a pretty good lower bound; it may in fact happen to be exact, but I don't have a proof of that; but it's bedtime):

There are

two separate modes of mark-inflation here. One is the rounding; the other is the fact that averages of averages are not necessarily averages. So, e.g., suppose a student has marks of 20, 40, 60. They can average 20 and 40 to get 30, and average this with 60 to get 45. No rounding involved at all, but they have gained 5 points just by "changing the weightings".

Now, let's first note that

a student never has reason to average groups larger than 2. Any time you would have done (a+b+c)/3, for instance, you can do ((a+b)/2+c)/2 where c is the best of the three marks; without rounding, this is never worse because it gives more weight to c and less to a,b; the extra "inner" rounding in the latter case can't make things worse; and then the final rounding step is applied to a number at least as large in the second case, and hence produces a number at least as large in the second case. All of this obviously generalizes to groups larger than 3.

So now let's consider

the possible "grouping trees" a student can construct. The leaves of each tree are the individual marks; then each time the student combines two marks two nodes get a new parent; the last such parent constructed, corresponding to the final averaging, is the root of the tree. The leaves are labelled with the original marks; the other nodes are labelled with the results of the averaging-and-rounding operations that created them; so the root is labelled with the final mark. In what follows we'll write (ab) for the result of averaging-and-rounding a,b; a,b might be original marks (leaf nodes) or already-averaged marks (non-leaf nodes). Bits of tree larger than one node together with its children will have notations like ((a(bc))d), meaning that we average-and-round b,c; then we average-and-round a together with that; then we average-and-round that together with d. Of course (ba) = (ab).

We'll try to

limit the trees that need to be considered as candidates for the best tree for a given set of original marks, by finding patterns of grouping such that some other grouping is definitely no worse. So, suppose we have the pattern ((ab)c), where c is not the largest of a,b,c. The order of a,b doesn't matter, so let's suppose a>=b and a>=c. Then I claim (a(bc)) >= ((ab)c). Why? Well, write R() for the rounding operation; I'm claiming R((a+R((b+c)/2))/2) >= R((R((a+b)/2)+c)/2); since R is monotonic this will be true if a+R((b+c)/2) >= R((a+b)/2)+c; suppose R adds an amount h to (a+b)/2 and an amount k to (b+c)/2; then I am claiming a+b/2+c/2+k >= a/2+b/2+h+c or (a+b)/2 - (b+c)/2 >= h-k; in other words, I am claiming that the amount by which (a+b)/2 is bigger than (b+c)/2 is at least the amount more by which it's rounded up. Is that right? Well, since (a+b)/2 >= (b+c)/2, if it is rounded up more it must be to a strictly bigger value, which means that its unrounded advantage must be at least 10 - 1.5; but its rounding advantage can't be bigger than 1.5, which is definitely smaller. On the other hand, if (a+b)/2 isn't rounded up more, i.e., if h-k <= 0, then trivially (a+b)/2 - (b+c)/2 >= h-k. So this is true either way, which is what we needed. We have proved that (a(bc)) >= ((ab)c) if a is the largest of a,b,c.

Now

consider the largest of the original marks. (Call it z.) At some point it must get averaged with something, giving (yz); y may or may not be one of the original marks. If we ever average that with something else, giving (x(yz)), then we know that ((xy)z) would have been at least as good; so in a best-possible tree we can assume this never happens. In other words: the largest of our original marks first enters in at the root of the tree, when it is averaged with ... whatever we did with everything else.

But

we can apply the same logic to "everything else", showing that the largest of those is averaged in at the end; and so on recursively, with the final conclusion being that the only tree we need to consider is the one that begins by averaging the two worst papers, then averaging that result with the third-worst, etc.

Now

in the absence of rounding, we would be done. The cunningly-grouped average gives weights 2^-(n-1),2^-(n-1),2^-(n-2),2^-(n-3),...,2^(-1) to the papers, in increasing order of original mark, versus 1/n for all of them; the mean of the original marks gives weights 1/n,1/n,...,1/n; so to maximize the difference we should give each paper a mark of zero if its non-uniform weight is below 1/n and a mark of 100 if its non-uniform weight is above 1/n; the number of "good" papers will then be k=floor(log2(n)), the total cheaty mark will be (1-2^-k).100, versus k/n.100 without clever grouping, and the difference will be (1-2^(-k)-k/n).100. For instance, if n=10 then k=3 and the difference is (7/8-3/10).100 = (0.875-0.300).100 = 57.5 marks. For large enough n, the difference becomes as close as we please to the full 100 marks, though of course it never reaches that figure. (With rounding the final score will be 100 for large enough n, but the gain will never be 100 because in order to get this we do need to score some marks somewhere and so the naive average can never be 0.)

Fortunately for the student, but unfortunately for me,

there is also the rounding-up to consider. The impact of this in the k'th step from the end (where r=0 for the last step, r=1 for the step before that, etc.; there are n-1 average-and-round steps, so r ranges from 0 to n-2) is at most 1.5 times 2^-r. The total benefit of all rounding is less than 3 marks. In order to get any rounding up at all we need the pre-rounding value to be at least 8.5. It feels as if these facts should make it possible to prove that most of the marks should be exactly zero, but I haven't yet managed to get my ducks sufficiently in a row for this.

It seems like it may be difficult

to figure out the max-gain strategy in the presence of rounding, which feels as if it could complicate things a lot. But there is at least one easy thing to do: all those 100s could equally well be 98.5s, since they will immediately be rounded up to 100. And of course we should round things up at the end. So a lower bound on the maximum gain with n papers is R((1-2^-k).100) - k/n.98.5 where k=floor(log2(n)) and R is the rounding function. For instance, for n=10 the maximum gain is at least 57.95, and for n=128 the maximum gain is at least 94.61328125. But this doesn't take into account the effects of rounding at intermediate stages (a bit of simple-minded programming suggests that in fact this effect is literally zero for all n up to 10000, with the naively-optimal original marks), nor the possibility of changing our original marks in any way more sophisticated than using 98.5 instead of 100 (which I suspect doesn't actually help). So at present I suspect that the upper bound earlier in this paragraph may be tight, but I have nothing resembling a proof.

$\endgroup$
8
  • 1
    $\begingroup$ Could you set out what you get for 2…10 pieces of work please. This will be interesting and make it easier for others to compare. $\endgroup$
    – Simd
    Commented Jan 6, 2023 at 6:04
  • 1
    $\begingroup$ Based on the construction at the end, we have: 2: 98.5 98.5 (+1.5). 3: 0 0 98.5 (+17.16). 4: 0 0 98.5 98.5 (+25.75). 5: 3x0 2x98.5 (+35.6). 6: 4x0 2x98.5 (+42.17). 7: 5x0 2x98.5 (+46.86). 8: 5x0 3*98.5 (+50.56). 9: 6x0 3x98.5 (+54.67). 10: 7x0 3x98.5 (+57.95). This explicit construction doesn't produce optimal one for n=2, as we can compare with the example from the question. $\endgroup$
    – justhalf
    Commented Jan 6, 2023 at 7:22
  • $\begingroup$ There one more optimization to make. Eg. For n=10 +60.773 $\endgroup$ Commented Jan 6, 2023 at 8:45
  • 2
    $\begingroup$ For n=4, (0,0,74,98.5) and (0,0,34,98.5) give a score of 70 and 60 respectively, which is an improvement of 26.875 over the regular average, which I think is optimal. $\endgroup$ Commented Jan 6, 2023 at 10:38
  • 1
    $\begingroup$ For large n, best set I found results in a perfect 100 score, using 603.5 points in total. So eg. For n=100 the difference is 93,965. $\endgroup$ Commented Jan 6, 2023 at 11:45
1
$\begingroup$

The full solution combines several techniques from different answers.
A solution table that (I believe now) incorporates all best ones:

enter image description here

$\endgroup$
-1
$\begingroup$

The biggest gap for n pieces of work is:

2.25

Because:

The max average would be (sum(n+1.5) * 1.5) / n = sum(n) / n + n * 1.5 * 1.5 / n = 1.5 * 1.5 = 2.25 sum(n) is sum of grades for pieces of work

$\endgroup$
2
  • 4
    $\begingroup$ I believe you can get more for 3 pieces of work. $\endgroup$
    – Simd
    Commented Jan 5, 2023 at 22:12
  • $\begingroup$ Ah right, I missed that rot13(nirentvat pna or qbar zhygvcyr gvzrf) $\endgroup$
    – Jason
    Commented Jan 6, 2023 at 1:41
-1
$\begingroup$

There is a tactic (but clearly not optimal yet, as proven in the comments by Justhalf) where the bias for a set of 10 works is

40.3

And the marks are

0,0,0,0,0,0,0,0,0,97

So a true average is 9.7. But if you first average all the zeros and then combine with the last 97, then you achieve a biased score of 50.

To generalize for all set sizes

Bias = 50 - 97/n, always using the same strategy.

Because…

There are two biases to exploit: unequal weights because of the order of averaging and the special rounding rule. This strategy exploit both (but not yet optimal).

$\endgroup$
4
  • 2
    $\begingroup$ It is definitely possible to do better. For instance, for n=10 exploiting only the first of the two effects can (if I have done my calculations right) gain you 57.5 marks, which is more than your figure. $\endgroup$
    – Gareth McCaughan
    Commented Jan 5, 2023 at 23:33
  • $\begingroup$ Cool, looking forward to your answer $\endgroup$ Commented Jan 5, 2023 at 23:37
  • 1
    $\begingroup$ For completeness of Gareth's comment, to give an example of Gareth's (based on his answer), you can have 0,0,0,0,0,0,0,100,100,100. Direct average is 30, with just averaging smartly we have (((0+100)/2+100)/2)+100)/2 = 87.5. Gap of 57.5 like Gareth mentioned. $\endgroup$
    – justhalf
    Commented Jan 6, 2023 at 2:12
  • $\begingroup$ of course. (And 57.5 isn’t even optimal yet). I stand corrected. I will update my answer. $\endgroup$ Commented Jan 6, 2023 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.