My grandmother(*) used to say: “I ask what trump is often — it shows I’m interested in the game!”
-
- Paternal grandmother. My maternal grandmother was an ACBL Life Master.
A puzzle I mused about yesterday:
Using the current Electoral College map, what outcomes (other than 0-2 and 566-567 EVs) are mathematically unattainable?
Can a candidate get 423 EVS? 17? 196? Etc. etc.
Ooops, I mean 536-537.
That’s equivalent to (one form of) the Knapsack problem, which is well-known to be a hard problem in a precise mathematical sense.
That said, there are only 50 states, and so one could brute-force the answer pretty easily. The best algorithms require (I think) 2[sup]n/2[/sup] steps, which isn’t very much for a computer. Kinda tempting, actually…
Don’t forget that Maine and Nebraska award electoral votes by district: Nebraska might split its 5 votes 3-2, 4-1, or 5-0. Because of this I’m rather certain any split of the 538 votes is possible.
I won’t provide a rigorous vote (although it would be easy to construct one) but the large number of states with only 3 or 4 votes (along with Nebraska and Maine ready to provide single votes as needed) means that any split is achieved easily.
On the remote Island of Gugu, the language of the islanders has a strange quirk. For any word, if you take any portion of the word and double it, the word still means the same thing. For for example:
The means the same as Thhe
computer means the same as computputer
elephant means the same as elephanephant
Show that kol means the same as kolokol.
Ah, the word problem for an idempotent monoid. Well,
kol = kokol (double ko) = kokolol (double ol) = kokolokolol (double okol, or, just as well, double kolo) = kolokol (un-double koko and un-double olol)
I like it![spoiler]kol => kolol
and
kolol => kolokolol
But also:
kolokol => kolokolol
kolokolol = kolokolol, so they’re the same[/spoiler]
(Ninjad by Indistinguishable, dagnabit. But I learned a new word.)
Speaking of identical adjacent substrings … here’s a famous old problem that may take much ingenuity to solve. For maximum kudos don’t be satisfied with the “usual” solution, findable via Google, but come up with a novel alternate approach!
Find an arbitrarily long string on the alphabet {a,b,c} such that no two adjacent substrings are identical.
For clarity, here’s a start which does NOT work:
abacaba…
You’ve already “painted yourself into a corner” because you must append an a, b, or c but none of them works:
abacaba****a
abacab****ab
abac****abac
This may have been too difficult a problem for a casual thread. Just find a solution via Google or ignore the problem altogether. There may be little noteworthy about the alternate solution I alluded to — it just has sentimental value to me! That solution came to me in a flash 50 years ago when I was a boy; the other identical adjacent substring problem reminded me. 
Or … find a satisfactory such arbitrarily long string in which the symbols a,b,c do NOT occur with equal (1/3, 1/3, 1/3) rates. AFAIK the existence of such is unsolved.
Well, I know some standard solutions and therefore avoided saying anything. What’s the alternate solution you have in mind?
Given a satisfactory sequence, we only need show a way to convert it into a longer satisfactory sequence, e.g. three times as long (or a little longer). Brief summary without rigorous proof follows.
Step 1) Duplicate letters that separate identical strings. For example, replace cbabcba with cbabbcba. Call this new string Z. (This string is in violation, but this is just an intermediate form; the key step follows.)
Step 2) Construct a new string c__c__c__c__c__c__ where the gaps between c’s are filled with 1, 2 or 3 letters (a or b) according as the letters in Z are a, b, or c. (Except at the very beginning of the string, there will be just one compliant way to do this.) For example, if Z = abca… (corresponding to 1,2,3,1) then the new string will be cacbacabacbc…. The gaps between c’s in the new string are of lengths 1,2,3,1.
Half a century later, I recall swinging on our backyard swing when this happy solution popped fully formed into my head. I knew it worked … and could prove that fact rigorously with much greater ease than I could now.
(Can this be adapted to get more than 33.33% c’s? I very dimly recall once randomly generating long compliant strings with well over 33.33% c’s, but very dim is the operative phrase here.)