Maximise your gold!

Question

You met a genie. He gets $150$ magic lamps out, which are numbered from $1$ to $150$. You have to colour each lamp red or blue. After colouring, the genie will count the number of triples $T$ of magic lamps which are numbered $a,b,c$, with $a<b<c$, the magic lamps numbered $a,c$ are red and the magic lamp numbered $b$ is blue. Then the genie will give you $T$ grams of gold.

What should you do to maximise the amount of gold you get? You have to prove that it is the maximum.

Answer 1

Suppose you have $r$ red lamps and $b$ blue lamps. What order should they be put in to maximise the score?

If you put a blue lamp in a position with $x$ reds to the left and the remaining $r-x$ reds to the right, it contributes $x(r-x)$ to the score. This is maximal for $x=\frac{r}{2}$. The same holds for each blue lamp independently of the other blue lamps. Therefore the optimal arrangement with $r$ reds and $b$ blues will have the blues in the middle with $\frac{r}{2}$ red lamps on either side.

Now that we know the arrangement, how many red lamps is optimal?

The score will be $\frac{r}{2}\times(150-r)\times\frac{r}{2} = (150r^2-r^3)/4$.
The derivative is $\frac{300r-3r^2}{4}=\frac{3r(100-r)}{4}$. This is zero at $r=0$ (which is a minimum) and at $r=100$. In other words, the optimal arrangment has $50$ blues with $50$ reds on either side, and a score of $50^3=125000$.

Answer 2

Jaap (and many others) already solved the problem by calculus (and other kinds of maths), but this geometry based solution had such a nice symmetry to it that I wanted to post it anyway.

First, let's start by figuring out the general colour pattern. Given a single blue and N reds, where should we put the blue? Let's put a reds before the blue, and b reds after. Since our score is going to be "a times b", we can turn this into a geometry problem:

Maximize the area of this rectangle

The maximum is "obviously"

a square, with a = b. A longer rectangle would be thinner, and therefore have smaller area than the square. Or as the old multiplication rule says: "deviating from a square shape by 1 unit decreases the area by 1 unit". $$ (x+1)(x-1) = x^2-1$$

So the best spot for the blue lamp, and by extension, all the blue lamps is

smack in the middle of all the reds.

Then, we need to decide the number of blues we should add. Let's call it c. Each blue gives us "a times b" points, for a total of "a times b times c", so next we get to solve the exact same problem as before, except Now in 3D!

Maximize the volume of this rectangular box

As before, the intuitive answer is the correct one, and we get the maximum points with

a cube, that is, a = b = c. If a box has a non-square side, we can always make a bigger box by turning that side into a square with the same perimeter, while leaving the other dimension untouched -> the maximal box cannot have any non-square sides.

So we should put

50 blue lamps in the middle, with 50 red lamps both before and after them

for a total of

$50^3$ grams (125 kg) of gold

which, if turned into a sphere of solid gold, would be just about the size of a standard bowling ball (diameter difference < 5%), and easily heavy enough to completely crush us. Maybe that was the genie's ulterior plan? Maybe we should figure out a less effective colouring, this deal seems suspiciously good for us..

Answer 3

I'm going to shoot for a ELI10 answer (because a lot of the answers seem pretty complicated or are already assuming things not explicitly proven, such as the lamps being together in 3 lumps.)

Okay - let's say the lamps are all mixed up with no pattern. How would we figure out how much money we'd get?

Well, one easy way would be:

• Look at each blue lamp
• 1. Count the number of red lamps that are somewhere to the left
• 2. Count the number of red lamps that are somewhere to the right
• 3. Multiply those two numbers together

Something that's important: when you're looking at a blue lamp? Then the rest of the blue lamp locations don't matter at all. They could be right next to it, or far away - it doesn't affect anything at all.

So let's say we're looking at a blue lamp - and it's got 10 red lamps to the left and 20 to the right. 10x20 - that lamp is giving us 200 towards our total.

But... what if we started moving that blue lamp to the left? If we move it one spot to the left, and it swaps position with another blue lamp? Then it doesn't matter - remember, it doesn't matter where it is in relation to the other blue lamps. Swapping two blue lamps doesn't do anything, doesn't change anything. So we keep moving it to the left, and it swaps places with a red lamp.

Now there are 9 lamps on one side, and 21 on the other. 9 x 21 = 189 - we lost 11, since before we'd be getting 200 from that lamp!

Let's go the other way. Each time the blue lamp changes place with a red lamp, our amount goes up... until we get to 15 on one side and 15 on the other - the same amount on each side. There's some math we could show, but when you're multiplying numbers together that have to add up to some number? Then the way to get the largest number is to make all the numbers the same (or as close as possible). 1x9 is smaller than 3x7 is smaller than 5x5.

So let's move that blue lamp into a spot where there are an equal number of red lamps on either side of it.

And since you can move around a blue lamp without affecting the other lamps, it makes sense to do that for all the blue lamps. And when we do that? We get a bunch of red lamps on the left, a bunch of blue lamps in the middle, and then another bunch of red lamps on the right. Why? Because if there were any blue lamps outside the middle? Then we'd get more gold if we shifted those blue lamps back towards the center!

How much money would we get? Each blue lamp gives us the exact same amount of gold now - they've all got the same number of red lamps to the left and to the right - so we get:

• Number of Red Lamps on the Left
• x Number of Blue Lamps (which are all in the center)
• x Number of Red Lamps on the Right

So now it's just a question... how many blue lamps works best? Well, remember how if we're multiplying numbers together that all have to add up to a specific number, how we get the highest value? All three of those numbers need to add up to 150. So we want all three numbers to be the same: 50.

50, times 50, times 50.

So the solution is 50 red lamps on the left, 50 blue lamps in the middle, and 50 red lamps on the right.

Answer 4

We are looking to maximize the number of triples where a (red) < b (blue) < c (red)

The first realization:

The best way to group is by coloring lamps 1 though j red, j+1 through k blue, and k+1 through l red.
Which looks like: [ 1,2,3,...j | j+1,j+2,j+3,...k | k+1,k+2,k+3,...l ]

Then, we will have:

j * k * l triples

To optimize the distribution of the group, we need to:

find the maximum T, where T = j * k * l, and j + k + l = 150.
This is trivial, because in multiplication, the maximum is reached when the groups are of equal size.
Meaning: j=50, k=50, l=50
Or: lamps 1-50 are red, 51-100 are blue and 101-150 are red.

This gives us:

50^3 = 125,000

grams of gold

Answer 5

Suppose there are $R$ red lamps and $150-R$ blue.

For a given blue lamp, suppose there are $x$ red lamps earlier in the ordering (so $R-x$ later). Then that blue lamp is in $x(R-x)$ scoring triples.

Now $$x(R-x)=(R/2-(R/2-x))(R/2+(R/2-x))=R^2/4-(R/2-x)^2,$$ so this is maximised (for a fixed value of $R$) when $x$ is as close as possible to $R/2$. We can achieve this maximum for every blue lamp simultaneously by having $\lfloor R/2\rfloor$ red lamps, then $150-R$ blue lamps, then $\lceil R/2\rceil$ red lamps.

This gives a score of $(150-R)\lfloor R^2/4\rfloor\leq (150-R)R^2$. Using AM-GM with $150-R,R/2,R/2$, this is maximised when $R/2=150-R$, i.e. $R=100$. In this case since $R$ is even we attain the upper bound, so 50 red, 50 blue, 50 red is the best option.