# Presidential Election

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?

• 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? – Bubbler Nov 4 '20 at 4:50
• Both assumptions are correct. – Dmitry Kamenetsky Nov 4 '20 at 4:57

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.

• Correct and very fast! – Dmitry Kamenetsky Nov 4 '20 at 5:04

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.

• Beautiful, thank you Rob! – Dmitry Kamenetsky Nov 5 '20 at 4:31