Meta
Categories
 algebra (47)
 arithmetic (85)
 books (34)
 calculus (7)
 challenges (57)
 combinatorics (29)
 complex numbers (6)
 computation (82)
 convergence (9)
 counting (38)
 famous numbers (48)
 fibonacci (18)
 fractals (13)
 games (34)
 geometry (72)
 golden ratio (8)
 group theory (28)
 humor (8)
 induction (8)
 infinity (19)
 iteration (24)
 links (76)
 logic (9)
 meta (43)
 modular arithmetic (30)
 number theory (108)
 open problems (11)
 paradox (1)
 pascal's triangle (8)
 pattern (105)
 people (23)
 pictures (74)
 posts without words (39)
 primes (57)
 probability (9)
 programming (20)
 proof (91)
 puzzles (18)
 recursion (16)
 review (24)
 sequences (28)
 solutions (31)
 teaching (15)
 trig (3)
 Uncategorized (6)
 video (19)
Archives
 January 2020 (4)
 December 2019 (4)
 November 2019 (2)
 October 2019 (5)
 September 2019 (7)
 August 2019 (3)
 July 2019 (5)
 May 2019 (4)
 April 2019 (2)
 March 2019 (3)
 February 2019 (3)
 January 2019 (4)
 November 2018 (3)
 October 2018 (4)
 September 2018 (4)
 August 2018 (6)
 July 2018 (2)
 June 2018 (5)
 May 2018 (3)
 April 2018 (5)
 March 2018 (4)
 February 2018 (3)
 January 2018 (4)
 December 2017 (3)
 November 2017 (3)
 October 2017 (1)
 September 2017 (1)
 July 2017 (4)
 June 2017 (4)
 May 2017 (9)
 April 2017 (7)
 March 2017 (5)
 February 2017 (4)
 January 2017 (3)
 December 2016 (4)
 November 2016 (6)
 October 2016 (6)
 September 2016 (2)
 August 2016 (5)
 July 2016 (2)
 June 2016 (4)
 May 2016 (4)
 April 2016 (2)
 March 2016 (3)
 February 2016 (9)
 January 2016 (8)
 December 2015 (5)
 November 2015 (29)
 August 2015 (3)
 June 2015 (2)
 April 2015 (1)
 May 2014 (1)
 December 2013 (1)
 October 2013 (1)
 July 2013 (1)
 June 2013 (1)
 May 2013 (1)
 April 2013 (3)
 March 2013 (3)
 February 2013 (2)
 January 2013 (5)
 December 2012 (3)
 November 2012 (4)
 October 2012 (5)
 September 2012 (1)
 August 2012 (4)
 July 2012 (1)
 June 2012 (6)
 May 2012 (2)
 April 2012 (3)
 March 2012 (1)
 February 2012 (4)
 January 2012 (5)
 December 2011 (1)
 November 2011 (7)
 October 2011 (4)
 September 2011 (6)
 July 2011 (2)
 June 2011 (4)
 May 2011 (5)
 April 2011 (2)
 March 2011 (4)
 February 2011 (1)
 January 2011 (1)
 December 2010 (1)
 November 2010 (4)
 October 2010 (2)
 September 2010 (1)
 August 2010 (1)
 July 2010 (1)
 June 2010 (2)
 May 2010 (3)
 April 2010 (1)
 February 2010 (6)
 January 2010 (3)
 December 2009 (8)
 November 2009 (7)
 October 2009 (3)
 September 2009 (3)
 August 2009 (1)
 June 2009 (4)
 May 2009 (5)
 April 2009 (4)
 March 2009 (2)
 February 2009 (1)
 January 2009 (7)
 December 2008 (1)
 October 2008 (2)
 September 2008 (7)
 August 2008 (1)
 July 2008 (1)
 June 2008 (1)
 April 2008 (5)
 February 2008 (4)
 January 2008 (4)
 December 2007 (3)
 November 2007 (12)
 October 2007 (2)
 September 2007 (4)
 August 2007 (3)
 July 2007 (1)
 June 2007 (3)
 May 2007 (1)
 April 2007 (4)
 March 2007 (3)
 February 2007 (7)
 January 2007 (1)
 December 2006 (2)
 October 2006 (2)
 September 2006 (6)
 July 2006 (4)
 June 2006 (2)
 May 2006 (6)
 April 2006 (3)
 March 2006 (6)
Book review: Opt Art
[Disclosure of Material Connection: Princeton Press kindly provided me with a free review copy of this book. I was not required to write a positive review. The opinions expressed are my own.]
Opt Art: From Mathematical Optimization to Visual Design
Robert Bosch
Princeton University Press, 2019
I recently finished reading Robert Bosch’s new book, Opt Art. It was a quick read, both because it’s not actually that long, but also because it was fascinating and beautiful and I didn’t want to put it down!
The central theme of the book is using linear optimization (aka “linear programming”) to design and generate art. The resulting art can be simply beautiful for its own sake, or can also give us insight into underlying mathematics.
Linear optimization is something I knew about in a general sense, but after reading Bosch’s book I understand it much better—both the details of how the simplex algorithm works, and especially the various ways linear optimization can be applied. I think Bosch does a fantastic job explaining things in a way that gives real insight but doesn’t get bogged down in too much detail. (In a few places I personally wish there had been a few more details—but it’s quite possible that adding more detail would have made the book better for me but worse for a bunch of other people, i.e. it would not be a global optimum!)
Another thing the book explains really well is how the Travelling Salesman Problem (TSP) can be solved using linear optimization. I had no idea there was a connection between the two topics. I’m sure the connection is explained in great detail in the TSP book by William Cook, which I read 7 years ago, but for some reason when I read that I guess it didn’t really click. But from reading Bosch’s book I feel like I now know enough to put together the details and implement a basic TSP solver myself if I wanted to (maybe I will)!
I’m definitely inspired to use some of Bosch’s techniques to make my own artwork—if I do, I will obviously post about it here!
More on Human Randomness
In a post a few months ago I asked whether there is a way for a human to reliably generate truly random numbers. I got a lot of great responses and I think it’s worth summarizing them here!
Randomness in poker strategies
Robert Anderson noted that poker players sometimes use the second hand of a watch to introduce some randomness into their strategy. I assumed this would be something like getting a random bit based on whether the number of seconds is even or odd, but Pete McAllister chimed in to say that it is usually something more like dividing a minute into chunks, and making a decision based on which chunk the current second is in. For example, if you want to make one choice 20 percent of the time and another choice 80 percent of the time, you could just make the first choice if the second hand is between 0–12 seconds, and the other choice otherwise.
In game theory this is called a “mixed” strategy, and this kind of strategy can arise naturally as the Nash equilibrium of certain kinds of games, so it’s not surprising to me that it would show up in highlevel poker. I found conflicting advice about this online; some people were claiming that you should not use randomness when playing poker, but I did find a website that talked about implementing this kind of mixed strategy using the second hand of a watch, and it seemed to be a website with pretty highlevel poker advice.
In any case, if you have a phone or a watch with you, this does suggest some strategies for generating random numbers: for example, look at the last digit of the seconds to get a random number from 0–9, or whether it is even or odd to get a bit. Or you could just take the number of seconds directly as a random number between 0–59. Of course this only works once and then you have to wait a while before you can do it again. Also, it turns out that my phone doesn’t show seconds by default. Taking the ones digit of the minutes as a random number from 0–9 should work too, but the tens digit of the minutes seems like it’s “not random enough”, in the sense that it might be correlated with whatever it is that I’m doing.
Of course, a phone or watch counts as an “aid”, but most people tend to carry around something like this all the time, so it’s relatively practical. On the other hand, if you’re going to use a phone anyway, you should just use an app for generating random numbers.
Bodies and clothing

Naren Sundar commented that hair is pretty random, but admitted that it would be hard to measure.

Frederik suggested spitting, or throwing your shoe in the air and seeing which way the toe points when it lands. I like the shoe idea, but on the other hand it’s somewhat obtrusive to take your shoe off and throw it in the air every time you want a random bit! And what if you’re not wearing shoes? I’m also afraid I might throw my shoe in the same way every time; I’m not sure how random it would be in practice.
Minds and memorization
Kaligule suggested taking whatever song is currently running through your head, stopping it at a random point, and getting a random bit by seeing whether the number of consonants in the next word is even or odd.
This is a cool idea, and is the only proposal that really meets my criterion of generating randomness “without aids”. I think for some people it could work quite well. “Stopping at a random point” is somewhat problematic—you might be biased to stop at certain points more than others—but it’s pretty hard to know how many consonants are in a word before you count, so I’m not sure this would really bias the results that much.
Unfortunately, however, it won’t work for me because, although I do always have some kind of music running through my head, it often has no lyrics! Kaligule suggested using whether the melody goes up or down, but this is obvious (unlike number of consonants in a word) and too easy to “cheat”, i.e. pick a stopping point that gives me the bit I “want”.
This suggested another idea to me, however: just pregenerate some random data and put some upfront effort into memorizing it. Whenever you need some randomness, use the next part of the random sequence you memorized. When you use it up, generate another and memorize that instead. This leaves a number of questions:

How do you reliably keep track of where you are in the sequence? I don’t actually have a good answer to this. I think in practice I would get confused and forget whether I had already used a certain part or not. Though maybe this doesn’t really matter that much.

What format would be most effective, and how do you go about memorizing it? Some ideas:

My first idea is to generate a sequence of random bits, and then write a story where sequential words have even or odd numbers of letters corresponding to the bits in your sequence. Unfortunately, this seems like a relatively inefficient way to memorize data, but writing a story that corresponds to a given sequence of bits does sound like a fun exercise in constrained writing.

Alternatively, one could simply generate a random sequence of digits (or hexadecimal digits) and memorize them using whatever sort of memorization technique you like (e.g. a memory palace). This is less fun but probably more effective. Memorizing a story sounds like it would be easier, but I don’t think it is, especially since you would have to memorize it wordforword and you only get one bit per word memorized, as opposed to something like e.g. four bits per hexadecimal digit.

I have generated some random hexadecimal digits but haven’t gotten around to trying to memorize them yet. If I do I will definitely report on the experience. In the meantime, I’m also open to more ideas!
Book review: The Mathematics of Various Entertaining Subjects, Volume 3
I have a bunch of books in the queue to review—I hope to begin writing these more regularly again!
[Disclosure of Material Connection: Princeton Press kindly provided me with a free review copy of this book. I was not required to write a positive review. The opinions expressed are my own.]
The Mathematics of Various Entertaining Subjects, Volume 3: The Magic of Mathematics
Jennifer Beineke and Jason Rosenhouse, eds.
Princeton University Press, 2019
The MOVES conference takes place every two years in New York. MOVES is an acronym for “The Mathematics of Various Entertaining Subjects”, and the conference is a celebration of math that isn’t necessarily considered an Important Research Topic, and doesn’t necessarily have Important Applications—but simply math that is fun for its own sake. (Although in hindsight, math that starts out as Just For Fun often seems to end up with important applications too—for example, think of graph theory or probability theory.) The most recent conference took place just a few months ago, in August 2019; the next one will be in August 2021 (you can already register if you like to plan that far ahead!).
This book is basically the conference proceedings from 2017—a collection of papers that were presented at the conference, published all together in book form. So it’s important to state at the outset that although the topics are entertaining, this really is a collection of research papers. Overall this is definitely not a book written for a general audience! I had to work hard to understand some of the papers, and some of them lost me completely.
However, there’s some great stuff in here that rewards patient study. Some of my favorites that are more generally accessible include:

A chapter on “Wiggly Games and Burnside’s Lemma” that does a great job explaining Burnside’s Lemma—a classic result about counting things with symmetry, at the intersection of combinatorics and group theory—via applications to counting the number of possible tiles in several different games.

“Solving Puzzles Backwards” has some nice puzzles and a discussion of elegant ways to approach their solutions.

“Should we Call Them FlexaBands?” has some interesting reflections on the topology of different types of flexagons.
Some other things I particularly enjoyed but which are not so accessible without some background include a chapter on the computational complexity of losing at checkers, a chapter on “Kings, sages, hats, and codes” that I wish I understood better, and a chapter on the combinatorics of Legos.
There’s so much other stuff in there on such wildly varying topics that it’s impossible to summarize. In any case, definitely recommended if you are a professional mathematician looking for some fun yet still technically meaty reading; definitely not recommended if you’re looking for a casual read of a popular math book. And if you’re somewhere in between—that is, you’re not a professional mathematician but you aspire to read and understand things on that level—this could honestly be a great place to start!
A combinatorial proof: PIE a la mode!
Continuing from my last post in this series, we’re trying to show that , where is defined as
which is what we get when we start with a sequence of consecutive th powers and repeatedly take successive differences.
Recall that we defined as the set of all functions from a set of size (visualized as blue dots) to a set of size (visualized as yellow dots on top of blue dots) such that the blue dot numbered is missing. I also explained in my previous post that the functions with at least one blue dot missing from the output are exactly the “bad” functions, that is, the functions which do not correspond to a onetoone matching between the blue dots on the left and the blue dots on the right.
As an example, the function pictured above is an element of , as well as an element of . (That means it’s also an element of the intersection —this will be important later!)
Let be the set of all functions from to , and let be the set of “good” functions, that is, the subset of consisting of matchings (aka Permutations—I couldn’t use for Matchings because is already taken!) between the blue sets. We already know that the number of matchings between two sets of size , that is, , is equal to . However, let’s see if we can count them a different way.
Every function is either “good” or “bad”, so we can describe the set of good functions as what’s left over when we remove all the bad ones:
(Notice how we can’t just write , because the sets overlap! But if we union all of them we’ll get each “bad” function once.)
In other words, we want to count the functions that aren’t in any of the . But this is exactly what the Principle of InclusionExclusion (PIE) is for! PIE tells us that the size of this set is
that is, we take all possible intersections of some of the , and either add or subtract the size of each intersection depending on whether the number of sets being intersected is even or odd.
We’re getting close! To simplify this more we’ll need to figure out what those intersections look like.
Intersections
What does look like? The members of are exactly those functions which are in both and , so contains all the functions that are missing both and (and possibly other elements). Likewise, contains all the functions that are missing (at least) , , and ; and so on.
Last time we argued that , since functions from to that are missing can be put into a 11 matching with arbitrary functions from to , just by deleting or inserting element :
So what about an intersection—how big is (assuming )? By a similar argument, it must be , since we can match up each function in with a function from to : just delete or insert both elements and , like this:
Generalizing, if we have a subset and intersect all the for , we get the set of functions whose output is missing all the elements of , and we can match them up with functions from to . In formal notation,
Substituting this into the previous expression for the number of blue matchings , we get
Counting subsets
Notice that the value of depends only on the size of the subset and not on its specific elements. This makes sense: the number of functions missing some particular number of elements is the same no matter which specific elements we pick to be missing.
So for each particular size , we are adding up a bunch of copies of the same value —as many copies as there are different subsets of size . The number of subsets of size is , the number of ways of choosing exactly things out of . Therefore, if we add things up size by size instead of subset by subset, we get
But this is exactly the expression for that we came up with earlier! And since we already know this means that too.
And that’s essentially it for the proof! I think there’s still more to say about the big picture, though. In a future post I’ll wrap things up and offer some reflections on why I find this interesting and where else it might lead.
Posted in arithmetic, combinatorics, proof
Tagged consecutive, difference, function, integers, matching, powers
Leave a comment
A few words about PWW #27
The images in my last post were particular realizations of the famous Sieve of Eratosthenes. The basic idea of the sieve is to repeatedly do the following:
 Circle the next number bigger than that is not yet crossed out, call it .
 Cross out every th number after , that is, all the multiples of . These are not prime since they are multiples of .
This is an efficient way to find all the primes up to a given limit. Note that it doesn’t require doing any division or factoring, just adding. Here’s the image of the sieve again:
Some questions for you to ponder:
 Why can we always cross out multiples of each prime using parallel straight lines?
 When will the lines be vertical? When will they be diagonal?
 Is there only one way to cross out multiples of each with straight lines, or could we have chosen different lines?
 Why are the primes on the top row circled, while the rest of the primes are in boxes? What’s the difference?
And just for fun here’s the sieve diagram for , one of my favorites. Click here for a larger version.
Posted in pattern, pictures, posts without words, primes
Tagged Eratosthenes, prime, sieve
4 Comments