4
$\begingroup$

The Roman Empire is at war with Carthage. Hannibal's army is composed of $a$ archers, $b$ ballistae, $c$ cavalrymen, $d$ dart-shooters, $e$ elephants and $f$ fighters.

  • In each round of the battle, Scipio chooses some categories of enemy troops (between those listed above) and destroys 1 unit from each of the selected groups.
  • Immediately after these units get destroyed, Hannibal restores his army with 1 unit in each of the non-attacked (in the same round) categories.

For example, if Scipio defeats 1 ballista and 1 elephant, Hannibal will displace 1 new archer, 1 cavalryman, 1 dart-shooter and 1 fighter. Of course, Scipio may also decide not to attack anything, but that might not be the best way to win the war!

Given $a,b,c,d,e,f$ can you determine the minimum number of Carthaginian troops that Scipio can leave on the combat field? Also, what's the minimum number of rounds needed to achieve such result?

For example, if $a,b,c,d,e,f$ are all equal to 6, Scipio can easily remove one element from all categories per round and leave Hannibal with 0 troops after 6 rounds.

Note: Scipio can't choose to attack a unit of a category with 0 elements. If he does, he automatically loses his honour and, consequently, the war.

Improve this question
$\endgroup$
2
  • $\begingroup$ Carthago? Is that like Carthage but more Spanish/Italian? ;-) $\endgroup$
    – Rand al'Thor
    May 3, 2015 at 19:16
  • $\begingroup$ @randal'thor I've edited. Carthago is the Latin name, forgot to translate it in English eheh $\endgroup$
    – leoll2
    May 3, 2015 at 19:19

2 Answers 2

Reset to default
4
$\begingroup$

Scipio can always reduce each section of Hannibal's army to number at most 1, and the entire army to number at most 3.

Proof

If $a$ to $f$ are all equal to the same number, then Scipio can annihilate them in that number of rounds (as explained in the OP). So Scipio's aim is to even out the numbers and make them all equal. He can do this as follows.

Target all sections of Hannibal's army whose numbers are either maximal or one less than maximal. That way, he can keep going until every section of Hannibal's army numbers either 1 or 0. At this stage, the only effect his attacks can have is to toggle the 1's and 0's, so he can ensure the 0's number at least as many as the 1's.

For example, let's say Hannibal starts off with $a=4,b=4,c=3,d=2,e=2,f=0$. Scipio proceeds as follows:

  • 1st round: target archers, ballistae, and cavalrymen. Then $a=3,b=3,c=2,d=3,e=3,f=1$.

  • 2nd round: target archers, ballistae, cavalrymen, dart-shooters, and elephants. Then $a=2,b=2,c=1,d=2,e=2,f=2$.

  • 3rd round: target all sections. Then $a=1,b=1,c=0,d=1,e=1,f=1$.

  • 4th round: target archers, ballistae, dart-shooters, elephants, and fighters. Then $a=0,b=0,c=1,d=0,e=0,f=0$. This is the best Scipio can do.

Improve this answer
$\endgroup$
9
  • $\begingroup$ What in the case (1,1,1,1,1,2) where the numbers between parenthesis represent a,b,c,d,e and f? $\endgroup$
    – leoll2
    May 3, 2015 at 19:25
  • $\begingroup$ @leoll2 Sorry, I was wrong at first (and I did spot it without seeing your comment!) :-) Check the updated answer - is it OK now? $\endgroup$
    – Rand al'Thor
    May 3, 2015 at 19:29
  • $\begingroup$ Bonus question (optional): given the 6 numbers, can you immediately determine the minimum troops without "simulating" the rounds? (I mean without doing the calculus, just analyzing the 6 numbers) $\endgroup$
    – leoll2
    May 3, 2015 at 19:35
  • 1
    $\begingroup$ @leoll2 Well, the parity of $a+b+c+d+e+f$ is invariant, so we can tell straight off whether the final number of troops is going to be in {1,3} or in {0,2}. $\endgroup$
    – Rand al'Thor
    May 3, 2015 at 19:49
  • 1
    $\begingroup$ You just have to count the odd and the even numbers in the initial sequence. If they're all 6 even (or odd), the minimum is 0. If you have 5 even and 1 odd (or viceversa), the minimum is 1. If you have 4 and 2, the minimum is 2. If you have 3 and 3, the minimum is 3. $\endgroup$
    – leoll2
    May 6, 2015 at 11:44
1
$\begingroup$

Let $m$ be the number of units in the largest group.

If every round Scipio attacks all groups that are not zero then after $m-1$ rounds the initially largest group (or groups) will only have one unit left.

If $m$ is an odd number then after $m-1$ rounds all groups that started with an odd number will also have one unit left. Call the number of these groups $n$.

If $m$ is an even number then after $m-1$ rounds all groups that started with an even number will also have one unit left. Call the number of these groups $n$.

If $n\gt3$ then another step is needed to minimise the total number of remaining units.

The minimum number of units that can be left on the battlefield is the smaller of $n$ and $6-n$.

Improve this answer
$\endgroup$

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.