An Alternative Ladybugs Activity

When JRMF throws a festival, some activities will invariably be more popular than others. When we introduce enough new activities, some old ones stop stacking up against the rest. While a new activity eclipsing an old one isn't a terrible problem to have, Ladybugs is currently not a fan favorite, and it is one of our more outwardly arithmetical activities. Since having a few arithmetic-forward activities in the bunch make it easier to sell our offerings as mathematical to the skeptical, we'll take a look at it as it stands and consider a reimagining.

Setup

Current Activity

The premise of Ladybugs as it currently exists is some number of ladybugs want to land on some leaves. The ladybugs are numbered either with a numeral or the equivalent number of pips and the rule is that no two ladybugs on a given leaf may have their numbers sum to a third ladybug on that same leaf. For example, it is possible to fit ladybugs numbered 1-8 on two leaves meeting this condition but not the 1-9. Some interesting extensions come about when exploring different number families like even numbers, odd numbers, multiples of 3, non-multiples of 3, multiples of 4, non-multiples of 4, and so on. The problems we've noticed, especially with younger students:

The condition that two numbers not sum to a third often gets mistaken by students as a "do sum to" condition.
It is nontrivial to check whether an arrangement satisfies the sum-free condition, and students often rely on the facilitator to check for them.
The base problem doesn't really have any deep pattern to be discovered -- it's tractable case of an interestingly tough computational problem. The interesting patterns that arise tend to be in the extensions.
We have used number tiles rather than something flashier. Something like this ladybug counting toy would be a near-perfect manipulative for our ladybug theme if it weren't so expensive, since the ladybugs are cute and have dots to aid subitizing.

We've tried sequencing the original problem in a few different ways, but nothing has quite hit the mark, so let's look at an alternative mechanism that is still based on sums but with a lower floor.

Alternative Activity

We'll use our cartoon ladybugs as stand-ins for the manipulatives, which might be number tiles, playing cards, pipped cards like in Math for Love's Tiny Polka Dot game kit, or something more custom. Ideally it will be a manipulative able to accommodate numbers up through 12 or so.

The new problem premise is that ladybugs like to hang out in groups but only when each group has exactly the same number of dots. One giant group is fine, but they like to mingle in smaller groups. (A group of one ladybug is fine!) As an example, suppose ladybugs 1-3 want to hang out in two groups. Since $ 1 + 2 = 3 $, they can do it as follows:

Here are some questions to get the ball rolling.

Decide whether each of the following is possible. If possible, give an arrangement. If not, try to explain why.

Ladybugs 1-4 want to hang out in two groups.
Ladybugs 1-4 want to hang out in three groups.
Ladybugs 1-5 want to hang out in two groups.
Ladybugs 1-5 want to hang out in three groups.
Ladybugs 1-6 want to hang out in two groups.
Ladybugs 1-6 want to hang out in three groups.
Ladybugs 1-7 want to hang out in two groups.
Ladybugs 1-7 want to hang out in three groups.
Ladybugs 1-7 want to hang out in four groups.
Ladybugs 1-8 want to hang out in two groups.
Ladybugs 1-8 want to hang out in three groups.
Ladybugs 1-8 want to hang out in four groups.

Initial Questions

This activity works as a series of puzzles, but here are some questions that will help students think a little deeper:

If ladybugs 1-$n$ want to hang out in two groups, for which $n$ is it possible?
If ladybugs 1-$n$ want to hang out in three groups, for which $n$ is it possible?
If ladybugs 1-$n$ want to hang out in four groups, for which $n$ is it possible?
Are there any patterns that help us make these groups or see why they can't be made?
What about five groups? Six groups?

Explorations

Of the twelve puzzles posed above, eight are possible and four are impossible. Here are some discoveries students might make along the way:

Students will likely stumble upon pairing highs and lows. For even $ n $, this gives a way of creating $ n/2 $ groups, as below for 1-8:

Slightly more subtle is for odd $ n $, we can have a group with just $ n $ and then pair the rest

If the total number of such pairs is even, we can split them into two groups. For example, with Ladybugs 1-15, we can turn

\[ 1+14 = 2+13 = 3+12 = 4+11 = 5+10 = 6+9 = 7+8 = 15 \]

into

\[ 1+14 + 2+13 + 3+12 + 4+11 = 5+10 + 6+9 + 7+8 + 15. \]

This provides a way to partition the ladybugs into two same-sum subsets when $n$ is even and so is $n/2$ or when $n$ is odd and $(n+1)/2$ is even. For students not yet comfortable with multiplication and division, divisibility by two can be completely framed in terms of pairing with no leftovers.

For students with some experience with multiplication and division, another piece of low-hanging fruit is combining several same-sum subsets to create a smaller number of larger same-sum subsets. We saw this above when taking a same-sum $8$-subset partition of 1-15 and turned it into a same-sum $8$-subset partition of 1-15, since $2$ divides $8$. Similarly, if we can create a same-sum $c$-subset partition of 1-$n$ and $ab = c$, we can combine these $c$ subsets into $a$ groups of $b$ to get an $a$-subset partition of 1-$n$.

For example, consider ladybugs 1-15. We can partition them into $6$ same-sum subsets:
\[ 1+2+3+4+10 = 5+15 = 6+14 = 7+13 = 8+12 = 9+11. \]
Since $6 = 2 \cdot 3$, we can easily repartition this into $2$ same-sum subsets
\[ (1+2+3+4+10) + (5+15) + (6+14) = (7+13) + (8+12) + (9+11). \]
or $3$ same-sum subsets
\[ (1+2+3+4+10) + (5+15) = (6+14) + (7+13) = (8+12) + (9+11). \]
In cases where $n$ is even but $n/2$ is odd or when $n$ is odd but $(n+1)/2$ is odd, we'll find we have some trouble creating two same-sum subsets. Students typically try to rectify this by trading ladybugs back and forth and will likely be able to arrange them so the difference between the subset sums is 1. At this point, there are a few observations they might make:
- There is a sort of "paradox" that I've seen stump people pretty regularly. If you have $100 and I have $110, if we want to have equal amounts, giving you $10 makes it so you have $110 and I have $100, creating the same gap in the other direction. A lot of people's intuition is that trading the difference should even things out whereas it's actually half the difference that does it.
- It's always the case that one group will have an odd sum while the other has an even sum. While we'll see another way to get at this fact, one way to think about it in terms of the above "paradox" is that trading a ladybug back and forth will offset the difference of the group sums by twice that ladybug's number. If one side was odd and the other even, their difference will be odd, and offsetting this by an even number results in another odd difference which must be the difference of another odd and even number. The sides that are odd and even might swap, but there will always be one of each. Since any configuration can be reached by trading in this way, if one configuration has an odd sum and an even sum, they all will!
A more sophisticated insight is to look at the numbers of the form $1 + 2 + 3 + ... + n $ and use facts about them. Numbers of this form are triangular numbers, and here are the first several:
\[ 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, ... \]
The ability to partition ladybugs 1-$n$ into two same-sum subsets requires the $n$th triangular number to be even. These numbers seem to follow a pattern of
\[ \textrm{odd, odd, even, even, odd, odd, even, even, odd, odd, even, even, ...} \]
A low-level way to see that this pattern holds is to note that the differences between them are $2, 3, 4, 5, 6, 7, ...$, i.e., numbers that follow the pattern
\[ \textrm{even, odd, even, odd, even, odd, even, odd, ...} \]
If students understand
\[ \textrm{even} + \textrm{even} = \textrm{even}, \qquad \textrm{odd} + \textrm{odd} = \textrm{even}, \qquad \textrm{even} + \textrm{odd} = \textrm{odd}, \qquad \textrm{odd} + \textrm{even} = \textrm{odd}, \]
then the parity pattern of the natural numbers can be used to argue the parity pattern of the triangular numbers, since adding even, odd, even, odd, even, odd, even, odd, ... will switch the parity every other number.

If students have seen that
\[ 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2} \]
then this and some divisibility arguments can be used. We've seen that we can partition two same-sum subsets when $n$ is even and $n/2$ is even or when $n$ is odd and $(n+1)/2$ is even. Both $n$ and $n/2$ being even is equivalent to $n$ being divisible by $4$. Similarly, $n$ being odd while $(n+1)/2$ is even is equivalent to $n+1$ being divisible by 4. If $n$ or $n+1$ is divisible by $4$, then
\[ \frac{n(n+1)}{2} \]
is even since
\[ \frac{n(n+1)}{4} \]
is an integer. Conversely, if $n$ is even but not divisible by $4$, $n+1$ is odd, so
\[ \frac{n(n+1)}{2} \]
must be odd. It's similarly odd if $n+1$ is even but not divisible by $4$, since $n$ would be odd.

Since $n$ or $n+1$ being divisible by $4$ is equivalent to $n$ having a remainder of $0$ or $3$ when divided by $4$, this together with our pairing method for creating groups shows that $n \equiv 0$ or $3 \mod 4$ is precisely the condition required to be able to partition ladybugs 1-$n$ into two same-sum subsets.

While the pairing approach discussed earlier is probably the conceptually easiest way to create a same-sum 2-subset partition when it's possible, a greedy algorithm also works. Start with ladybugs 1-$n$ in the left set. Then move the largest one right that won't make the sum on the right larger than

\[ \frac{1}{2}\left(\frac{n(n+1)}{2}\right) = \frac{n(n+1)}{4}. \]

For ladybugs 1-8,

\[ \frac{8(9+1)}{4} = 18 \]

and this is how the algorithm would form a same-sum 2-subset partition:

This algorithm also works for creating sets with sums differing by 1 in the cases where a same-sum 2-subset partition is impossible.

For a partition of $k > 2$ same-sum subsets, things get more nuanced. We still have divisibility on our side, since in order to create a same-sum $k$-subset partition from ladybugs 1-$n$, we clearly need
\[ \frac{n(n+1)}{2} \]
to be divisible by $k$. Divisibility on its own is not enough, though, since going back to our example of ladybugs 1-8,
\[ \frac{8(9+1)}{2} = 36 \]
is divisible by $6$. However, partitioning 1-8 up into 6 subsets would require at least 4 of the subsets to have one ladybug. Since the ladybugs all have different numbers, no two subsets containing a single ladybug can have the same sum. This sort of pigeonhole principle argument can be made when considering many of the edge cases. We can use it to rule out a same-sum $k$-subset partition of ladybugs 1-$n$ when $n \leq 2k-2$, for example.
Looking at same-sum 3-subset partitions, we note that
\[ \frac{n(n+1)}{2} \]
is divisible by 3 precisely when $n$ or $n+1$ is, meaning $n$ has a remainder of $0$ or $2$ when divided by $3$ (in symbols, $n \equiv 0 \textrm{ or } 2 \mod 3$). Here's one possible way to create the subsets in these cases when $n \geq 5$.

Create "starter" solutions for small cases:
- $n = 5$: $ 1+4 = 2+3 = 5 $ $n = 6$: $ 1+6 = 2+5 = 3+4 $ $n = 8$: $ 1+3+8 = 2+4+6 = 5+7$ $n = 9$: $ 1+6+8 = 2+4+9 = 3+5+7 $
Any $n > 9$ with $n \equiv 0 \textrm{ or } 2 \mod 3$ will differ from one of 5, 6, 8, or 9 by a multiple of 6. Choose this "starter" and then add the next six numbers in high-low pairs.

For example, for 1-26, note that 26-8 = 18, a multiple of 6, so we'll start with
\[ 1+3+8 = 2+4+6 = 5+7. \]
The next six numbers are $9, 10, 11, 12, 13, 14$, which we can pair off $9+14 = 10+13 = 11+12$ and then throw them in:
\[ (1+3+8)+(9+14) = (2+4+6)+(10+13) = (5+7)+(11+12) \]
Next,
\[ (1+3+8)+(9+14)+(15+20) = (2+4+6)+(10+13)+(16+19) = (5+7)+(11+12)+(17+18), \] and finally, \[ \begin{eqnarray*} (1+3+8)+(9+14)+(15+20)+(21+26) & = & (2+4+6)+(10+13)+(16+19)+(22+25) \\ & = & (5+7)+(11+12)+(17+18)+(23+24), \end{eqnarray*} \]
Thus, we see everything meeting our divisibility criterion can be made!
The case of 4-subset partitions is simpler. The divisibility criterion is that $4$ must divide
\[ \frac{n(n+1)}{2}, \]
i.e., $8$ must divide $n(n+1)$. Since one of $n$ or $n+1$ is odd, this means $8$ divides $n$ or $n+1$, or $n \equiv 0 \textrm{ or } 7 \mod 8$. In both of these cases, we can do our pairing trick (with $n$ by itself if $n \equiv 7 \mod 8$) and get $4k$ same-sum subsets for some $k$. We then cluster them into four groups of $k$ pairs.

For example, for 1-23, we do our usual (almost) pairings:
\[ 1+22 = 2+21 = 3+20 = 4+19 = 5+18 = 6+17 = 7+16 = 8+15 = 9+14 = 10+13 = 11+12 = 23. \]
There are 12 of these, so we use our $12 = 4 \cdot 3$ trick to turn it into 4 subsets:
\[ \begin{eqnarray*} (1+22) + (2+21) + (3+20) & = & (4+19) + (5+18) + (6+17) \\ & = & (7+16) + (8+15) + (9+14) \\ & = & (10+13) + (11+12) + (23). \end{eqnarray*} \]

Wrap-Up Questions

The main lingering question is for which $n$ and which $k$ it is possible to partition 1-$n$ into $k$ subsets with equal sums and, for cases where it's possible, if there's a nice procedure for making these subsets.

We discussed possible toeholds for $k = 2, 3, \textrm{ or } 4$ above. Were students able to find these or similar ideas?

We treated $k = 2 \textrm{ and } 4$ pretty similarly and $k = 3$ pretty differently. Is that necessary, or are there ways to think about it where these cases are more similar?

What patterns might exist in terms of $n$ when $k = 5$ or when $k = 6$?

A result on the existence of these partitions can be found in a paper of Straight and Schillo. Their theorem is that if

\[ n(n+1) = 2st, \qquad \textrm{for } t \geq n \]

then $\{1,2,3,...,n\}$ can be partitioned into $s$ subsets all having sum $t$. Their approach can be adapted into a recursive algorithm, but it's likely not something students would come up with!

Extensions

We were mostly preoccupied with finding some partition of 1-$n$ into $k$ same-sum subsets. What if, in addition to having the same sum, we also wanted all of these subsets to have the same size or as close to the same size as possible? For example,

\[ 2+3+4+6+7+8 = 1+14+15 = 5+12+13 = 9+10+11 \]

is a fine partition of 1-$n$ into four same-sum subsets, but one has 6 elements while the others have 3. On the other hand,

\[ 1+14+15 = 2+3+12+13 = 4+5+10+11 = 6+7+8+9 \]

has subsets of size 3, 4, 4, and 4, and we can't do better. If 1-$n$ can be partitioned into $k$ same-sum subsets, can they always be made to have (almost) equal size? In this case, "almost" would be if all sets had size $m$ or $m+1$ where $m = \lfloor n/k \rfloor$.

This post was sponsored by the Julia Robinson Mathematics Festival

Search This Blog

math them