Presidential Election

Question

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?

Bubbler · Accepted Answer

I think the answer is

Reasons:

RobPratt · Answer

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

Presidential Election

2 Answers

Add your own answers!

Ask a Question