3
$\begingroup$

This puzzle was inspired by the current 2020 US presidential election.

You are running for president in a country with 10 states. To win a state you must conduct more rallies than your opponent. Winning a state gives you some predefined number of college votes. To win the election you must obtain more college votes than your opponent. Your opponent already conducted his/her rallies as follows:

  • State A: college votes 1, opponent rallies 3
  • State B: college votes 2, opponent rallies 2
  • State C: college votes 3, opponent rallies 15
  • State D: college votes 4, opponent rallies 16
  • State E: college votes 5, opponent rallies 5
  • State F: college votes 6, opponent rallies 6
  • State G: college votes 7, opponent rallies 35
  • State H: college votes 8, opponent rallies 32
  • State I: college votes 9, opponent rallies 45
  • State J: college votes 10, opponent rallies 40

What is the least number of rallies you need run to win the election?

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm assuming I can conduct zero rallies for some of the states, and to win a state I have to conduct at least one more than the opponent's rallies. Is this correct? $\endgroup$
    – Bubbler
    Nov 4, 2020 at 4:50
  • $\begingroup$ Both assumptions are correct. $\endgroup$
    – Dmitry Kamenetsky
    Nov 4, 2020 at 4:57

2 Answers 2

Reset to default
3
$\begingroup$

I think the answer is

78 rallies, for winning in A, B, D, E, F, J.

Reasons:

Given the above solution, no other solution can use fewer rallies by winning in at least two states out of GHIJ. If I plan to win J, I need to win either ABDEF or CDEF (other sets are supersets of either one), where the former is cheaper. If I plan to win H, I need to win BCDEF, which is not cheaper than the best known solution. Winning I or G is strictly worse off than winning J or H respectively.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Correct and very fast! $\endgroup$
    – Dmitry Kamenetsky
    Nov 4, 2020 at 5:04
1
$\begingroup$

You can solve the problem via integer linear programming as follows. For state $s$, let $v_s$ and $r_s$ be the numbers of votes and rallies, respectively. Let binary decision variable $x_s$ indicate whether I win state $s$. The problem is to minimize $\sum_s (r_s+1) x_s$ subject to $$\sum_s v_s x_s \ge 1 + \sum_s v_s (1-x_s)$$ The unique optimal solution turns out to be

$x=(1, 1, 0, 1, 1, 1, 0, 0, 0, 1)$ with 78 rallies and 28 votes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Beautiful, thank you Rob! $\endgroup$
    – Dmitry Kamenetsky
    Nov 5, 2020 at 4:31

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.