# Presidential Election

Puzzling Asked on January 5, 2021

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?

Reasons:

Correct answer by Bubbler on January 5, 2021

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

Answered by RobPratt on January 5, 2021