December 2020
 

[URL="https://www.research.ibm.com/haifa/ponderthis/challenges/December2020.html"]December 2020.[/URL]

Error in example?
 

134 160 206 235 265 = 1000 and not 1001

I think the correct numnber should be 134 161 206 235 265

[QUOTE=tgan;564911]134 160 206 235 265 = 1000 and not 1001

I think the correct numnber should be 134 161 206 235 265[/QUOTE]

And [50, 60, 77, 88, 99] only 99 is odd

Yep, you are right on both counts. They will probably correct it later.
I fixed your first post (runaway link).

I count 67 unique solutions. :confused:

Have puzzles in the past had multiple solutions, or did I just make a mistake somewhere?

[QUOTE=retina;564929]I count 67 unique solutions. :confused:

Have puzzles in the past had multiple solutions, or did I just make a mistake somewhere?[/QUOTE]

I think it is possible
must admit that i did not totally understood the puzzle. do we look for a maximum or we need to get the required number?

[QUOTE=retina;564929]I count 67 unique solutions. :confused:

Have puzzles in the past had multiple solutions, or did I just make a mistake somewhere?[/QUOTE]I remember past puzzles with many answers. A few were "special" and gained extra credit. Special, such that a name may appear or a palindromic answer, etc. within the solutions.

I don't see anything about "the" solution being unique, so why not multiple solutions? I'm not sure exactly what "67 'unique' solutions" means; it seems like an oxymoron. I'm guessing "unique" refers to a specific ordering of the 5 population numbers, so you don't have two solutions with the same five population numbers.

Nonuniqueness of solutions is no major defect, but geez -- they can't even give a proper example. Pathetic.

Struggling to derive an interesting puzzle from the conditions...

It occurred to me to wonder how many ways there are of expressing 1001 as the sum of 5 odd positive integers.

Subtracting 1 from each summand gives 5 non-negative even integers.

Dividing through by 2, we have the the problem of expressing 498 as the sum of 5 non-negative integers.

This is well-known to be equal to the number of ways of expressing 498 as the sum

498 = x[sub]1[/sub] + 2*x[sub]2[/sub] + 3*x[sub]3[/sub] + 4*x[sub]4[/sub] + 5*x[sub]5[/sub]

where the x's are non-negative integers; the corresponding 5 summands of 498 are

x[sub]5[/sub], x[sub]5[/sub] + x[sub]4[/sub], x[sub]5[/sub] + x[sub]4[/sub] + x[sub]3[/sub], x[sub]5[/sub] + x[sub]4[/sub] + x[sub]3[/sub] + x[sub]2[/sub], and x[sub]5[/sub] + x[sub]4[/sub] + x[sub]3[/sub] + x[sub]2[/sub] + x[sub]1[/sub].

The number of such 5-tuples is approximately the volume of the 5-dimensional "simplex" in Euclidean 5-space bounded by the coordinate axes and the hyperplane given by the above equation.

This volume is 498^5/(5!*5!), which is approximately 2,000,000,000.

[QUOTE=Dr Sardonicus;564939]I don't see anything about "the" solution being unique, so why not multiple solutions? I'm not sure exactly what "67 'unique' solutions" means; it seems like an oxymoron. I'm guessing "unique" refers to a specific ordering of the 5 population numbers, so you don't have two solutions with the same five population numbers.[/QUOTE]If you ignore the ordering, and just consider the raw population counts, then 67 results. If you account for the ordering then a lot more than 67 results.

I only included odd population numbers, as the puzzle says. But the example has even numbers. So I'm not sure what to make of that.

It all seems a bit muddled with the errors and non-conforming examples.

Upon rereading the problem, I find I hadn't been reading it correctly. I think I have it now, but if so I have a major difficulty with it.

A component p[sub]i[/sub] of the vector pop is the numbers of eligible voters in state i. The hypothesis that all the v[sub]i[/sub] are odd insures that there can't be a tie at the ballot box in any state. The corresponding component v[sub]i[/sub] of the vote is the number of votes a candidate got in state i.

Therefore v[sub]i[/sub] <= p[sub]i[/sub], and if 2*v[sub]i[/sub] < p[sub]i[/sub], then the other candidate gets all that state's electors.

OK, the grand total number of electors is given to be 1001. Here is the difficulty I have with that: Both in the example with the non-conforming vector pop and erroneous computation with only 1000 electors being assigned, and in the vector pop in the puzzle itself,

[i][b]the number of electors is greater than the number of eligible voters![/b][/i]

:ermm: :confused: :confused2: :shock:

[QUOTE=retina;564977]It all seems a bit muddled [/QUOTE]
Of course, what did you expect? It is about elections... :razz:

[QUOTE=tgan;564933]must admit that i did not totally understood the puzzle. do we look for a maximum or we need to get the required number?[/QUOTE]The way I understood it was to simply generate a set of populations, compute what is the most number of votes achievable and still lose on the electors count, then see if the total votes divided by the total population is the given number.

There are solutions to give both higher percentages and lower percentages, so those can be eliminated quickly.

Indeed the given percentage is very specific, and that is why it was easy to find the answers. It could also be done by hand if one were so inclined, it wouldn't take very long at all.

Agree from this part of the world, if you limit your pi's to [100,150], there are about 350 millions (51^5) possibilities in the whole search space, so a brute force is quite fast, without any "intelligence" behind. Write a pari line with 5 for or while loops one inside the other and forget it for a while (pun intended).
(Edit: I considered that the "odd pi" trick is there only to ensure there is no "tie" in voting, but as long as there is no tie, the even numbers work as well, that is why I said 51, and not 25).

:snipe:[QUOTE=retina;565011]The way I understood it was to simply generate a set of populations, compute what is the most number of votes achievable and still lose on the electors count, then see if the total votes divided by the total population is the given number.

There are solutions to give both higher percentages and lower percentages, so those can be eliminated quickly.

Indeed the given percentage is very specific, and that is why it was easy to find the answers. It could also be done by hand if one were so inclined, it wouldn't take very long at all.[/QUOTE]

Thanks for your explanation now I understand the puzzle

[QUOTE=LaurV;565016]Agree from this part of the world, if you limit your pi's to [100,150], there are about 350 millions (51^5) possibilities in the whole search space, so a brute force is quite fast, without any "intelligence" behind. Write a pari line with 5 for or while loops one inside the other and forget it for a while (pun intended).
(Edit: I considered that the "odd pi" trick is there only to ensure there is no "tie" in voting, but as long as there is no tie, the even numbers work as well, that is why I said 51, and not 25).[/QUOTE]I tried your suggestion of including even population counts (but not your suggestion of 5 nested while loops).

And I find 1336 results.

Also, I now find 104 results for the original puzzle, after seeing that I did indeed have a mistake.

And curiously these results are the same for both 1000 and 1001 electors, so the error in the definition statement makes no difference.

[QUOTE=retina;565011]The way I understood it was to simply generate a set of populations, compute what is the most number of votes achievable and still lose on the electors count, then see if the total votes divided by the total population is the given number.[/quote]And there's an obvious way to insure the maximum number of votes to win the electors of a given set of states.

[quote]Indeed the given percentage is very specific, and that is why it was easy to find the answers. It could also be done by hand if one were so inclined, it wouldn't take very long at all.[/QUOTE]Curious they didn't ask for the maximum percentage.

One of the present-day complications in the US presidential election system is that Maine and Nebraska do [i]not[/i] assign electors by "winner take all."

Possibly the most undemocratic US presidential election was that of 1824. According to [url=https://www.history.com/this-day-in-history/presidential-election-decided-in-the-house]History.com[/url],[quote]Andrew Jackson of Tennessee won 99 electoral and 153,544 popular votes; John Quincy Adams of Massachusetts received 84 electoral and 108,740 popular votes[/quote]No majority in the Electoral College, so for the second time in US history (the first being the election of 1800), the election went to the House of Representatives. Henry Clay, who had come in fourth in electoral votes, was out of the running. But he helped Adams, and so John Quincy Adams became President, despite Jackson's lopsided win in the popular vote.

Then there was the election of 1876...

[QUOTE=Dr Sardonicus;565046]Curious they didn't ask for the maximum percentage.[/QUOTE]
Because that's trivial. [SPOILER] 74.5424292845258 for odds, and 74.6268656716418 when evens are included too, due to the fact that you can make the "won" electorates 150, while in the first case you can only make them 149, so you got a bit higher percentage[/SPOILER]
You only need pencil, paper, and 3 minutes to find that out.

[QUOTE=retina;565025]I tried your suggestion of including even population counts (but not your suggestion of 5 nested while loops).[/QUOTE]
Well, I put those 5 loops in excel, with calculation of the maximal losing vote in the innermost one, which makes it 6 nested loops :razz:, because that calculation (the stupidest implementation possible, also brute force) is also a "for loop" from 1 to 31 where each bit 1 shows the electorate you lost, and the excel "macro" goes through all possible population combinations in less than a minute, in spite of such a slow, interpreted, excel VBA. [SPOILER]Because the search space is much smaller than what I said yesterday, if you keep the population vector always sorted (i.e. for p1=100 to 150, for p2=p1 to 150, for p3=p2 to 150, etc). When you step only through the odd numbers, for example, there are only Combin(25,5)*31=1674030, versus 350 millions that I was blabbing yesterday. [/SPOILER]

Has anyone a link to a list of the number of eligible voters for each state of the USA and to the real-world non-simplified formula, how the electors are computed?
I found a list, how many voters voted in each state, but I guess that we shall use the number of eligible voters.
Or is that the real task?

[QUOTE=Dieter;565130]Has anyone a link to a list of the number of eligible voters for each state of the USA and to the real-world non-simplified formula, how the electors are computed?
I found a list, how many voters voted in each state, but I guess that we shall use the number of eligible voters.
Or is that the real task?[/QUOTE]Number of presidential electors is easy: for each State, add the number of Senators (2) to the number of US Representatives. Constitution of the United States, Article II, Section 1, Clause 2:

[quote]Each State shall appoint, in such Manner as the Legislature thereof may direct, a Number of Electors, equal to the whole Number of Senators and Representatives to which the State may be entitled in the Congress: but no Senator or Representative, or Person holding an Office of Trust or Profit under the United States, shall be appointed an Elector.[/quote]

Clause 3, the way the Electoral College actually [i]selects[/i] the president and vice-president, was superseded by the Twelfth Amendment in the wake of the election of 1800. Some of it, in turn, was changed by the Twentieth Amendment, AKA the "Lame Duck Amendment," which set Inauguration Day as January 20, and the day the new session of Congress begins.

Each State's electors are assigned according to State law. In all but Nebraska and Maine, the rule is "winner take all." Nebraska and Maine divide the electors to reflect the popular vote, but I don't know the formula.

As to [i]eligible[/i] voters, the basic requirement is citizenship, and the age requirement is at least 18, by the Twenty-Sixth Amendment. Some (natural-born or naturalized) US citizens who are [i]old[/i] enough to vote are ineligible because e.g. they are convicted felons.

In order to cast a ballot, an otherwise eligible voter has to [i]register[/i] to vote. This part of the process allows States to prevent otherwise eligible people from voting because they are not rich enough, not white enough, or not Republican enough. The number of [i]registered[/i] voters in each State is probably available on line. You might try the US Census or ballotpedia,org

[b]EDIT:[/b] This [url=https://ballotpedia.org/Voter_registration]Ballotpedia page[/url] has a table of registered voters by state as of 2018.

[QUOTE=Dr Sardonicus;565133]Each State's electors are assigned according to State law. In all but Nebraska and Maine, the rule is "winner take all." Nebraska and Maine divide the electors to reflect the popular vote, but I don't know the formula.[/QUOTE]
Nebraska and Maine allot 1 elector per congressional district (most votes in that district determines who gets that elector) and then the 2 remaining electors "at-large" are assigned based on who got the most votes in the state.

Adding my solution here since the month is over:

This was quite an easy problem, with a straightforward solution that requires no programming either.

That each state is between 100 and 150 population means that the candidate that wins 3 states is always the overall winner (wins states with at least 303 votes, opponent at most 298 - the details of the elector stuff can never matter). Maximal loss in this setup means getting every vote in the 2 biggest states, and maximum non-winning amount in the 3 smallest.

The only possible ratio within the given population sizes that is close to 71.781305% is 405/567 (as you can see with standard rational approximation, or just an exhaustive search). So the total population is 567, and the loser gets 405 votes.

The winning candidate gets 567-407=160 votes. In a minimal win, he gets (population+1)/2 votes in each of the smallest 3 states. So (p1+p2+p3+3)/2=160, and p1+p2+p3=317. Any state sizes where the sum of the 3 smallest is 317 and total population is 567 are a valid solution.