Old algorithms and new

I’m taking a number theory class this summer, so my mind is full of residuals and mods.  In that mindset it’s easy to forget all the other math I’ve learned in my life.  Here’s an example.  I was asked to find a divisor between 2000 and 3000 of this expression:

85^9 -21^9 + 6^9

Because 85, 21, and 6 all have prime factors in common, it’s easy to find some primes that evenly divide this expression.  But that alone isn’t enough to find a single number between 2000 and 3000.

I considered all the divisibility formulas I had learned in the previous lecture:  Fermat’s Little Theorem, Euler’s Theorem, and Wilson’s Theorem, but nothing seemed to work.

It turns out, solving the problem is made easier by seeing that the first 2 terms in the expression:  85^9 - 21^9 can be expressed as a difference of cubes.  Twice actually!

85^9 - 21^9 = (85^3)^3-(21^3)^3

A difference of cubes can be factored as:

a^3-b^3 = (a-b)(a^2 +ab + b^2)

Substituting, we find:

85^9 - 21^9 = (85^3)^3-(21^3)^3 = (85^3-21^3)((85^3)^2+85^321^3+(21^3)^2)

But now we can do it again with the first factor:

85^3-21^3=(85-21)(85^2+85 \cdot 21+21^2)

Setting N equal to all those yucky square and cubes to the right, we now we have

85^9 - 21^9 = (85-21)N=64N=2^6N.

And so we have:

85^9-21^9+6^9 = 2^6N + 2^62^33^9 = 2^6(N+2^33^9)

And voila, we have found another factor, 2^6, that divides this expression.

Good math problems force the student to use not only skills they have just learned, but also draw on older skills and older theorems that have been sitting around unused in your brain.

This is another reason I think math contests are so valuable to our students.  Students continue to use all the algorithms they learned earlier, keeping it fresh in their minds.   Is it unfair to test students on factoring polynomials in a number theory class?  Strong students welcome the opportunity to be reminded of old almost-forgotten formulas because hopefully they’ll recognize those differences of cubes again in the future.

 

 

Rates

Students who are solid on rate problems will earn easy points on MathCounts!

img_20190702_135510

The only formula to memorize is the definition of rate, r=\frac{d}{t} where d= distance and t= time.  I find it helpful to draw a quick diagram so I can visualize what is happening to our MathCounts team on their way to and from the contest.  (H=home, MC = MathCounts contest.)

On the return trip we multiply the time by 2, multiply the distance by \frac{3}{2}, and subtract 10 mi/h from the rate.

The first equation I have written derives from the fact that the new rate is equal to the old rate minus 10 mi/h.  Then it is a matter of solving for r=\frac{d}{t} which is the rate to the contest.

Source: MathCounts

Number of factors

There’s a neat trick for finding the number of factors of a number.  First find the prime factorization of the number, for example:

756 = 2^2 \cdot 3^3 \cdot 7^1

Add +1 to the power of each prime factor and then multiply those numbers together.  In this example,

(2+1)\cdot(3+1)\cdot(1+1)= 3\cdot 4 \cdot 2 = 24 factors.

This reflects the fact that each factor of 756 contains 2^n where n= 0, 1, or 2 and 3^m, where m = 0, 1, 2, or 3 and 7^p where p = 0 or 1.

I used this property to solve a problem in a number theory class I’m taking.  The problem asks to compute the sum of all positive integers k such that 1984k has  21 positive factors.

Since 21 = 3\cdot7 , working backward we are looking for a prime factorization with 2 primes raised to the powers of 2 and 6.  The prime factorization of 1984 = 2^6\cdot 31 so we have one prime raised to the sixth power.  All we need is the other prime to be squared.  Setting k=31 gives us

1984k = 2^6\cdot 31^2 with (6+1)(2+1)= 21 divisors.

Python for fun

screenshot-2019-05-27-at-3.06.21-pm

With the school year over, I’ve had time to pursue other math related activities.  I’ve been reading through the book Joy of SET by Liz McMahon and others.  It describes the “many mathematical dimensions of a seemingly simple card game” and was recommended to me a few months ago.

There were a few chapters on various probabilities, like the probability of finding 1 set out of 4 randomly chosen cards.  I enjoy writing  python programs that can confirm calculated probabilities by running a simulation several thousands of times.

My program will step through a game of SET, dealing 12 cards, finding SETs and removing them from the table, and dealing more cards so that there are 12 cards on the table again.  If there are no SETs in the dozen cards, then it deals 3 more.

I also wrote a function that will find the probability of finding n SETs when one randomly deals x cards, allowing the user to choose how many times to run the simulation.  I find that 10,000 repetitions is about adequate.

Check out my SET program here.  It’s still a work in progress.  I’m now deciding whether to calculate the expected value of the number of SETs in a dozen cards, which will mean rewriting some of my methods.

Here’s a hack:  if you forget anything in python you can just google it for a refresher.   For example, I couldn’t remember how to set argument defaults for my functions, so I googled:  “python function set default arguments.”

Summertime is a great time for students to follow rabbit holes and exercise python skills.

 

Keep those skills fresh

A student and I were slaying a tricky geometry problem from an old AMC.  She hadn’t taken geometry yet, but she had excellent insights, and we were making good progress.  We were close to the end and we needed to simplify \sqrt{12}.  Since 12 is a multiple of a square (4), and since the square root of a product is the product of the square roots, we can rewrite \sqrt{12}  as  2\sqrt{3}.
But she couldn’t do it.  I thought maybe she hadn’t learn how to simplify square roots, but she admitted she had learned them, but hadn’t solved a square root problem for a long time and was out of practice.   Fair enough.
As a student progresses through a math curriculum over the years, they are gradually adding tools to their problem solving tool box.  Simplifying square roots is another tool.  The textbook teaches you how to use it, you practice using it on a bunch of squares, then you throw into your tool box for some unspecified time when you will need it later.   Then they go on to learn another tool.  And another tool.
The trouble is, like my student, you can forget how to use your tools if you don’t practice.
That’s another reason why practicing math contests can be so helpful in keeping those skills fresh.  Math contests typically have all kinds of problems: geometry, probability, number theory, and yes solving square roots.  Sometimes, like in that geometry problem, you need to deploy several of your tools to arrive at a solution.

Factorials –> Factoring

I was working through this year’s MathCounts State Level exam, and found 2 problems involving factorials.  Your reflex when seeing a factorial problem is to see how you can factor the expression.  For example we are asked to find the value of this expression:

\frac{5!+6!}{4!+3!}

Notice that the 2 terms in the numerator are both products of 5! and the 2 terms in the denominator are both products of 3!.  So we can factor these both out:

\frac{5!+6!}{4!+3!}=\frac{5!(1+6)}{3!(4+1)}

If you notice that 5! and 3! both have a factor of 3! then the fraction is much easier to evaluate.

Another problem on the same exam asks us to solve for n:

(n+1)! - n! = 4320

Again you can factor n!  from the 2 terms on the left hand side:

(n+1)! - n! = n!(n+1 - 1)= 4320

n!\cdot n = 4320

To finish out this problem we can find the prime factorization of 4320 and match that up to the product of consecutive integers.

4320 = 2^5 \cdot 3^3 \cdot 5 = 2 \cdot 3 \cdot 2^2 \cdot 5 \cdot (2 \cdot 3) \cdot (2 \cdot 3) = 6! \cdot 6

n = 6