Fence Painting
Today we'll look at an activity based on covering the integers with arithmetic sequences.
Setup
The first time I saw this idea presented was as a problem of painting fences. I haven't thought of anything better since, so I'll stick with it! Here is a motivating example.
Example
Three painters wish to paint a fence with infinitely many pickets. Each painter must paint at least one picket and two people cannot paint the same picket. The quirk is that once the \(i\)th painter has painted their first picket, they must choose an integer \(n_i\) and paint every \(n_i\)th picket going forward and backward. How can the painters paint the fence so every picket gets painted according to these rules?
If anyone chooses \(n_i=1\), then that painter paints all of the pickets, which breaks the rules. So for each painter, we must have \(n_i \geq 2\). After some fiddling around, up to relabeling the painters we'll find that we must have \(n_1 = 2, n_2 = 4, n_3 = 4\) or \(n_1 = 3, n_2 = 3, n_3 = 3\).
We'll relax some of the conditions to get a nice puzzle set, but this idea of evenly-spaced painting will be the heart of the activity. There are two implementations I've toyed with, one for beginners and one for advanced students.
For beginners, I try to use a manipulative that makes the spacing automatic. For example, a strip of paper with a row of pickets and then set of transparencies with pickets where each transparency has every \(m\)th picket colored in for some value of \(n\). Generally, you'll want \(n\) copies of each transparency overlay that have a spacing of \(n\) -- i.e., two copies where every other picket is painted, three copies where every third is painted, and so on, but it's ok to not have a full set for larger values of \(n\). If each \(n\) has a different color of paint, this can make patterns easier to pick out.
Here are some printouts, if you want to go that route. I've gone with \(42\) pickets, since it was a pretty decent fit for a standard \(8.5'' \times 11''\) sheet. All pages are meant to be cut into six strips along the horizontal lines. Page 1 is strips of fence pickets to be covered that can be printed on plain paper. Pages 2-8 are pickets with different spacings meant to be printed on transparency sheets. Here's how the solutions to the example above would look with these:
For advanced students, I'll leave the actual spacings to them. A row of dixie cups that counters can be placed in makes a pretty good medium. Again, if they have different colors of counters, this can be helpful for finding patterns that arise with different spacings. Here are some options:
Plastic bingo chips (500 for $7)
Acrylic bicone beads (2880 for $14)
Challenges
In all of these challenges, it is assumed a painter must paint evenly spaced pickets. We'll use \(100\) pickets as a proxy for infinitely many pickets. "No overlap" means two painters shouldn't end up painting the same picket, while in some challenges overlap will be allowed.
\(4\)-Painter Challenges
Can you find a way for \(4\) painters to paint the fence with no overlap? What were your spacings?
What other ways can \(4\) painters paint with no overlap? Keep track of spacings that work.
Do any of your spacing sets allow the fence to be painted with no overlap in different ways than the one you found?
If painters are allowed to overlap, what new ways can you find for \(4\) painters to paint the fence?
The spacings \(2,2,3,3\) can be used to paint the whole fence with overlap, but some of the painters will only paint pickets also painted by others! Can you find a way for \(4\) painters to paint with overlaps so that every painter can point to at least one picket that only they have painted?
\(5\)-Painter Challenges
What ways can \(5\) painters paint the fence with no overlap? Keep track of spacings that work.
What ways can \(5\) painters paint the fence with some overlaps? Keep track of spacings that work.
Find a way for \(5\) painters to paint the fence with overlap so each has at least one picket they painted alone.
Can you find a way for \(5\) painters to paint the fence (with or without overlap) so that only \(2\) painters use the same spacing?
Can you find a way for \(5\) painters to paint the fence (with or without overlap) so that every painter uses a different spacing?
Notes
This topic in number theory was popularized by Paul Erdős and these painting schemes are known as covering systems, typically described in the language of modular congruences. For the discussion below, we'll focus only on the cases where no painter only paints redundantly, which are called minimal covering systems.
The only spacings that give rise to minimal covering systems for \(3\) painters are \((2,4,4)\) and \((3,3,3)\), which were what we listed in the example.
For \(4\) painters, the \(6\) spacing sets giving rise to minimal covering systems are
\[ (2,3,3,6), (2,3,6,6), (2,4,8,8), (2,6,6,6), (3,3,6,6), (4,4,4,4) \]For \(5\) painters, we have \(19\) viable spacing sets:
\[ \begin{eqnarray*} & & (2, 3, 3, 4, 12), (2, 3, 3, 12, 12), (2, 3, 4, 6, 12), (2, 3, 4, 12, 12), (2, 3, 6, 12, 12), \\ & & (2, 4, 6, 6, 12), (2, 4, 6, 12, 12), (2, 4, 12, 12, 12), (2, 6, 6, 12, 12), (2, 8, 8, 8, 8), \\ & & (3, 3, 4, 4, 6), (3, 3, 4, 6, 12), (3, 3, 6, 12, 12), (3, 3, 9, 9, 9), (3, 4, 4, 6, 6), \\ & & (3, 6, 6, 6, 6), (4, 4, 4, 8, 8), (4, 4, 6, 6, 6), (5, 5, 5, 5, 5) \end{eqnarray*} \]- Though the problem concerns painting the integers, any pattern with spacings \((n_1,n_2,...,n_k)\) will necessarily repeat itself every \(m = \textrm{lcm}(n_1,n_2,...,n_k)\). This means that checking all of the infinitely many pickets have been painted is equivalent to examining just pickets \(1, 2, 3, ..., m\). (For the purposes of modular arithmetic, pickets \(0, 1, 2, ..., m-1\) are typically nicer.)
-
In order for a set of spacings \((n_1, n_2, ..., n_k)\) to give rise to a covering system, we must have
\[ \frac{1}{n_1} + \frac{1}{n_2} + ... + \frac{1}{n_k} \geq 1. \]In the case of a covering system with
\[ \frac{1}{n_1} + \frac{1}{n_2} + ... + \frac{1}{n_k} = 1, \]there must be no overlaps. However, given a collection of numbers \((n_1, n_2, ..., n_k)\) that satisfy the above inequality, there's no guarantee it can be used to generate a covering system. For example,
\[ \frac{1}{2} + \frac{1}{3} + \frac{1}{3} > 1, \]but \((2,3,3)\) can't be made into a covering system. Similarly, \((2,3,6)\) seems like it could be spacings for a covering system with no overlaps, since
\[ \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1, \]but they actually can't be arranged into a covering system.
-
If two of the spacing values are relatively prime, there will necessarily be overlap. On the other hand, if \(\gcd(n_i,n_j) = d > 1\), then considering the covering system with \(d\) copies of pickets spaced \(d\) apart, we could paint so the pickets spaced \(n_i\) apart are a subset of one of them and the pickets spaced \(n_j\) apart are a subset of another.
Extra Challenges
Increasing the number of painters gives the most natural extension. First, focus on covering systems with no overlap. Then with overlap, but minimal. There are a number of conjectures that students can make and explore. For example, it can be proven that any covering system without overlaps must include at least two copies of its biggest spacing. Students may also notice some patterns in divisibility. Does every cover have some spacing that divides another? If a prime divides a spacing, can you predict how many other spacings it will divide?
An \(m\)-cover is a covering system where every picket gets painted at least \(m\) times. It's quite a bit more challenging, but students might like to look for a \(2\)-covering that is minimal in the sense that it's not just a superposition of two \(1\)-covers.
Comments
Post a Comment