Flood

I stumbled upon a game called Flood. It's a simple enough game. You start with a grid of random colors. Then, you change the color of contiguous region formed from the upper left corner until you have flooded the entire grid with one color. I wrote some code and have been tinkering around some. 

The most naive solver is a breadth first search. So, I did that. Below you see the solution length for a grid size of varying size with only three colors.

This search breaks down at large grid size because it's so slow. Some kind of heuristic approach would perform better, but can you prove it's within some epsilon of optimal? What is the expected optimal solution length? I think that should be proveable theoretically since you just have a uniform grid and can constrain the growth rate. I will likely return and do that. 

The Value of a Peer-Reviewed Activity

This week, we have been talking about proof writing in the discrete mathematics course I'm teaching. Yesterday, I started class by having students answer how confident they are about their proof writing skills on a scale of 1 to 10, 1 being "clueless and not sure where to start", 5 being "Okay and ready for homework," and 10 being "I can do most any proof you throw at me with ease." I then had them individually complete three proofs in 15 minutes.

Many students struggled with Problem 2 because they are not comfortable with sequence notation. Some misunderstood Problem 3 and tried proving something completely different than intended. After 15 minutes, they traded papers (with anonymous codes instead of their names so there was no embarrassment) and reviewed each someone else's papers as we went over them in class. They wrote some lovely, encouraging comments to each other. For example, one student had no idea of what to do on the second problem so they left it blank and their reviewer wrote, "Bet you can do it now! :D." Others noted where the proof failed and wrote a comment that they too had that difficulty. It's refreshing to see such kindness. Finally, they took the same survey about their proof writing again and there were dramatic changes in confidence.

Many more students were confident in their abilities. I'm not sure who the one who reported 1 after the exercise is. I hope they come to office hours.

This is in no way a rigorous test, but students expressed they learned more from this exercise because it forced them to think about the material instead of just going through the proof together on the board. I imagine there is a psychological benefit of seeing how someone else is doing too and being kind to them in written comments. It was also suggested that I do a problem example in class without proving it before class so students could hear my raw thought process first hand. I'll have to think about that. I like being prepared, but I'm sure I could find some way to do that.

In-class assignment collection

I have been quite busy and not prioritized logging work here; it was fairly new so it never became a habit. I'm teaching a course in Discrete Mathematics right now, the first class I've ever been the instructor. It's exciting. I have many things to learn, but I believe it's going well.

One trick that someone suggested to me is to have students try and solve a problem, write down their solution, and then hand it in with their name on it. It serves two purposes: you get a record of attendance and also get to glance through the work and gauge student progress. I award 3 points of quiz credit regardless of whether they answered correctly as an incentive to attend class. It's a little thing I might never have thought of, but it seems very effective.

Ulam–Warburton automaton inquiry: Part 1

The Ulam-Warburton automaton is a simple growing pattern. See Wikipedia or this great Numberphile video for more information. For the more technical see this paper too.

Ulam-Warburton animation from Wikipedia

I was curious what you'd get under various other versions of it, using the same basic rule of "turn on cells with exactly one neighbor" but with a tweak. For example, what happens if you a cell turns off after being activated for a few cycles?

You get this beautiful modification. I plan to follow this up more and will make code available then (although it's insanely simple). I would be curious what statements you can make about the periodicity and the number of active cells at any time. 

For example, empirically it seems that the number of cells in a "dying" version is always upper bounded by the ageless and standard Ulam-Warburton Automaton. Now, prove that and derive formulas (or prove it's not possible) for a generalized version. 

Other ideas:

• How does the total cell count formula change depending on the starting configuration, e.g. more than one active cell? 
• Are there interesting stochastic versions? 
• What happens when cells have a regeneration period, a time after they die before they can activate again? That models disease and other phenomena better maybe since resources/population has to restore before a new outbreak is successful. 
• What if the age of a cell is a function of its position on the plane? 
• Can we generalize to other grid types? 
• How does this fit into other work? Has it already been done? 

This whole curiosity partially started because I wanted to assign a simple proof about Ulam-Warburton to my summer discrete math class. I also have an affinity for fractals, who doesn't?