## Friday, July 25, 2014

### When Linear Sequences Coincide

I was playing around with this idea yesterday: How do we figure out when two linear sequences will eventually have the same value? How do we know when they will not? Randomly, I came across Amy Gruen's question on Twitter from a while back (but it also relates to the last NRich task I had posted yesterday, in trying to figure out how to find numbers that would light up multiple colors in the applet):

I am a number less than 3000, Divide by 32, the remainder is 30. Divide by 58, the remainder is 44. Who am I?

(If you haven't had a chance to play with this problem, I encourage you to do so and to get back to me if you have a different method than the one I have described below!)

I started by listing some multiples of 32 (32, 64, 96, 128, 160, 192, 224, ...) in Excel and then adding 30 to find numbers that satisfy the first condition ("Divide by 32, the remainder is 30"). These are the numbers in the first linear sequence, we'll call it sequence A: 62, 94, 126, 158, 190, 222, 254, ... A 5th grader can do this as well (as Amy had stipulated), but probably not in Excel but by hand.

And then, similarly, I listed out some of the sequence of numbers that would satisfy the second condition ("Divide by 58, the remainder is 44"): 102, 160, 218, 276, 334, 392, 450, ... We'll call this Sequence B.

My first instinct was to write two expressions 32n + 30 and 58n + 44 and to set them equal, but of course that doesn't work because the sequence values are likely not going to coincide at the same position n. (This is probably a common misconception, so I thought I would point out that it's a natural one to make.) Also, algebra isn't part of the Grade 5 curriculum.

Then, I thought if I started iterating through elements of Sequence B, I would probably reach the coinciding element faster, only because sequence B takes "bigger steps" and skips more of the in-between, irrelevant values. And, instead of listing every element from each sequence, I thought that maybe keeping track of how far "off" sequence B is from the closest element of sequence A might help me.

I made a table that looked like this. I decided to use shorthands in column 3 to help me focus on seeing a pattern. Originally I didn't have the a and b, but the numbers by themselves didn't seem helpful. Once I added the a and b (for above and below), the pattern was much more recognizable, because I was essentially assigning positive and negative signs to the distances.

 Sequence B Element Distance from Nearest Sequence A Elements Shorthand representation of distance 102 8 above 94; 24 below 126 8a (24b) 160 2 above 158; 30 below 190 2a (30b) 218 4 below 222; 28 above 190 4b (28a)

I observed what I think was a linear pattern by this point, and decided that I could predict what the next few sequence B elements' distance would be from the nearest element of sequence A. I also noticed that the above and below nearest distances added up to 32, as you would expect. (Since sequence A elements are separated by steps of size 32, if you're 8 values above the nearest value in that sequence, you must be 24 values below the next one, like being suspended in between two rungs of a ladder of fixed space between the rungs.)

So, based on this I hypothesized and tested that the next elements of sequence B will continue to follow this pattern and be located at a predictable distance from the nearest sequence A elements.

 Sequence B Element Shorthand representation of distance from nearest Sequence A elements 276 10b (22a) 334 16b (16a) 392 22b (10a) 450 28b (4a)

A pause here. I haven't reached any repeats yet. If I had reached any repeats in my table in terms of distance from the nearest elements (for example if I saw 8a and 24b appear twice in the table before reaching 0a or 0b), I would conclude that the two sequences will never meet. In the case of this problem, I should continue the table since we haven't reached any cycles yet.

 Sequence B Element Shorthand representation of distance from nearest Sequence A elements 508 30a (2b) 566 24a (8b) ... ... skipping some rows here, since I can see that 24a is a multiple of 6 and it will eventually decrease to 0a perfectly... 798 0a (32b)
So, if this pattern holds, 798 should be the first time that sequences A and B converge, which means this number should leave me a remainder of 30 when divided by 32 and leave me a remainder of 44 when divided by 58. And it does!

To find the subsequent elements is much easier (more of a standard math problem), because we know that the two sequences move by paces of 32 and 58, respectively. All we need to do is to find the least common multiple of their steps, which will be the distance that separates pairs of coinciding elements. The factors of 58 are 29 and 2, the (partial) factors of 32 are 2 and 16. So, 29x2x16 = 928 should be the least common multiple. That means that after 798, the next time the sequences converge to satisfy both conditions is at 798 + 928 = 1726, and the next time is 1726 + 928 = 2654.  Since 2654 + 928 > 3000 and 798 - 928 < 0, our complete set of solutions is {798, 1726, 2654}.

Just in case, I tested all three values against the two given conditions (since I don't trust myself with arithmetic and book-keeping). Also just in case I didn't mess up the LCM calculation, I tested the value halfway in between 798 and 1726 to make sure that it doesn't satisfy both given conditions.

Now, here are the follow-up questions: Do you think this problem is doable by a student? What type of scaffolding would they need in order to accomplish this type of task? Are there other ways of doing this problem?

#### 1 comment:

1. You may find useful in these problems the Chinese Remainder Theorem