A Challenging Divisibility Puzzle: Spoilers

(A new question of the week)

Sometimes we give only minimal help on a question, to let a student puzzle over the problem and learn to figure it out herself. That may be enough, or we may go back and forth for some time, guiding her thinking until she finds the answer. In the latter case, do we put the whole discussion in our archive, so the answer is given away along with all the thinking? Or do we archive only hints? Recently a student wrote to ask about the answer to a puzzle we didn’t work to the end, and the discussion gives some interesting insights into the process — so here come the spoilers.

The problem

First, here is the question from our archive, asked by 12-year-old Subby in 2015:

All in a Row: Divisible Except for One Consecutive Pair

In a class, 25 students were lined up. 

The teacher wrote a number on the board.

The first student said the number was divisible by 1.

Student number 2 said it was divisible by 2.

Student 3 said it was divisible by 3.

This went on until the 25th student.

The teacher said everyone was correct except two boys, named Ben and
Danny, who were wrong. They were standing one after the other in the line.

What are their positions in the line?

Not sure if I have to find a common factor between 1 and 25, then divide
the found number by each number between 2 and 25 to see who has divided
correctly.

I think I am not approaching this right.

Doctor Greenie answered this, restating the problem and giving some hints:

This is a terrific problem -- quite challenging, I would think, for a 12-year-old.

According to the problem description, there are two consecutive numbers from 1 to 25 which do not evenly divide the teacher's number; and they are the only two numbers that do not divide the teacher's number.

The key to solving the problem is to look at divisibility rules for the numbers 1 to 25. 

For a couple of examples:

   25 = 5^2
            since the only prime factor of 25 is 5,
            we can't relate divisibility by 25 to
            divisibility by any smaller numbers

   24 = (2^3)*3 = 8*3
            the number is divisible by 24 if it is
            divisible by both 8 and 3

   23 is prime
            we can't relate divisibility by 23 to 
            divisibility by any numbers smaller than 23

   22 = 2*11
            the number is divisible by 22 if it is
            divisible by both 2 and 11

Continue this list down to 1; there will only be one place where it is not possible to relate the divisibility rules for two consecutive numbers to divisibility rules for smaller numbers.

Those two consecutive numbers are Ben's and Danny's places in the line.

The hint was (intentionally, I assume) not very detailed; a year later, another student wrote to ask about it, focusing too much on the rules for recognizing when a number is divisible by another, such as that “a number is divisible by 3 if the sum of its digits is divisible by 3”. That type of rule was not what Doctor Greenie emphasized; but rather, others, like “a number is divisible by 6 if it is divisible by both 3 and 2”, which is a particular case of a very general rule. I responded with some more specific hints:

I think you are misinterpreting what Doctor Greenie said. I imagine he deliberately kept his hint rather cryptic to avoid spoiling it for others. (For that matter, I'm not sure I follow his hint completely, myself!)

What I would say is that, rather than get caught up in the details of the divisibility rules, you want to consider just the relationships that some of them imply -- the rules like yours for 6. This rule implies two things:

1. If 6 does NOT evenly divide the number, then either 2 or 3 must also NOT be a divisor (since if both did divide it, 6 would also); since 2 or 3 and 6 are not consecutive, 6 can't be one of the two non-divisors.

2. If either 2 or 3 does NOT evenly divide the number, then 6 must also NOT be a divisor (since if 6 were a divisor, then both 2 and 3 would be too); so neither 2 nor 3 can be one of the two non-divisors.

Look for this sort of relationship among other sets of numbers. You might need to make a table or diagram showing these connections, or it may be enough to cross off from a list each number that is excluded. You should soon get a feel for what kind of numbers one of the pair has to be, and then discover what the other one must be.

Doctor Greenie also responded, saying he had trouble understanding his own hint (which is not uncommon, when we look back at our own old answers!), and adding more:

The input that Doctor Peterson gave is important. Where you were looking at the divisibility rules in isolation, the thing you want to be looking at is the relationship between the divisibility rules.

For example, a number is divisible by 24 if it is divisible by both 3 and 8; a number is divisible by 14 if it is divisible by both 2 and 7.

Note in that first example, it is important to say a number is divisible by 24 if and only if it is divisible by both 8 and 3. It would not be sufficient to say it is divisible by 24 if it is divisible by 4 and 6. 4 times 6 is 24; but 4 and 6 have a common factor of 2. 12 is divisible by 4 and 6; but it is not divisible by 24.

So if 24 were one of the two numbers that did not divide the teacher's number, then it would not be divisible by 3 or 8 either. But then you have numbers that are neither consecutive nor divisors of the teacher's number. So 24 can't be one of the two consecutive non-divisors.

What about 23? It is prime, so having a number divisible by 23 does not imply divisibility by any smaller number. There is a possibility that 23 is one of the two consecutive non-divisors.

But we already know that 24 can't be one of the two non-divisors; and divisibility by 22 implies divisibility by both 2 and 11. So even though 23 had the possibility of being one of the two non-divisors, each of its neighbors can't be the other one.

Similarly, we can rule out 22, 21, and 20 as being one of the two consecutive non-divisors, because for each of them divisibility implies divisibility by smaller numbers that are not adjacent:

   non-divisibility by 22 --> non-divisibility by 2 or 11
   non-divisibility by 21 --> non-divisibility by 3 or 7
   non-divisibility by 20 --> non-divisibility by 4 or 5

Continue down the list to find the only place where non-divisibility by two consecutive numbers does *not* imply non-divisibility by any smaller numbers.

In the process of trying to provide an explanation that could help you solve the problem, I came up with this alternative method, which you might (or might not!) find easier. Start by finding the smallest number (in prime factorization form) of the number that is divisible by all the numbers from 1 to 25. Then search for ways to remove certain prime factors so that two consecutive integers become non-divisors.

More help

Now, this summer, Sarah got interested in solving this, and wrote to us for help:

I found this in the Ask Dr.Math archives, and got curious what the solution is: http://mathforum.org/library/drmath/view/77746.html. After reading the hints, I thought the obvious answer is 2 and 3, since they’re both prime? Is this correct? And how would you find the actual number the teacher wrote? (Out of curiosity and as a check)

We went back and forth on this for four days (partly due to being in distant time zones). I first corrected her attempt:

No, the answer can’t be 2 and 3; as I said in my answer,

If either 2 or 3 does NOT evenly divide the number, then 6 must also NOT be a divisor (since if 6 were a divisor, then both 2 and 3 would be too); so neither 2 nor 3 can be one of the two non-divisors.

What we know is that every integer from 1 through 25 is a divisor of N except for two consecutive numbers. If nothing else, you could just try every pair from 1,2 to 24,25 and think about the implications; along the way, you might get some special insight. But I will tell you that my immediate thought (which could be wrong) is that the pair of non-divisors might more likely be large than small. The 2,3 case shows why, and this may be why Dr. Greenie started his list at 25.

Give it another try. I’ll be thinking about it while you do. (I don’t immediately recall what the answer was.)

She gave it a try that didn’t work, and I responded with further clarification:

Let’s look more closely.

We want to find two consecutive numbers such that our unknown number N can be a multiple of every number from 1 to 25 except those two.

Suppose the answer were 24 and 25. That would mean that N is a multiple of everything up to 23, but not of 24 or 25.

First, consider 25 = 5^2. If N were a multiple of 25, then it would also be a multiple of 5; that doesn’t matter (just now). But if N is not a multiple of 25, it can still be a multiple of 5 (e.g. 35), so there is no problem. None of the other numbers is forced to be a divisor of N by this fact. We might call 25 a “safe” number.

But consider 24 = 2^3 * 3. If N were a multiple of 24, then it would also be a multiple of any divisor of 24 (1, 2, 3, 4, 6, 8, 12). But what matters to us at the moment is the implication if N is not a multiple of 24.

We can split 24 into 3*8, where 3 and 8 have no common factors; then we know that if N is a multiple of both 3 and 8, it must be a multiple of 24. Do you see why? This is fundamental to divisibility checks, and would not be true if we chose a pair of numbers with a common factor, like 4 and 6: 12 is a multiple of both, but not of 24.

Now, the contrapositive of that statement in bold is, if N is not a multiple of 24, then it must not be a multiple of both 3 and 8; that is, it must either not be a multiple of 3, or not be a multiple of 8. But we were supposing that 24 and 25 are the only numbers from 1 to 24 of which N is not a multiple. So 24 can’t be one of the numbers we’re looking for. We might say that 24 is not a “safe” number.

Now, I mentioned some facts that we don’t care about yet (with 24 or 25); they will come into play when we look at smaller numbers. For instance, if N were not a multiple of 2, then it couldn’t be a multiple of any multiple of 2 either. That would give us a lot of other numbers from 1 to 25 that N was not a multiple of, so 2 can’t be one of our numbers: it is not “safe”.

What I did to solve the problem was to look individually at each number from 1 to 25 and do thinking like I just did: what other facts would be implied if N were not a multiple of a given n? If n not being a divisor implies that any other numbers than n-1 and n+1 are also not divisors, then n can’t be it. Eventually, you should be able to speed up a bit, by noticing certain kinds of numbers that are “safe”. I’m deliberately avoiding some words that would give you too much of a hint!

My introduction of a made-up term, “safe” (by which I meant that it doesn’t “endanger” other numbers), is a common trick of mathematicians to make it easier to talk about a concept that is useful in a particular problem. I think of this as a “local definition”. A common word that is used is “nice”, which in ordinary usage has only a vague positive meaning, and so, like tofu, can be given whatever specific flavor you want. Here, it lets me state the goal quickly: We want to find two consecutive safe numbers.

Sarah gave me a lot of detail on her next try:

I understand what you said, but I’m not sure I know how to continue. I was probably mixing up factors and multiples, even though I know the difference between the two. I’m guessing that by certain kinds of numbers you meant the primes, but thanks for not giving too many hints; it’s good to do some thinking!

Let me try:

If N is not a multiple of 23 – 23 is prime, so it’s “safe”

If N is not a multiple of 22 – it can’t be a multiple of both 2 and 11 so it’s not “safe”

If N is not a multiple of 21 – it can’t be a multiple of both 3 and 7, so its not “safe”

If N is not a multiple of 20 – it can’t be a multiple of both 4 and 5, or both 2 and 10, so it’s not “safe”

If N is not a multiple of 19 – 19 is prime, so it’s “safe”

If N is not a multiple of 18 –  it can’t be a multiple of both 3 and 6, or both 2 and 9, so it’s not “safe”

If N is not a multiple of 17 – 17 is prime, so it’s “safe”

If N is not a multiple of 16 – it can’t be a multiple of both 2 and 8, so it’s not “safe”

If N is not a multiple of 15 – it can’t be a multiple of both 3 and 5, so it’s not “safe”

If N is not a multiple of 14 – it can’t be a multiple of both 2 and 7, and 28 can’t be a multiple, so it’s not “safe”

If N is not a multiple of 13 – 26 can’t be a multiple either

If N is not a multiple of 12 – it can’t be a multiple of both 4 and 6,  and 24 can’t be a multiple, so it’s not “safe”

If N is not a multiple of 11 – it can’t be a multiple of 22

If N is not a multiple of 10 – it can’t be a multiple of both 2 and 5

If N is not a multiple of 9 – then 18 cannot be a multiple, and N can’t be a multiple of 3

If N is not a multiple of 8 – it can’t be a multiple of both 2 and 4

If N is not a multiple of 7 – 14 can’t be a multiple, and neither can 21

If N is not a multiple of 6 – it can’t be a multiple of both 2 and 3

If N is not a multiple of 5 – 10, 15, 20, and 25 can’t be multiples either

If N is not a multiple of 4 – 8, 12, 16, 20, and 24 can’t be multiples either

We’ve already ruled out 2 and 3, and 1 obviously can’t be, since every number is divisible by 1.

Spoiler alert!

She was very close now. My reply:

Primes were one of two kinds of numbers I could have mentioned. Certainly they are always “safe”. (Or not? Comment below.)

So you’ve listed these numbers as “safe”: (By the way, I first used that term just on a whim as I was typing, but I now see how good an idea it is!)

17, 19, 23

I’d also listed 25 as safe.

I see that for 14 and 13, you mentioned numbers greater than 25; you might want to reconsider. That will be a significant change in the way you have to think once you get to smaller numbers. But you were still thinking, because you saw that 11, though prime, is not safe, because 22 is less than 25. So we should say that primes greater than 13 are safe.

The main problem is that you didn’t take to heart my comment about the importance of “factors with common factors”. For 18, you say “it can’t be a multiple of both 3 and 6, or both 2 and 9, so it’s not “safe”. That’s correct for 2 and 9, which are relatively prime (I can use that word now), but not for 3 and 6. Since these have a common factor, 3, a number can be a multiple of both but not be a multiple of their product: 12 is a multiple of 3 and of 6, but not of 18. So you can’t say that if N is not a multiple of 18, then it can’t be a multiple of both 3 and 6. (This was part of what Dr. Greenie had in mind about divisibility rules.)

The main thing you need to do is to work through things a little more slowly, and perhaps do as I had not done and write explicit statements like “primes greater than 13 are safe” so you can check them out. But I’ll give you one more specific hint: you know why that latter fact is true (well, check it out!); what is it that makes 25 safe? It isn’t prime! Is it just being the highest number in the list, or is there more to it?

Sarah’s next attempt:

This is very interesting! I also like the idea of defining safe numbers!

My first thought about 25 is that it is safe because it is a square number, so I’m thinking the solution is 16 (square number) and 17 (prime greater than 13). Let’s check it out:

16 is 2 * 8, and 2 is a common factor, so I can’t say that if N is not a multiple of 16, it can’t be a multiple of both 2 and 8. (In this case, I can’t find a number that is a multiple of both 2 and 8, but not of 16). If N is not a multiple of 16, it can be a multiple of 4 though.

We’ve already said 17 is a safe number.

I’ve just reread what you wrote about 25, and realised that you wrote “consider 25 = 5^2”, so it was there in front of me! Nice hint 🙂

But let’s check another example, to be sure:

9 – if N is not a multiple of 9, it can be a multiple of 3 (example 6)

So think the answer is 16 and 17.

Also, I don’t think 18 is safe, since it can’t be a multiple of both 2 and 9. Otherwise, the answer would have been there already – 17 and 18.

The reference to 25 = 5^2 was not intended as a hint; I was showing the factors of everything. But it did make the key idea visible.

I answered:

Elaborating on what you said about 16, the general idea is to look at the prime factorization of a number, in this case 2^4. With only one prime factor, there is no pair of factors (other than 1 and 16) that are relatively prime; so the only conclusion regarding smaller numbers is that if 16 is a divisor of N, then every lower power of 2 is a divisor of N (2, 4, 8). Given that 16 is not a divisor of N, we can’t conclude that any lower number must not be a divisor of N. Also, since 2*16> 25, we can’t conclude that any larger number must not be a divisor of N. Thus we can conclude that 16 is safe. (You said, “I can’t find a number that is a multiple of both 2 and 8, but not of 16”; did you try 8?)

Your answer is correct.

Now, notice how much more has to be said than I said explicitly last time:

We define a safe number as a positive integer n such that, if n is not a divisor of some number N, then no other number in {1, 2, .., 25} is necessarily not a divisor of N.

Whether a number is safe depends on two things: whether there are any smaller numbers that are forced not to be divisors, and whether there are any larger numbers up to 25 that are forced not to be divisors. These work in different ways, and must both be considered.

No number less than 13 can be safe, because doubling it will yield a number less than 26.

Any prime n greater than or equal to 13 is safe, because no smaller number (except 1) is a factor of n, and no larger number through 25 is a multiple of n.

Any prime power n greater than or equal to 13 is safe, because there are no pairs of relatively prime numbers that are both factors of n.

After this, we discussed a similar problem I had run across with some interesting differences. But this post is already over my self-imposed size limit …