Thoughts on the Accidental Fraction Brainbuster

I really enjoyed reading a recent article on Math With Bad Drawings centered on solving the following problem without a calculator:

I won’t repeat the whole post here, but it’s an excellent exercise in numeracy, or developing intuitive understanding of numbers without necessarily doing a ton of computations. It’s also a fun exercise to see how much we can figure out without resorting to plugging into a calculator. I highly recommend reading it.

When I saw this problem, my first reflex wasn’t the technique used in the post. Instead, I thought to try the logic that follows. I don’t claim that this is a better way of solving the problem than the original solution linked above. But I do think that this alternative solution, in its own way, also encourages numeracy as well as what we can quickly determine without using a calculator.

Let’s get a common denominator for the two fractions:

$\displaystyle \frac{3997 \times 5001}{4001 \times 5001} \qquad$ and $\displaystyle \qquad \frac{4001 \times 4996}{4001 \times 5001}$.

Since the denominators are the same, there is no need to actually compute $4001 \times 5001$. Instead, the larger fraction can be determined by figuring out which numerator is largest. At first glance, that looks like a lot of work without a calculator! However, the numerators can both be expanded by cleverly using the distributive law:

$3997 \times 5001 = (4000-3)(5000+1) = 4000\times 5000 + 4000 - 3 \times 5000 - 3$,

$4001 \times 4996 = (4000+1)(5000-4) = 4000\times 5000 - 4 \times 4000 + 5000 - 4$.

We can figure out which one is bigger without a calculator — or even directly figuring out each product.

• Each contains $4000 \times 5000$, so we can ignore this common term in both expressions.
• Also, $4000 - 3\times 5000$ and $5000 - 4 \times 4000$ are both equal to $-11,000$, and so we can ignore the middle two terms of both expressions.
• The only difference is that there’s a $-3$ on the top line and a $-4$ on the bottom line.

Therefore, the first numerator is the larger one, and so $\displaystyle \frac{3997}{4001}$ is the larger fraction.

Once again, I really like the original question as a creative question that initially looks intractable that is nevertheless within the grasp of middle-school students. Also, I reiterate that I don’t claim that the above is a superior method, as I really like the method suggested in the original post. Instead, I humbly offer this alternate solution that encourages the development of numeracy.

Lessons from teaching gifted elementary school students: Index (updated)

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on various lessons I’ve learned while trying to answer the questions posed by gifted elementary school students. (This is updated from my previous index.)

Part 1: A surprising pattern in some consecutive perfect squares.

Part 2: Calculating 2 to a very large exponent.

Part 3a: Calculating 2 to an even larger exponent.

Part 3b: An analysis of just how large this number actually is.

Part 4a: The chance of winning at BINGO in only four turns.

Part 4b: Pedagogical thoughts on one step of the calculation.

Part 4c: A complicated follow-up question.

Part 5a: Exponentiation is multiplication as multiplication is to addition. So, multiplication is to addition as addition is to what? (I offered the answer of incrementation, but it was rejected: addition requires two inputs, while incrementation only requires one.)

Part 5b: Why there is no binary operation that completes the above analogy.

Part 5c: Knuth’s up-arrow notation for writing very big numbers.

Part 5d: Graham’s number, reputed to be the largest number ever to appear in a mathematical proof.

Lessons from teaching gifted elementary school students: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on various lessons I’ve learned while trying to answer the questions posed by gifted elementary school students.

Part 1: A surprising pattern in some consecutive perfect squares.

Part 2: Calculating 2 to a very large exponent.

Part 3a: Calculating 2 to an even larger exponent.

Part 3b: An analysis of just how large this number actually is.

Part 4a: The chance of winning at BINGO in only four turns.

Part 4b: Pedagogical thoughts on one step of the calculation.

Part 4c: A complicated follow-up question.

A subtle math joke

In case you need a subtle hint, here’s another version:

Thoughts on 1/7 and Other Rational Numbers: Index

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series the decimal expansions of rational numbers.

Part 1: A way to remember the decimal expansion of $\displaystyle \frac{1}{7}$.

Part 2: Long division and knowing for certain that digits will start repeating.

Part 3: Converting a repeating decimal into a fraction, using algebra.

Part 4: Converting a repeating decimal into a fraction, using infinite series.

Part 5: Quickly converting fractions of the form $\displaystyle \frac{M}{10^t}$, $\displaystyle \frac{M}{10^k-1}$, and $\displaystyle \frac{M}{10^t (10^k-1)}$ into decimals without using a calculator.

Part 6: Converting any rational number into one of the above three forms, and then converting into a decimal.

Part 7: Same as above, except using a binary (base-2) expansion instead of a decimal expansion.

Part 8: Why group theory relates to the length of the repeating block in a decimal expansion.

Part 9: A summary of the above ideas to find the full decimal expansion of $\displaystyle \frac{8}{17}$, which has a repeating block longer than the capacity of most calculators.

Part 10: More thoughts on $\displaystyle \frac{8}{17}$.

Lessons from teaching gifted elementary school students (Part 4c)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received:

What is the chance of winning a game of BINGO after only four turns?

When my class posed this question, I was a little concerned that the getting the answer might be beyond the current abilities of a gifted elementary student. As discussed over the past couple of posts, for a non-standard BINGO game with 44 numbers, the answer is

$\displaystyle 4 \times \frac{4}{44} \times \frac{3}{43} \times \frac{2}{42} \times \frac{1}{41} = \displaystyle \frac{4}{135,751}$

What’s that in decimal?

With these gifted students, I encourage thinking as much as possible without a calculator… and they wanted me to provide the answer to this one in like fashion. For my class, this actually did serve a purpose by illustrating a really complicated long division problem so they could reminded about the number of leading zeroes in such a problem.

Gritting my teeth, I started on the answer:

At this point, I was asked the other question that I had anticipated but utterly dreaded… motivated by child-like curiosity mixed perhaps with a touch of sadism:

How long do we have before the digits start repeating?

My stomach immediately started churning.

I told the class that I’d have to figure this one later. But I told them that the answer would definitely be less than 135,751 times. My class was surprised that I could even provide this level of (extremely) modest upper limit on the answer. After some prompting, my class saw the reasoning for this answer: there are only 135,751 possible remainders after performing the subtraction step in the division algorithm, and so a remainder has to be repeated after 135,751 steps. Therefore, the digits will start repeating in 135,751 steps or less.

What I knew — but probably couldn’t explain to these elementary-school students, and so I had to work this out for myself and then get back to them with the answer — is that the length of the repeating block $n$ is the least integer so that

$135751 \mid 10^n - 1$

which is another way of saying that we’ve used the division algorithm enough times so that a remainder repeats. Written in the language of group theory, $n$ is the least integer that satisfies

$10^n \equiv 1 \mod 135751$

(A caveat:this rule works because neither 2 nor 5 is a factor of 135,751… otherwise, those factors would have to be taken out first.)

Some elementary group theory can now be used to guess the value of $n$. Let $G$ be the multiplicative group of integers modulo $135,751$ which are relatively prime which. The order of this group is denoted by $\phi(135751)$, called the Euler totient function. In general, if $m = p_1^{a_1} p_2^{a_2} \dots p_r^{a_r}$ is the prime factorization of $m$, then

$\phi(m) = n \left( \displaystyle 1 - \frac{1}{p_1} \right) \left( \displaystyle 1 - \frac{1}{p_2} \right) \dots \left( \displaystyle 1 - \frac{1}{p_r} \right)$

For the case at hand, the prime factorization of $135,751$ can be recovered by examining the product of the fractions near the top of this post:

$135751 = 7 \times 11 \times 41 \times 43$

Therefore,

$\phi(135,751) = 6 \times 10 \times 40 \times 42 = 100,800$

Next, there’s a theorem from group theory that says that the order $n$ of an element of a group must be a factor of the order of the group. In other words, the number $n$ that we’re seeking must be a factor of $100,800$. This is easy to factor:

$100,800 = 2^6 \times 3^2 \times 5^2 \times 7$

Therefore, the number $n$ has the form

$n = 2^a 3^b 5^c 7^d$,

where $0 \le a \le 6$, $0 \le b \le 2$, $0 \le c \le 2$, and $0 \le d \le 1$ are integers.

So, to summarize, we can say definitively that $n$ is at most $100,800$, and that were have narrowed down the possible values of $n$ to only $7 \times 3 \times 3 \times 2 = 126$ possibilities (the product of one more than all of the exponents). So that’s a definite improvement and reduction from my original answer of $135,751$ possibilities.

At this point, there’s nothing left to do except test all 126 possibilities. Unfortunately, there’s no shortcut to this; it has to be done by trial and error. Thankfully, this can be done with Mathematica:

The final line shows that the least such value of $n$ is 210. Therefore, the decimal will repeat after 210 digits. So here are the first 210 digits of $\displaystyle \frac{4}{135,751}$ (courtesy of Mathematica):

0.000029465712959757202525211600651192256410634175807176374391348866675015285338597874048809953517837805983013016478699972744215512224587664\
179269397647162820163387378361853688002298325610861061796966504850792996…

Lessons from teaching gifted elementary school students (Part 4b)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received:

What is the chance of winning a game of BINGO after only four turns?

When my class posed this question, I was a little concerned that the getting the answer might be beyond the current abilities of a gifted elementary student.  Still, what I love about this question is that it gave me a way to teach my class some techniques of probabilistic reasoning that probably would not occur in a traditional elementary school setting.

As discussed yesterday, for a non-standard BINGO game with 44 numbers, the answer is

$\displaystyle 4 \times \frac{4}{44} \times \frac{3}{43} \times \frac{2}{42} \times \frac{1}{41}$

For a standard BINGO board with 75 numbers, the denominators are instead 75, 74, 73, and 72.

Now, for the next challenge: getting my students to simplify this product. I’m always mystified when college students blindly multiply numerators and denominators together without bothering to attempt to cancel common factors. Fortunately, this class already understands how to simplify fractions, and so the next step was easy:

$\displaystyle 4 \times \frac{1}{11} \times \frac{3}{43} \times \frac{1}{21} \times \frac{1}{41}$

So I was ready for the next step: cancelling 3 from the numerator and denominator. To my surprise, this was a major stumbling block. I tried probing around to prod them to perform this cancellation, but no luck. Eventually, I guessed the issue that my class was facing: they were familiar with the mechanics of both adding and multiplying fractions and also with writing fractions in lowest terms, but they weren’t yet comfortable enough with fractions to cancel 3 from the numerator of one fraction and the denominator of a different fraction.

So, toward this end, I asked my class if it was OK to shuffle a couple of the numerators and rewrite this product as

$\displaystyle 4 \times \frac{1}{11} \times \frac{1}{43} \times \frac{3}{21} \times \frac{1}{41}$

It took a moment, but then they agreed that this was OK because the order of multiplication doesn’t matter, even volunteering the word commutative to explain their reasoning. (I’m going to try to remember this technique for future reference as a way to get students new to fractions more comfortable with similar cancellations.) Once they got past this conceptual barrier, it was straightforward to continue the simplification:

$\displaystyle 4 \times \frac{1}{11} \times \frac{1}{43} \times \frac{1}{7} \times \frac{1}{41}$

$= \displaystyle \frac{4}{135,751}$

So I explained that if a game of BINGO took one minute, we could play round the clock for 135,751 minutes (about 96 days) and expect to win in the minimal number of turns only four times. Not very likely at all. (Though I didn’t discuss this with my class, the answer is even smaller with a standard BINGO game with 75 numbers: you’d expect to win only once every 211 days.)

Lessons from teaching gifted elementary school students (Part 4a)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received:

What is the chance of winning a game of BINGO after only four turns?

I leave a thought bubble in case you’d like to think this. One way of answering this question appears after the bubble.

When my class posed this question, I was a little concerned that my class was simply not ready to understand the solution (described below), as it takes more than a little work to get at the answer. Still, what I love about this question is that it gave me a way to teach my class some techniques of probabilistic reasoning that probably would not occur in a traditional elementary school setting. Also, I was reminded that even these gifted students might need a little help with simplifying the answer. So let me discuss how I helped these young students discover the answer. I found the ensuing discussion especially enlightening, and so I’m dividing this discussion into several posts.

Here’s a non-standard BINGO board:

Using the free space in the middle, there are four ways of winning the game in four moves:

• Horizontally (11-12-13-14)
• Vertically (3-8-17-22)
• Diagonally (1-7-18-24)
• Diagonally (5-9-16-20)

A standard BINGO board has 75 possible numbers (B 1-15, I 16-30, N 31-45, G 46-60, O 61-75). However, the board that I was using with my class (which was being used for pedagogical purposes) only had 44 possibilities. So the solution below assumes these 44 possibilities; the answer for a standard BINGO board is obvious.

My class quickly decided to start by solving the problem for the horizontal case. I began by asking for the chance that the first number will be on the middle row; after some thought, the class correctly answered $\displaystyle \frac{4}{44}$.

Next, I asked the chance that the next number would also be on the middle row. To my surprise, this wasn’t automatic for my young but gifted students. They felt that they didn’t know where the first number was, and so they felt like they couldn’t know the chance for the second number. To get them over this conceptual barrier (or so I thought), I asked them to pretend that the first number was 11. Then what would be the odds that the next number fell on the middle row? After some discussion, the class agreed that the answer was $\displaystyle \frac{3}{43}$.

Once that barrier was cleared, then the class saw that the next two fractions were $\displaystyle \frac{2}{42}$ and $\displaystyle \frac{1}{41}$. I then explained that, to get the answer for the four consecutive numbers on the middle row, these fractions have to be multiplied:

$\displaystyle \frac{4}{44} \times \frac{3}{43} \times \frac{2}{42} \times \frac{1}{41}$

I didn’t justify why the fractions had to be multiplied; my class just accepted this as the way to combined the fractions to get the answer for all four events happening at once.

Then I asked about the other three possibilities — the middle column and the two diagonals. The class quickly agreed that the answer should be the same for these other possibilities, and so the final answer should just be four times larger:

$\displaystyle 4 \times \frac{4}{44} \times \frac{3}{43} \times \frac{2}{42} \times \frac{1}{41}$

At this point, I was ready to go on, but then a student asked something like the following:

Shouldn’t the answer be $\displaystyle \frac{1}{44} \times \frac{1}{43} \times \frac{1}{42} \times \frac{1}{41}$? I mean, we chose 11 to be the first number so that we can figure out the chance for the second number, and the chance that the first number is 11 is $\displaystyle \frac{1}{41}$.

Oops. While trying to clear one conceptual hurdle (getting the answer of $\displaystyle \frac{3}{43}$ for the second number), I had inadvertently introduced a second hurdle by making my class wonder if the first number had to be a specific number.

I began by trying to explain that the first number really didn’t have to be 11 after all, but that only seemed to re-introduce the original barrier. Finally, I found an answer that my class found convincing: Yes, the chance that the first number is 11, the second number is 12, the third number is 13, and fourth number is 14 is indeed $\displaystyle \frac{1}{44} \times \frac{1}{43} \times \frac{1}{42} \times \frac{1}{41}$. But there are other ways that all the numbers could land on the middle row:

• The first number could be 12, the second number could be 11, the third number could be 13, and the fourth number could be 14.
• Quickly, light dawned, and my class began volunteering other orderings by which all the numbers land in the middle row.
• We then enumerated the number of ways that this could happen, and we found that the answer was indeed 24.
• I then tied the knot by noting that $4 \times 3 \times 2 \times 1 = 24$, and so gives another explanation for the numerators in the answer.

Having found the answer, it was now time to simplify the answer. More on this in tomorrow’s post.

Arithmetic with big numbers (Part 3)

In the previous two posts, we considered the use of base-$10^n$ arithmetic so that a calculator can solve addition and multiplication problems that it ordinarily could not handle. Today, we turn to division. Let’s now consider the decimal representation of $\displaystyle \frac{8}{17}$.

There’s no obvious repeating pattern. But we know that, since 17 has neither 2 nor 5 as a factor, that there has to be a repeating decimal pattern.

So… what is it?

When I ask this question to my students, I can see their stomachs churning a slow dance of death. They figure that the calculator didn’t give the answer, and so they have to settle for long division by hand.

That’s partially correct.

However, using the ideas presented below, we can perform the long division extracting multiple digits at once. Through clever use of the calculator, we can quickly obtain the full decimal representation even though the calculator can only give ten digits at a time.

Let’s now return to where this series began… the decimal representation of $\displaystyle \frac{1}{7}$ using long division. As shown below, the repeating block has length $6$, which can be found in a few minutes with enough patience. By the end of this post, we’ll consider a modification of ordinary long division that facilitates the computation of really long repeating blocks.

Because we arrived at a repeated remainder, we know that we have found the repeating block. So we can conclude that $\displaystyle \frac{1}{7} = 0.\overline{142857}$.

Students are taught long division in elementary school and are so familiar with the procedure that not much thought is given to the logic behind the procedure. The underlying theorem behind long division is typically called the division algorithm. From Wikipedia:

Given two integers $a$ and $b$, with $b \ne 0$, there exist unique integers $q$ and $r$ such that $a = bq+r$ and $0 \le r < |b|$,  where $|b|$ denotes the absolute value of $b$.

The number $q$ is typically called the quotient, while the number $r$ is called the remainder.

Repeated application of this theorem is the basis for long division. For the example above:

Step 1.

$10 = 1 \times 7 + 3$. Dividing by $10$, $1 = 0.1 \times 7 + 0.3$

Step 2.

$30 = 4 \times 7 + 2$. Dividing by $100$, $0.3 = 0.04 \times 7 + 0.02$

Returning to the end of Step 1, we see that

$1 = 0.1 \times 7 + 0.3 = 0.1 \times 7 + 0.04 \times 7 + 0.02 = 0.14 \times 7 + 0.02$

Step 3.

$20 = 2 \times 7 + 6$. Dividing by $1000$, $0.02 = 0.002 \times 7 + 0.006$

Returning to the end of Step 2, we see that

$1 = 0.14 \times 7 + 0.02 = 0.14 \times 7 + 0.0002 \times 7 + 0.006 = 0.142 \times 7 + 0.006$

And so on.

By adding an extra zero and using the division algorithm, the digits in the decimal representation are found one at a time. That said, it is possible (with a calculator) to find multiple digits in a single step by adding extra zeroes. For example:

Alternate Step 1.

$1000 = 142 \times 7 + 6$. Dividing by $1000$, $1 = 0.142 \times 7 + 0.006$

Alternate Step 2.

$6000 = 587 \times 7 + 1$. Dividing by $100000$, $0.006 = 0.000587 \times 7 + 0.000001$

Returning to the end of Alternate Step 1, we see that

$1 = 0.142 \times 7 + 0.006= 0.142 \times 7 + 0.000587\times 7 + 0.000001 = 0.142857 \times 7 + 0.000001$

So, with these two alternate steps, we arrive at a remainder of $1$ and have found the length of the repeating block.

The big catch is that, if $a = 1000$ or $a = 6000$ and $b = 7$, the appropriate values of $q$ and $r$ have to be found. This can be facilitated with a calculator. The integer part of $1000/7$ and $6000/7$ are the two quotients needed above, and subtraction is used to find the remainders (which must be less than $7$, of course).

At first blush, it seems silly to use a calculator to find these values of $q$ and $r$ when a calculator could have been used to just find the decimal representation of $1/7$ in the first place. However, the advantage of this method becomes clear when we consider fractions who repeating blocks are longer than 10 digits.

Let’s now return to the question posed at the top of this post: finding the decimal representation of $\displaystyle \frac{8}{17}$. As noted in Part 6 of this series, the length of the repeating block must be a factor of $\phi(17)$, where $\phi$ is the Euler toitent function, or the number of integers less than $17$ that are relatively prime with $17$. Since $17$ is prime, we clearly see that $\phi(17) = 16$. So we can conclude that the length of the repeating block is a factor of $16$, or either $1$, $2$, $4$, $8$, or $16$.

Here’s the result of the calculator again:

We clearly see from the calculator that the repeating block doesn’t have a length less than or equal to $8$. By process of elimination, the repeating block must have a length of $16$ digits.

Now we perform the division algorithm to obtain these digits, as before. This can be done in two steps by multiplying by $10^8 = 100,000,000$.

So, by the same logic used above, we can conclude that

$\displaystyle \frac{8}{17} = 0.\overline{4705882352941176}$

In other words, through clever use of the calculator, the full decimal representation can be quickly found even if the calculator itself returns only ten digits at a time… and had rounded the final $2941176$ of the repeating block up to $3$.

(Note: While this post continues exploring the unorthodox use of a calculator to handle arithmetic problems, it also appeared in a previous series on the decimal expansions of rational numbers.)