NOD to the QROD - a mnemonic for converting improper fractions

I was trying to think of how to teach my kids about converting improper fractions to mixed form. The whole process is kind of confusing and easy to forget. I came up with the following mnemonic to help remember how to do it:

NOD to QROD

What does that mean? It sounds like a mantra that fans might chant at a baseball game as their favorite baseball star QROD approaches the plate. "NOD to QROD, NOD to QROD, NOD to QROD"... Then QROD goes up to the plate, here's the pitch... it's a long drive deep to center field, it's going, it's going, it's gone. QROD hits a home run! Everybody in the park explodes with excitement as QROD circles the bases.

So with NOD to QROD, you can hit a home run every time you want to convert an improper fraction. So again, what does that mean?

Numerator Over Denominator to Quotient Remainder Over Denominator

You always start with an improper fraction of the form Numerator Over Denominator. Your goal is to convert the fraction into mixed form. What that really means is that you should express the fraction as Quotient Remainder Over Denominator. For example suppose you wanted to convert the improper fraction 37/5 into mixed form. Reading the expression out loud we have "37 Over 5". The Numerator 37 is Over the Denominator 5. As I'll explain in the next paragraph, you'll need to do some long division and get a Quotient 7 and Remainder 2. Using the mnemonic, we need to write the answer as QROD. So Quotient 7 Remainder 2 Over Denominator 5 or 7 2/5. Summarizing:

N O D to Q R O D

37/ 5 = 7 2/5

So that tells you how to write the final answer, but it doesn't tell you how to get Q the quotient, or R the remainder. For that you'll need to know how to do long division, something that you will need to learn to do first. But once you know how to do long division, the Quotient is what you get on top, and the Remainder is what you get at the very end, when you've finished dividing the numerator as much as possible into the denominator. For example, the 37/5 example, you would do something like

      7    ---------Quotient

   _______

 5 | 3 7  

     3 5    

     ---

       2    --------Remainder 

Or in general:

                    Q   Quotient

                _______

 Denominator D |   N    Numerator    

                   .

                     .

                       .  

                         R  Remainder

so visually the NOD to QROD means:

                ___Q___

N/D     =    D |   N         =   Q  R/D     

                    ... R

The Importance of Getting Your Units Right According to Spinal Tap

One of my favorite movie skits of all time. It's very applicable to physics!

Warning: It's borderline R-rated due to foul language.

Spinal Tap - Stonehenge

A Stable Physics Demo

I was wondering about the following idea for a physics demo.

You drop a metal ball from the ceiling along a vertical ramp which guides the ball and launches it at the bottom at some angle. Then you set up a small basket to catch the metal ball a certain distance away. When you do the math you get the following formula for the distance d that the basket should be away from the launch point:

d = 2 h sin 2θ

where d is the distance between the launch point and the basket, h is the original height of the ball, and θ is the launch angle from the horizontal.

In particular, if you set up the launch angle as 45 degrees, you get the nifty formula:

d = 2 h

meaning that the horizontal distance is exactly twice the height!

The last formula makes it extremely easy to set up (or to try to verify as a lab experiment). The question I had was whether this will actually work? In particular, when you set up the demo, you're bound to make small mistakes in the set up. You'll lose the "WOW" factor if your metal ball doesn't fall into the basket on your first attempt. The most brittle part of the set up is the launch angle. So it's worthwhile to compute the error introduced into d from an error in θ. I.e., how far will the ball fly off the mark if you set up the launch angle as 44 degrees instead of 45.

It turns out, that since sin 2θ has a maximum at 45 degrees, the error is actually quite small. If you do the calculus of variations you'll get

Δd / d ≈ -4 (Δθ)²

so that the proportional error in distance varies quadratically with the angular error. For an error of 1 degree and a distance of 5 m, this is less than 1 cm error -so we can expect a bullseye! For an error of 5 degrees and a distance of 5m, this is around 15 cm, so that there is a high probability of getting into a small trash can.

Even though the most brittle part of the set up is the launch angle, there are some other issues I could see interfering with perfect results:

• The angle of the launcher on the horizontal plane. You could get the right total distance but still be off the mark because you end up on left or right of target.
• Measuring h and d accurately.
• Friction on the way down or during launch that will reduce the ball's kinetic energy and hence reduce d.
• To a lesser extent, air resistance.

I'll try this experiment and report back!

Josephus Problem in Binary

One of my favorite discrete math problems is Josephus's problem. I love to introduce the problem to the class telling the story of how the clever Josephus Flavius was able to survive the mass suicide, and then act out the story with the entire class using some implement of violence - such as a whiffle ball bat. Of course, I rig the game so that I win. The class is typically is quite amazed and claps enthusiastically when they realize that I'm the last man standing.

So how do I do pull it off? I don't simulate the entire game in my head! Instead, I use a handy little formula for the solution of the Josephus problem:

J(n) = left_rot( n )

where left_rot is the operation on n obtained by expressing n as a binary number, then rotating all the digits one bit to the left (so in particular bringing the left-most bit all the way to the right)

That means, that if there are 52 students present add me to make 53, then consider the binary expression [53]₂ = 110101, then rotate one bit to the left obtaining 101011 which represents 43. I just need to position myself so that I'm in the 43rd position and I'll be the last man standing!

Proof of formula.

For the proof we start with the partial recursive formula for J(n) which you can obtain by simply considering what happens to an even or odd number of people after the sword goes around the circle once:

J(n) =

• 2*J( (n-1)/2 ) + 1, in the case when n is odd
• 2*J( n/2 ) - 1, in the case when n is even

Use induction on the length L of [n]₂.

The base cases are length L = 1 and 2 in which case one can verify directly the three cases:

• J(1) = 1 is the left_rot of itself
• J(2) = 1 which is the left_rot of 10 = [2]₂
• J(3) = 3 which is the left_rot of 11 = [3]₂

Suppose we know the theorem to be true up to length L. Consider J(n) where n has L+1 bits base 2. Express [n]₂ a the string 1ml where l is the least significant bit, and m is the string consisting of the middle L-1 bits.

Case 1 of the inductive step [n is odd]. So l=1. By the recursive formula for J(n) we have

J(n) = 2*J((n-1)/2)+1

= 2*J( ( number(1m1) - 1) / 2 )+1

= 2*J( number(1m0) / 2 ) + 1

= 2*J( number(1m) ) + 1

= 2*number(m1) + 1

Where in the last step we applied the inductive hypothesis. Continuing on we have

2*number(m1) + 1 = number(m10) + 1

= number(m11)

= rot_left( number(1m1 )

= rot_left( n )

and finishes up the first case.

Case 2 of the inductive step [n is even]. So l=0. By the recursive formula for J(n) we have

J(n) = 2*J(n/2)-1

= 2*J( number(1m0) / 2 ) - 1

= 2*J( number(1m) ) - 1

= 2*number(m1) - 1

Where in the last step we applied the inductive hypothesis. Continuing on we have

2*number(m1) - 1 = number(m10) - 1

= number(m01)

= rot_left( number(1m0 )

= rot_left( n )

and finishes up the second case and the proof in its entirety.