10
$\begingroup$

As the title says, you have 15 boxes, a real number is in each, and they're ordered such that box 1 contains the lowest value, box 2 the second lowest, box 3 third lowest and so on, until box 15, which contains the highest value.

You want to be sure to pick the 5 boxes with the greatest total product, such that $$\text{box} * \text{box} * \text{box} * \text{box} * \text{box} = \text{maximum amount}$$ and you want to do this with as few operations and comparison as possible. An operation is anything like $x * x$ or $x - y$, and a comparison is anything like $a > b$. What do you do?


You want to be able to know that, no matter what set of 15 in-order (least-greatest) boxes you are given, you can follow this simple formula (whatever you come up with) to always come out with the greatest product of 5 of them. And you want to come out with the minimum total of operations + comparisons that will let you always do that.

And numbers are not necessarily distinct! And all 4 of the basic operators ($+, -, *, /$) are allowed, though I am pretty sure you will only need $*$ ;)

$\endgroup$
  • 1
    $\begingroup$ To be honest, I don't see what's the point of this question. If the boxes are ordered (and assuming we know the order) then obviously the 5 biggest numbers will produce the biggest product. If the boxes are not ordered you can't tell the answer without ordering them. $\endgroup$ – rhsquared Mar 14 '18 at 7:30
  • 1
    $\begingroup$ Wouldn't that just be a matter of picking boxes 11 - 15 since they'll have the 5 largest numbers? $\endgroup$ – Phylyp Mar 14 '18 at 7:55
  • 7
    $\begingroup$ Real numbers include negative numbers... ;) $\endgroup$ – Lily Potter Mar 14 '18 at 7:57
  • 2
    $\begingroup$ @Phylyp, not if box11 < 0 < box12. $\endgroup$ – Bass Mar 14 '18 at 7:57
  • 1
    $\begingroup$ Agree with phylyp, i think you could edit your question to include all of the extra details you mentioned here (numbers doesnt have to be distinct, what operators are allowed, etc). What i do want to know is whether we can sneak in a negative operator in there somewhere (e.g. box1 * -box2) which would trivialize the issue of negative numbers. $\endgroup$ – votbear Mar 14 '18 at 8:21
10
$\begingroup$

If we can, we must pick an even number of negative numbers. First, get the special case, where we cannot, out of the way:

if $\boxed{15} < 0$, pick $\boxed{11}\times\boxed{12}\times\boxed{13}\times\boxed{14}\times\boxed{15}$

Then we need the largest absolute value available, with the restriction that there must be an even number of negative values. So the answer is one of these:

$\boxed{11}\times\boxed{12}\times\boxed{13}\times\boxed{14}\times\boxed{15}$

$\boxed{1}\times\boxed{2}\times\boxed{13}\times\boxed{14}\times\boxed{15}$

$\boxed{1}\times\boxed{2}\times\boxed{3}\times\boxed{4}\times\boxed{15}$

Then, note that the boxes are ordered, so out of all the possible pairs of two consecutive boxes, at most one contains both a positive and a negative value. Therefore, when comparing products of two such pairs, at least one of the products is guaranteed to be non-negative, so it's safe to multiply the larger one into our solution without further checks.

So, calculate $\boxed{1}\times\boxed{2}$ and $\boxed{13}\times\boxed{14}$ and compare them. Disqualify the solution that doesn't contain the pair with the larger result.

Then, we need to compare the two remaining possibilities. Luckily, they both contain $\boxed{15}$ and the "winner" of the previous phase, and one of the possibilities contains the losing pair from the previous phase (we already know the multiplication result), so we will need to do only one more multiplication and comparison to distinguish between the two remaining cases.

So the total number of operations required for choosing the boxes is

3 multiplications and 3 comparisons.

If we want to know what the actual maximum product is, we can get that by using

two more multiplications, because we already have two of the pairwise products calculated, so we can multiply those by each other, and then multiply the result by $\boxed{15}$ to get the maximum product.

(For completeness's sake, when we detected the "all numbers negative" case, we hadn't done any multiplication yet, so in that case we can get the maximum product by using 4 multiplications.)

$\endgroup$
  • 2
    $\begingroup$ I like the box notation :-) Edit: Also, thank you for a clear explanation readable by non-math folks. $\endgroup$ – Phylyp Mar 14 '18 at 10:24
  • $\begingroup$ you do not address [15] = 0 that makes every other combination with even # of negatives greater than any product that uses box 15. $\endgroup$ – Mindwin Mar 14 '18 at 13:01
  • $\begingroup$ @Mindwin - how do you get an even number of negatives from any other combination of 5 boxes since we know all other boxes contain a negative? $\endgroup$ – Damien_The_Unbeliever Mar 14 '18 at 13:10
  • 1
    $\begingroup$ @Mindwin, we have to take exactly 5 boxes. If $\boxed{15}$ is 0, then all the numbers that aren't 0 are negative. If you want a product that is bigger than 0, you need to take 2 or 4 negative values, but the rest of the numbers you pick (there will have to be at least one) are going to be zeroes anyway -> no need for a special case. $\endgroup$ – Bass Mar 14 '18 at 13:24
5
$\begingroup$

To find out which boxes to pick I need

6 operations

Use the following strategy:

Let's call $a = x_{1} \times x_{2}, b = x_{3} \times x_{4}, c = x_{11} \times x_{12}, d = x_{13} \times x_{14}, e = x_{15}$.
The best solutions can only be case 1: $c \times d \times e$ or case 2: $a \times d \times e$ or case 3: $a \times b \times e$.

If $x_{15} < 0$ then case 1 (1 comparison needed).

Now if $a < d$ we need to check $a < c$. If true, then case 1, else case 2 (3 multiplications and 2 additional comparisons needed).
Now if $a >= d$ we need to check $b < d$. If true, then case 2, else case 3 (3 multiplications and 2 additional comparisons needed).

$\endgroup$
  • $\begingroup$ Beat you to it by all of 8 seconds :-) $\endgroup$ – Bass Mar 14 '18 at 10:43
  • $\begingroup$ @Bass Was busy writing a program to verify (I never trust my own logic). $\endgroup$ – w l Mar 14 '18 at 10:54
4
$\begingroup$

Here is what I could come up with taking into account a few samples.
Let the boxes be $x_1, x_2, ... x_{15}$ then follow the following procedure:
Step 1: if $x_{15}$ is negative then take the boxes $x_{11}, x_{12}, x_{13}, x_{14}$ and $x_{15}$ else continue to next step.
Step 2: if $x_{13}$ is negative then take the boxes $x_1, x_2, x_3, x_4$ and $x_{15}$ else continue to next step.
Step 3: if $x_{11}$ is negative then go to step 4-a else go to step 4-b.
Step 4-a: take $x_1, x_2, x_3, x_4, x_{15}$ if $(x_3*x_4) > (x_{13}*x_{14})$ else take $x_{1}, x_{2}, x_{13}, x_{14}, x_{15}$. Stop.
Step 4-b: take $x_1, x_2$ and go to step 5 if $(x_1*x_2) > (x_{11}*x_{12})$ else take $x_{11}, x_{12}, x_{13}, x_{14}, x_{15}$. Stop.
Step 5: take $x_3, x_4, x_{15}$ if $(x_3*x_4) > (x_{13}*x_{14})$ else take $x_{11}, x_{12}, x_{13}, x_{14}, x_{15}$. Stop.

Case for all negatives is trivial.
Let's see some other examples:
Example 1: All positives
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Step 1 and 2 will not satisfy. In step three, 11 is positive so we go to step 4-b. Now, $(x_1*x_2) < (x_{11}*x_{12})$ so we will take 11, 12, 13, 14, 15 for max product

Example 2: 1 positive all Negatives -14 -13 -12 -11 ... -1 1
Step 1 will not satisfy but Step 2 will as $x_{13}=-2<0$ so we take -14, -13, -12, -11, 1 which will give max product

Example 3: 4 non-negatives and other negatives
-11 -10 ... -1 0 1 2 3
Step 1 and 2 will not satisfy. In step 3, -1 is negative so we go to step 4-1. In step 4-a, we see $(x_3*x_4) > (x_{13}*x_{14})$ so we will take -11, -10, -9, -8, 3 to get the max product.

In my opinion this involves quite less number of computations, if not the least. Including every multiplication and every comparison as one operation, this takes 9 steps in worst case scenario

I have written a code in C++ to test this which can be found at https://ideone.com/pppGuD

$\endgroup$
  • $\begingroup$ Nice. I thought I saw a problem in step 2, but realized it actually works as expected :-) $\endgroup$ – Phylyp Mar 14 '18 at 9:05
  • $\begingroup$ I think we should include the minimum number of operations+comparisons we need in the worst case scenario for your formula - in this case, it's 7 (1 from step 1, 1 from step 2, 3 from step 3, and 2 from the last step (assuming we can store one of the multiplication results from step 3)) $\endgroup$ – votbear Mar 14 '18 at 9:10
  • 1
    $\begingroup$ Don't think this works. For example, in the case -14 -14 -14 -14 1 1 1 1 1 1 1 1 15 15, we end up with -14,-14,1,15,15 when a better solution is -14,-14,-14,-14,15.. $\endgroup$ – ffao Mar 14 '18 at 9:19
  • $\begingroup$ Phylip: :-) @Votbear I have added that now. Actually it would be 9 considering every comparison and multiplication as one operation $\endgroup$ – lucifer Mar 14 '18 at 9:25
  • $\begingroup$ @ffao oh! Thanks for the example. I will check how can I modify my method for properly working. $\endgroup$ – lucifer Mar 14 '18 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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