You always set your alarm clock to wake you up one hour before you have to leave. But if you have to leave before 7 am, you give yourself 15 extra minutes to get ready since you know you’ll be groggy.

What’s the input for the process described above? What’s its output?

What time would you have to leave if the clock woke you up at 5:40am? 5:50am?

Your alarm wakes you up. Based on the time you see on the clock, how do you know when you’ll have to leave?

You’ve lost your calculator, and your diabolical arch nemesis has decided to exploit this opportunity. He’ll make calculations for you — for a price! Multiplication costs $\$1$, whereas exponentiation costs $\$6$. Unfortunately, you desperately need to compute ${7^{10}}$, and you’ve only got $\$5$. What will you do?

You input any word, and the AlphaBlast algorithm outputs the same word but with all the ‘a’s replaced with ‘z’s. Is AlphaBlast reversible? Example: AlphaBlast(“mathematics”) = “mzthemztics”. Test it carefully and then explain your answer. (An algorithm is called reversible if it’s possible to create an inverse algorithm for it.)

For each of the following algorithms, assume that the input can be any number, and call it $X$. Read each description, and decide in each case whether the algorithm is reversible. If so, write the inverse.

The Foo algorithm either multiplies $X$ by 2 (if it’s a whole number) or doesn’t change it (if it’s not a whole number).

The Bar algorithm either multiplies $X$ by 2 (if it’s NOT a whole number) or doesn’t change it (if it IS a whole number).

The FractionsAreFun algorithm takes $X$, adds 10, and divides that answer by 4, and outputs the result.

The NoReallyTheyAre algorithm divides $X$ by 20 then adds 1 and outputs the result.

The Flip algorithm outputs the value of 100/$X$, unless $X$ is zero, in which case the output is just zero.

The Flop algorithm divides 20 by $X$, then adds 1 and outputs the result.

The Square algorithm simply outputs the value of ${X^2}$.

Here’s a variation on the Number Devil game: the Number Devil is allowed to change its secret number after each time you guess. However, it can’t change it in a way that makes any of its previous answers untrue. (So, if you guessed “5” the first time and the answer was “higher”, it could not change its answer to “2”, but it $could$ change it to “7”.)

Explain why binary search algorithm’s worst-case guarantee is still the same.

Describe an algorithm the Number Devil could use to force a worst-case outcome every time, as long as you didn’t get lucky and guess right the first time.

Here’s a tougher variation of the game you played in problem 8. The setup is the same: your partner shuffles the cards and lines them up, and you can’t look at them. But now, instead of just finding the largest one, your goal is to sort all the cards into descending order (i.e., line them up from largest to smallest). Your basic operations are (i) to ask your partner to compare two cards (just like last time), and (ii) to swap the positions of any two cards.

Write an algorithm for this game. That is, create an algorithm that will sort a list of 5 numbers. After writing the algorithm, go ahead and try it out with a group member. Does it work?

Look back at your pancake-flipping algorithm from problem 34. If you extended your algorithm to stacks of $N$ pancakes, how many flips, maximum, could you guarantee it taking — that is, what’s the worst it could do?

Here’s a different version of the pancake problem. This time, you have three plates. Plate #1 has a stack of 5 pancakes, in order from the largest one on the bottom to the smallest on top. This time, though, you can only use the spatula to shift one pancake at a time to another plate. At no time can any larger pancake be on top of a smaller pancake. How many moves does it take to get the entire stack of pancakes from Plate #1 to Plate #3?

Don’t use a calculator for this problem.

Simplify $\frac{{20{a^4}{b^7}}}{{30{a^3}{b^{ - 2}}}}$

Reduce the fraction $\frac{x^3 +2x}{x^2 + x}$

Solve for $x$: ${x^{\frac{2}{3}}} = 64$

Solve for $x$: ${x^2} + 8x + 9 = 0$

Solve for $x$: $3{x^2} + 7x + 3 = 0$

If you double the size of a list in which you’re doing a binary search, will it (in the worst-case scenario) take you about twice as long to do the search?

The shape below is called a “tromino.”

Each of the following “checkerboards” has had one square removed. For each board, find a way to cover all of the remaining squares with trominoes.

You have only a compass and an unmarked straightedge. Come up with an algorithm for finding a point equidistant from three given points. In doing so, you will have proven that it is always possible to find such a point.

Alice is in the top right square of a giant chessboard, and the white rabbit she’s chasing is in the bottom left square. Each turn, Alice gets to move one square up, down, left, or right. Then, after that, the white rabbit gets to move (up, down, left, or right). Alice catches the rabbit when she’s able to move into the square he’s sitting in. Assuming that both Alice and the white rabbit are strategically quite savvy, predict the outcome.

The Floor operation takes any number whatsoever as an input. ${\mathop{\rm Floor}\nolimits} (x)$ simply takes $x$ and returns the greatest integer that’s less than or equal to $x$. In other words, the Floor function always “rounds down.” Examples: ${\mathop{\rm Floor}\nolimits} (2.001) = 2$, $\mathrm{Floor}(\pi ) = 3$, and $\mathrm{Floor}(5.9999)=5$.

The following algorithm, which uses Floor and some basic arithmetic operations, only takes positive integers for its input. What does it do?

${\mathop{\rm Mystery}\nolimits} (n) = 5\left( {\frac{n}{5} - {\mathop{\rm Floor}\nolimits} \left( {\frac{n}{5}} \right)} \right)$

The RightShift and LeftShift operations work for any non-negative integers with five or fewer digits:

${\mathop{\rm RightShift}\nolimits} (N,d)$ chops off the rightmost $d$ digits of $N$ and outputs the result. Example: ${\mathop{\rm RightShift}\nolimits} (3214,2) = 32$.

${\mathop{\rm Left}\nolimits} {\mathop{\rm Shift}\nolimits} (N,d)$ moves each digit $d$ places to the left, and fills in 0’s in the empty spaces; then, it chops off all but the last five digits. Examples: ${\mathop{\rm Left}\nolimits} {\mathop{\rm Shift}\nolimits} (75,3) = 75000$, and ${\mathop{\rm Left}\nolimits} {\mathop{\rm Shift}\nolimits} (3214,2) = 21400$.

Starting with the number 6789, how can you use only the LeftShift and RightShift operations to end up with the number 7?

Generalize your work from part a to create the PickADigit algorithm, where ${\mathop{\rm PickADigit}\nolimits} (N,d)$ outputs the $d$th digit of a positive integer $N$.

What does the following algorithm do, assuming that $N$ is a positive, five-digit integer?

You input a whole number to a certain algorithm. If it’s even, the algorithm doesn’t change the number. If it’s odd, the algorithm turns the number backwards — for example, 57 becomes 75. Is this algorithm reversible?

Come up with a non-trivial numerical algorithm that reverses itself. In other words, come up with an algorithm Boing such that, for every $N$,
$\text{(Boing(Boing}(N))= N$.

Imagine your friend gave you a very long table of $all$ the possible inputs to her algorithm and their corresponding outputs. Even if she didn’t explain the process her algorithm used, describe using a single sentence how you could figure out whether or not the algorithm was reversible.

Your basic operations for the following are addition, subtraction, multiplication, division, and testing which of two numbers is the biggest.

Write an algorithm for figuring out whether or not a positive integer $N$ is prime. Pick some three-digit numbers and try it out. (By the way, computer systems actually use algorithms like these to encrypt your private data.)

Suppose it takes you 3 seconds to use your calculator to do each of the basic operations above. How long would it take you to check whether or not 1,000,003 is prime? How about 1,000,005?

You have 4 identical-looking coins. Two of them are heavy and two of them are light (the two heavy ones weigh the same, and the two light ones weigh the same).

Call the coins A, B, C, and D. Your goal is to find out which two are heavy and which two are light. Your only instrument is a balance scale — you put some coins on the two sides of the scale, and it tells you which side is heavier (or that the two sides weigh the same).

Describe an algorithm for finding the light coins in as few steps as possible.

When you type a text message into a cell phone using multi-tap typing, you are essentially encoding English words into a long sequence of numbers (and pauses). For example, to type in the word “EIGHT”, I type: 3 3 4 4 4 [pause] 4 [pause] 4 4 8. Use this picture of a cell phone’s keypad to help you:

I typed 7 7 7 7 , 7 3 3 , 3 3 2 2 2 4 4. (Here the commas represent pauses). What word did I type?

Write an algorithm for “decoding” a string of numbers and pauses into a word.

You and a fellow explorer need to be able to communicate two numbers to each other — coordinates for your location, which will always be positive whole numbers, but can be small or large. The only means of communication you have is a carrier pigeon. Due to its tiny brain, the pigeon can only remember one $whole$ number (though it can be as big as you want).

Somehow, you need to fit the two numbers together into one number, but you need to make sure that the process is reversible, so that your companion can figure out what numbers you’re sending him.

Here’s the first process you try. Say your two numbers are 67 and 302. Then you just put them together to make 67302, and send that number along with the pigeon.

Why is this non-reversible?

The next strategy you develop fails as well. What you tried to do was separate the numbers with “000”. So, 67 and 302 gets written as 67000302.

This strategy will usually work, but not for every pair of numbers. When is this strategy non-reversible?

Create your own strategy, and show that it works — that it is reversible.

Look back at the sorting algorithm you wrote for problem 39.

Are there certain initial arrangements of the cards that make your algorithm finish in fewer steps?

Using your algorithm, what’s the maximum number of comparisons you have to make, in the worst case, when you play the game with five cards?

If you used your sort algorithm from problem 39 to sort a list with $N$ items in it, how many comparisons would it take? See if you can express your answer as a simple algebraic formula.

Five pirates come across 100 bars of gold. The pirates have a pecking order, with #5 and #1 indicating the top and bottom-ranked pirates, respectively. Each pirate wants to maximize his or her share of the gold bars. There are no coalitions or collusions between them. They are all very analytical — they can think things through!

Their process for splitting the loot is somewhat democratic. It begins with the top-ranked pirate making a proposal on how to divvy up the loot. (Note that the gold bars cannot be broken up, glued together, or otherwise changed; there are 100 bars of gold, period.) Each pirate gets one vote, up or down on the entire proposal. Remember, each pirate votes based on his or her own pocket and there are no side agreements of any sort. If the proposal gets 50% or more votes, it wins, and that’s that. On the other hand, if it fails to muster 50%, then the pirate who made the proposal is thrown overboard, and the process continues with the next pirate down the hierarchy.

What is the maximum number of bars that the most powerful pirate can get and what allocation to each pirate will ensure him the 50% vote that he needs?

(from http://www.eogogics.com/talkgogics/ezine/tech-talk/pirates1)

Create an algorithm to find the median of a list of numbers. Your only basic operation allowed is to compare two numbers to see which is larger. Assume the list has an odd number of items in it.

Write an algorithm that finds the second largest number in a list of 16 numbers, using only comparison as the basic operation. It’s possible to guarantee a correct answer in fewer than 29 comparisons — can your algorithm do this?

Sherlock and Watson create the following code to encrypt their messages:

First, turn each letter into a number (A is 1, B is 2, etc). Then for each number, multiply it by 7 and add 1. Finally, if any numbers have 3 digits, just ignore the hundreds digit — so 141 just gets written as 41, and so on.

Encrypt the word NO according to their code.

Sherlock sends Watson the message 36 34 22 8 13 36. Decode it.

Even though the code "erases” hundreds digits, it’s still perfectly reversible — you can always decode any message and know exactly what was written. Explain why it’s reversible.

You create an especially tricky locker code. Here’s what you do to encode the 3-number combination: The new first number will be the sum of all three numbers in the original.

The new second number will be the sum of the first two numbers in the original.

The new third number will be the sum of the last two numbers in the original.

Encode 12 – 8 – 1. Do you see how you could find the 12, 8, and 1 from the coded version?

Decode 17 – 14 – 5.

You receive a coded combination: A – B – C (A, B, and C represent the numbers you receive). Write instructions or equations for decoding it.

This is a famous problem that’s challenged many mathematicians. You have 12 coins that look alike. 11 are genuine and each have the same weight. 1 is counterfeit, and is $either$ too heavy or too light.

Write an algorithm for how to use a balance scale to find the fake coin, $and$ determine whether it’s too heavy or too light, in as few steps as possible. (It can be done with three weighings! See if you can figure out how.)

Hint: it will probably help a lot to make a chart to keep track of the different possibilities.

If ${\log _5}\left( x \right) = 5$ and ${\log _5}\left( y \right) = 7$, then what is the value of ${\log _5}\left( {\frac{y}{x}} \right)$?

If ${\log _3}\left( x \right) = 1.776$ and ${\log _3}\left( y \right) = 2.018$, then what is the value of ${\log _3}\left( {\frac{y}{x}} \right)$? (By the way: how old is the United States of America?)

Based on what you did in problems 28 and 29, complete the following generalization: “If ${\log _b}\left( x \right) = C$ and ${\log _b}\left( y \right) = D$, then ${\log _b}\left( {xy} \right) = $….” Now prove it using algebra.

Revise the generalization you wrote in the previous problem into an identity that relates ${\log _b}\left( {x \cdot y} \right)$ to ${\log _b}\left( x \right)$ and ${\log _b}\left( y \right)$. (Remember that an identity is just an equation that is always true, for all values of the variables involved.) This identity is going to come in handy, so write it down somewhere where it will be easy to refer to it.

Given that ${\log _2}\left( 5 \right) = 2.322$ and ${\log _2}\left( 3 \right) = 1.585$, what is the value of ${\log _2}\left( {15} \right)$?

State and prove an identity that relates ${\log _b}\left( {\frac{x}{y}} \right)$ to ${\log _b}\left( x \right)$ and ${\log _b}\left( y \right)$.

If ${\log _3}\left( {10} \right) = 2.096$, then what is the value of ${\log _3}\left( {30} \right)$? How about ${\log _3}\left( {100} \right)$?

Don’t use a calculator for this problem.

Simplify $16^\frac{1}{2} \cdot 2^3$.

Simplify $\frac{{{x^5}{y^{ - 3}}}}{{{x^{ - 1}}{y^2}}}$.

Solve for x: $4x^3 + 2x^2 = 0$.

Simplify $\frac{{\sqrt {125} }}{{\sqrt {50} }}$.

If $\frac{1}{{{x^2}}} - \frac{1}{x} = 1$, find ${x^2} + x + 1$.

What is the value of ${\log _2}\left( {{4^{1005}}} \right)$?

For each of the following equations, use the log function of your calculator (and possibly some algebra) to approximate $x$ to the nearest thousandth.

${10^x} = 461.2$

$3 \cdot {10^x} = 5$

${10^{x + 2}} = 50$

Mr. Golthramis was in a bad mood one day, and decided to take it out on his students by giving them this problem: “Write down, using no exponents, a number $x$ such that $\log_{10}(x) > 1000$.” The students, having recently learned the definition of log, were outraged, and refused to do the homework. Why?

Verify with your calculator that ${\log _3}\left( {12} \right) = 2.2619$. Now, find the values of $\log_3 (36)$ , ${\log _3}\left( 4 \right)$, and $\log_3 (108)$.

According to the incomplete table below, ${\log _5}\left( {10} \right) = 1.4307$. Is this (approximately) correct? Correct it if not, and then complete the rest of the table.

Suppose we visualize some number $L$ as a tree diagram with $L$ leaves, and another number $M$ as a tree with $M$ leaves. Using these as building blocks, how could you build a tree to visualize the quantity $L \cdot M$? Can you use this to illustrate the multiplication and division identities of logarithms you proved? (It might help to use specific numbers first: try $L = 27$ and $M = 9$.)

Consider a balanced binary tree with a depth of $D$.

True or false: the total number of nodes in the tree will be $1 + 2 + {2^2} + ... + {2^D}$.

Find a simple formula for the total number of nodes in the tree. Answer in terms of $D$, and without using “…”. (Hint: try several small examples, and look for a pattern.)

If a balanced binary tree has 1023 nodes total, then how many of the nodes are leaves?

Have one of your group members make up a binary tree and show it to you. Your job is to add nodes to the tree until you have doubled the total number of nodes, while keeping the tree as “shallow” as possible. Try this a few times with trees of different sizes and shapes. If the original tree has $N$ nodes, then how many additional levels of depth do you need?

If you build a binary tree by adding the numbers 5, 2, 3, 7, 11, 17, and 13, in that order, the resulting tree would not be balanced. (Check this.) Instead of this, suppose you put these seven numbers into a hat and randomly chose one number at a time to add to the tree. What is the probability that your tree would be balanced?

Prove that each of the following are true:

${\log _b}\left( {{x^2}} \right) = 2 \cdot {\log _b}\left( x \right)$

${\log _b}({x^3}) = 3 \cdot {\log _b}(x)$

${\log _b}\left( {{x^4}} \right) = 4 \cdot {\log _b}\left( x \right)$

${\log _b}\left( {{x^5}} \right) = 5 \cdot {\log _b}\left( x \right)$

Use the rule you just proved in the previous problem to solve each of the following for $x$, and give your answer to the nearest thousandth. (Hint: $A = C$ if and only if ${\log _b}A = {\log _b}C$.)

${1.02^x} = 2$

${2^x} = 1000000$

${1.5^{x - 3}} = 21$

What is ${\log _{10}}\left( {{{\log }_{10}}\left( {{\mathrm{one \, googol }}} \right)} \right)$? What is ${\log _{10}}\left( {{{\log }_{10}}\left( {{{\log }_{10}}\left( {{\mathrm{one \, googolplex}}} \right)} \right)} \right)$?

(If you don’t know what a “googol” or “googolplex” is, Google them.)

Professor Arlo G. Smith poses the following questions:

What is the ratio of ${2^9}$ to ${2^5}$? What is the ratio of ${2^m}$ to ${2^n}$?

What is the ratio of $\log {2^9}$ to $\log {2^5}$? What is the ratio of $\log {2^m}$ to $\log {2^n}$?

What is the ratio of $100000000$ to $1000000$? What is the ratio of $\log 100000000$ to $\log 1000000$?

If:${\log _b}\left( X \right) = 3 \cdot {\log _b}\left( 2 \right) + 2 \cdot {\log _b}\left( 3 \right) + {\log _b}\left( 5 \right)$ then what is $X$?

Rewrite the expression ${\log _5}7 + {\log _5}15 - {\log _5}3$ as a single logarithm in the form ${\log _b}a$.

Not all calculators have a built-in way to calculate ${\log _2}\left( {47} \right)$. However, using the definition and properties of logarithms, there is a way to figure this out with any scientific calculator. Here’s a hint: re-write ${\log _2}\left( {47} \right) = x$ in exponential form, and then solve for $x$.

Can the ${\log _{10}}$ of an irrational number minus the ${\log _{10}}$ of a different irrational number ever equal a positive integer? Explain.

Solve each of the following equations, giving your answer to the nearest thousandth.

${1500 \cdot {1.13^t} = 4000}$

$3 \cdot {5^{x + 5}} = 8$

${\log _3}x - 2{\log _3}7 = 1$

${5^{x - 1}} = {2^{3x - 1}}$

$7 \cdot {x^3} = 1492$

A binary tree has 6000 nodes in it. What are its minimum and maximum possible depths?

Recall the Number Devil guessing game from the previous lesson, where the Number Devil picks a number between 1 and 15 and you have to guess it. When you guess, the Number Devil will tell you whether you’re correct, too high, or too low. If you use binary search, how many guesses will you need in the worst case? What if the Number Devil chose a number between 1 and 1 million?

That pesky bad coin you saw in the previous lesson is back. (Maybe the Number Devil brought it along.) You have 27 identical-looking coins. The bad coin is too light, and the rest all weigh exactly the same.

Using a balance scale, how many weighings do you need to find the bad coin?

How many weighings would it take to find one bad coin among 2187 coins? How about 1 million coins?

If you look up logarithms on the Web, you’re likely to see the following sentence, which is meant to be a helpful reminder when you’re learning what logarithms are:

“A logarithm is an exponent.”

What do you think people mean by this?

If $a_1,a_2, a_3, \ldots$ is a geometric sequence, then what kind of sequence is $\log_b(a_1), \log_b(a_2), log_b(a_3), \ldots$?

Recall that the Floor operation from the previous lesson takes a positive number $x$ and chops off anything after the decimal point. Similarly, the Ceiling function essentially “rounds up”: e.g., ${\mathop{\rm Ceiling}\nolimits} \left( 3 \right) = 3$, and ${\mathop{\rm Ceiling}\nolimits} \left( {2.0001} \right) = 3$. If $N$ is a positive integer, what does ${\mathop{\rm Ceiling}\nolimits} \left( {{{\log }_{10}}\left( N \right)} \right)$ tell you about $N$?

If you double a three-digit number 100 times, how many digits will the resulting number have?

Prove that squaring a number at most doubles the number of digits in the number.

Prove that ${\log _b}\left( {\frac{1}{x}} \right) = - {\log _b}\left( x \right)$.

Generalize what you did in problem 59 into an identity about logarithms.

What is ${\log _{10}}\left( 2 \right) \cdot {\log _2}\left( {10} \right)$?
How about ${\log _{10}}\left( 3 \right) \cdot {\log _3}\left( {10} \right)$?
And ${\log _7}\left( 3 \right) \cdot {\log _3}\left( 7 \right)$?

In a balanced ternary tree, every non-leaf node has three children, and all the leaves have the same depth. How many nodes are in a balanced ternary tree with a depth of 10?

There are 20 cities in a certain country, and every pair of them is connected by an air route. How many air routes are there?

Remember Jan who bats .500 in softball. What’s the probability that she will get exactly 4 hits in 10 at-bats? What’s the probability that she will get no more than 4 hits in 10 at-bats?

How many “words” can you form from 5 A’s and no more than 3 B’s?

There are 6 books on a shelf. How many ways are there to arrange some (or all) of the books in a stack? The stack may consist of one book.

A teacher has a collection of 40 true-false questions. She wishes to create a test using 5 of these questions. How many different tests can she create if

the order of the questions doesn’t matter?

the order of the questions does matter?

How many three-letter words can be formed from the letters A, B, C, D, E, F, G, H, and I, where each letter can only be used once per word?

The points A, B, C, D, E, F, G, H, and I are vertices of a regular polygon. If three of the points are chosen, and connected by line segments, a triangle is determined. How many triangles can be formed in this way? If four points were chosen to form a quadrilateral, then how many such quadrilaterals will there be?

You have six sticks of lengths 1, 2, 3, 4, 5, and 6 inches. How many non-congruent triangles can be formed by using three of these sticks as sides?

There are three rooms in a dormitory: one single, one double, and one for four students (called a “quad”). How many ways are there to house 7 students in these rooms?

Creamy Heaven serves 30 different ice cream flavors. A customer can order a single-, double-, or triple-scoop cone.

How many double-scoop cones are there if both scoops can be the same flavor and the order of the scoops doesn’t matter?

How many possible cones are there if flavors can be repeated and the order of the scoops doesn’t matter?

Three couples go to the movies and sit together in a row of seats. How many ways can they arrange themselves if each couple sits together?

Eight people are at Chen’s house for a party (Chen is one of the eight). Chen has several options for sitting people for dinner.

If Chen gets a long table she can sit people on one side of the table so that they can watch a movie while they’re eating. How many ways can she sit the eight people in this situation?

Chen can get a shorter, but rectangular table, and sit four people on one side and the other four on the opposite side. How many ways can she sit the eight in this situation? Assume that two arrangements that are reflections of each other over the long axis of the table are indistinguishable from each other.

Chen can sit the eight around a circular table. How many ways, now? Assume that two arrangements that are rotations of each other are indistinguishable from each other.

If Chen sits $n$ people around a circular table, then how many ways can this be done if two arrangements that are rotations of each other are indistinguishable?

A bug jumps from lattice point to lattice point on a piece of graph paper according to the following pattern: from $\left( {a,b} \right)$, the bug can jump only to $\left( {a+1, b} \right)$ or to $\left( {a, b+1} \right)$. How many different paths can the bug take if it wishes to start at $\left( {0,0} \right)$ and end up at $\left( {6,4} \right)$? Hint: tinker with this problem a bit so that you can get a feel for what the bug is doing.

Homer starts at the origin and performs a five-step random walk along a number line. Each second he steps either one unit to the left or one unit to the right.

Describe all the places that Homer can wind up at the end of this walk.

How likely is Homer to end up 5 steps to the right? 3 steps to the right?

If Homer were to perform this 5-step random walk 32000 times, what is your prediction of the average of all the final positions? What is your prediction of the average of all the distances from the origin to Homer’s final position?

How many diagonals are there in a pentagon? a hexagon? a decagon? an $n$-gon? A diagonal is a straight line segment that connects any two non-consecutive vertices.

The rules of a checkers tournament indicate that each contestant must play every other contestant exactly once. How many games will be played if there are 12 participants? How many will be played if there are $n$ participants?

Don’t use a calculator for this problem.

Reduce the fraction $\frac{6a^2}{4a^2-6a}$.

Solve for x: ${x^2} - 5x = 14$.

Solve for x: ${x^2} - x - 1 = 0$.

Divide $\frac{2}{x} \div \frac{4}{{{x^2}}}$.

Write as one fraction: ${\left( {\frac{b}{{2a}}} \right)^2} - \frac{c}{a}$.

How many ways can you split up 12 people into six pairs?

You have learned that any positive integer has a prime factorization of the form ${2^a} \cdot {3^b} \cdot {5^c} \cdot {7^d} \cdot {11^e} \cdot {13^f}...$, where the “…” represents the rest of the primes, and $a$, $b$, $c$, $d$, $e$, $f$, and so on can each equal 0, 1, 2, 3, … . So for example, 360 is equal to ${2^3} \cdot {3^2} \cdot {5^1}$.

Remembering that every possible factor of 360 comes from one of the possible combinations of these prime factors (e.g. $20 = {2^2} \cdot {3^0} \cdot {5^1}$ and $90 = {2^1} \cdot {3^2} \cdot {5^1}$), and using the principles of counting that you learned studying combinatorics, determine the number of factors that 360 has. Note that 1 is considered a factor of 360 in this problem, i.e. $1 = {2^0} \cdot {3^0} \cdot {5^0}$. (You might try answering for 84 instead of 360 if you want an easier example to start with.)

Generalizing Problem 44, find a way to determine the number of factors that any positive integer has. Try out your method with at least 3 other positive integers to check to see if it works.

Let $n \choose r$ stand for $\frac{{n!}}{{r!\left( {n - r} \right)!}}$, where $n$ and $r$ are nonnegative integers, and $r \leq n$.

Calculate $6 \choose 2$.

Calculate$7 \choose 1$.

Is $n \choose r$ ever not an integer? Explain.

Prove: $\frac{n(n-1)(n-2) \cdots (n-r+1)}{r(r-1)(r-2) \cdots 2 \cdot 1} = {n \choose r}$.

Determine what should replace the question mark so that the following statement is true, then prove that the statement is true:
${n+1 \choose r} = {? \choose r-1} + {? \choose r}$

How many different 5-person basketball teams can be chosen from a group of 10 people? How many ways can you split up 10 people into two different 5-person basketball teams?

The points A, B, C, D, E, and F are vertices of a regular hexagon. What is the probability that three randomly chosen vertices from this hexagon will form an equilateral triangle? What’s the probability that four randomly chosen vertices from this hexagon will form a rectangle?

This is a continuation of Problem 38. In this problem you will see a connection between algebra and counting.

Expand ${\left( {r + u} \right)^5}$ and explain how this can help you determine how many paths there are from $\left( {0,0} \right)$ to $\left( {2,3} \right)$. Recall that when simplifying and collecting expressions such as $rru$, $rur$, and $urr$, we can write the final result as $3{r^2}u$.

What expression can you expand and simplify in order to answer Problem 38?

What is the coefficient of the ${x^3}{y^5}$ term in the expansion of ${\left( {x + y} \right)^8}$?

What is the coefficient of the ${x^5}{y^7}$ term in the expansion of ${\left( {2x + y} \right)^{12}}$?

What is the sum of all the 3-digit numbers that can be formed using three different odd digits?

Box Problems You probably didn’t realize that there are combinatorial problems that involve boxes, but there are.

Four boxes are numbered 1 through 4. How many ways are there to put 8 identical balls into these boxes (some of the boxes can be empty)? Hint: Imagine that you have 12 slots to work with.

Four boxes are numbered 1 through 4. How many ways are there to put 8 identical balls into these boxes so that none of them is empty?

Below is shown a triangle of dots. Suppose you start at dot A and move down through the triangle in the following manner: from any dot you can only move to the next dot that is down left or down right. So, if you are at dot A you can move to either dots B or C, but not directly to D or E. Below each dot in the triangle write the number of distinct paths from dot A to that dot.

There is a well-known triangle called Pascal’s Triangle. What is this triangle and how does it relate to counting?

Sweden and Croatia are locked in an escalating arms race. Every year, one of the countries builds some bombs and missiles, and then inevitably, the next year, the other country builds even more to compensate. In each country, the Department of Defense has the following strategy:

For every new bomb that the enemy built last year, we’ll build 2 new bombs. For every new missile that the enemy built last year, we’ll build 2 new missiles, AND a new bomb.

Neither country can afford the expense of this pointless arms race, and each one claims that the other country started the whole situation by building the first few weapons.

In 2008, Sweden built a total of 64 new bombs and 16 new missiles. What will happen in 2009? How about 2010?

Those 64 bombs and 16 missiles were constructed in response to the weapons that Croatia built in 2007. What were those weapons?

Continue working back in time to determine who must have started the situation. What year did it start, and what weapons were built?

In problem 12:

If the length of each side of the original triangle is 1 unit, write a recursion equation for ${P_n}$, the perimeter of the shape after $n$ stages. Will the perimeter ever reach 1,000,000 units?

Suppose that the area of the original triangle was 1 cm$^2$, what would be the area of the shape after 1 stage? After 2 stages? After 3 stages?

Write a recursive equation for ${A_n}$, the area of the shape after $n$ stages. Could the area get as large as 5 cm$^2$?

2000 people are exposed to a particularly contagious cold virus. Every day, $\frac{1}{4}$ of the people (rounded to the nearest person) that were healthy the day before, have now caught the virus. ${I_t}$ is the total number of people infected, after $t$ days.

If ${I_1} = 0$ (no one is infected on the first day), find ${I_t}$ up to $t = 5$.

If ${I_1} = 40$, do the same.

Write a recursive equation for ${I_t}$. (In your formula, you may use $\mathrm{Round}(x, 0)$, which is the operation on your calculator that rounds any number $x$ to the nearest integer.)

What happens eventually to these 2000 people?

Suppose that a less contagious cold virus infects 1/20 of the healthy population on a given day.

Find out how many days it takes for a population of 2000 to go from 0 sick people to half of the population being sick.

If you double the population to 4000, how many days do you think it will take for half of the population to get sick? Do the calculations to see if you are right.

You have 10 pet lizards and each gets fed 3 crickets at the end of every week. You buy 80 crickets, thinking that as the crickets reproduce at a rate of 50% per week, the population will sustain itself even though some crickets will be fed to the lizards. But the lizards reproduce at a rate of 10% per week. After the lizards and crickets both reproduce, then the lizards get fed.

At the end of the first week, how large is each population?

Draw a chart to track the populations over the next few weeks. Each week, round to the nearest whole number in your answers.

Write recursive equations for ${L_t}$ and ${C_t}$, the number of lizards and the number of crickets after t weeks respectively. Your equation for ${C_t}$, the number of crickets, will have to depend on how many crickets there were last week AND how many lizards there were this week.

Do you think you’ll always have enough crickets to feed the lizards, even though the lizard population will continue to grow?

A well-fed bacteria colony in a Petri dish grows as follows:

Find a pattern, and fill in the blanks.

Write a recursive equation for ${B_n}$, the number of bacteria after $n$ hours.

Check whether the pattern you discovered in problem 17 satisfies the equation ${B_n} = 60 * {3^{n - 1}}$. Find the size of the colony after 24 hours, by using either your recursive formula or the explicit formula.

Let the sequence $\{ {R_n}\} $ be generated by the quadratic equation ${R_n} = {n^2} + 1$.

Create a table for $\{ {R_n}\} $.

Write a recursive equation for $\{ {R_n}\} $.

Repeat problem 19 for the:

Quadratic equation, ${R_n} = 2{n^2} - 3n + 1$.

Exponential equation ${R_n = 3^n}$.

Exponential equation ${R_n} = 3 \cdot {2^n}$.

For each chart below find a recursive equation and an explicit equation.

You come across the following sequence in a textbook.

Find an explicit formula for ${T_n}$. (It might help to first carefully make a graph with $n$ as your horizontal axis and ${T_n}$ as your vertical axis.)

Find ${T_{100}}$.

A sequence follows this recursive rule: ${A_n} = {A_{n - 1}} - {A_{n - 2}}$.

Pick several different starting values for the sequence, and find the next ten or so values. What always happens?

How can you be sure of your conclusion in part a?

Write a recursive equation to describe the pattern you see in the Fibonacci sequence below.

You take out a loan from a bank. At the end of each year, you pay them \$200, and then they charge 3% interest on the amount that you still owe. For example, if you borrowed \$1200, you would owe \$1,030 after 1 year.

Find out how many years it would take to pay off your loan of $1200. (Once you hit a negative number, just assume the loan is now paid off.)

In part a, did the amount of money owed decrease faster and faster as time went on, or slower and slower? Why?

Write an equation ${M_t}$ for the amount of money you owe after t years.

What happens if instead you borrow $5000? Track the loan over at least ten years.

What happens if you borrow $10,000? Track the loan over at least ten years.

Find an initial loan amount that is an equilibrium solution.

One of the simplest models for population growth is based on the idea that the growth rate of the population is proportional to the current size of the population. So, for example, we might expect that, each year, the number of frogs in a pond will increase by 6% every year.

Write a recursive equation for this model of growth.

Does this equation have any equilibria?

The population model you looked at in the previous problem has a major limitation: it doesn’t take into account the fact that the frogs in the pond have a limited number of resources (food, lily pad real estate, etc.). The following equation, called the logistic model of population growth, attempts to take this into account:

${F_{n + 1}} = {F_n} + 1.1{F_n} \cdot \left( {\frac{{40 - {F_n}}}{{40}}} \right)$

The idea here is that, the pond has a “carrying capacity” of 40 frogs — i.e., it has enough resources for 40 frogs to live healthily. So, while the population’s growth rate is proportional to the current population size, it is also proportional to how close the population is to the carrying capacity.

Suppose that there were 15 frogs in the pond. According to the equation, how much would the population change the next year? How about if there were 35 frogs in the pond?

Does it seem plausible that this system (unlike the one in the previous problem) would have an equilibrium solution other than 0?

Starting with an initial population of 2 frogs, use the equation above to track the frog population over several years. What happens in the long run?

Predict what would happen if you repeated part c, but with an initial population of 60 frogs. Then try it and see.

Connect the midpoints of the sides of a triangle. Now connect the midpoints of the sides of your new triangle. If you could repeat this operation indefinitely it seems as though you would end up with a point. Where in the original triangle would that point be located?

Three kids sitting in a circle play a card game in which they are given a number of cards and asked on each turn to pass half of their cards to the kid sitting to their right. If they have an odd number of cards they must round up — for example, a kid who has 5 cards must pass 3. How is this game going to turn out?

Find the lowest value ever reached by the sequence $\{ {S_n}\} $, and explain why you know it’s the lowest value, given that:

${S_1} = 8000$
${S_n} = {S_{n - 1}} \cdot \frac{n}{{10}}$

A bank’s loan policy is that they calculate interest monthly: .8% per month. ${M_n}$ will represent how much money you owe the bank after $n$ months.

Suppose you start by borrowing $\$1500$ — so $M_0 = 1500$. How much do you owe after 1, 2, and 3 months?

Write a recursive equation for ${M_n}$.

If you choose to pay off the loan a little bit at a time, by paying $100 every month, calculate how much you’ll owe after 1, 2, and 3 months — assume that the \$100 is paid before interest is calculated for the month.

Write a recursive equation for ${M_n}$, under the assumptions of part c.

Now suppose the bank, hoping to make more money, decides to calculate interest every month before accepting your \$100 payment for the month. How much more will you owe at the end of 1, 2, and 3 months?

Write a recursive equation for ${M_n}$, under the assumptions of part e.

A sequence follows this recursive rule: ${F_n} = 2{F_{n - 1}}^2$.

Try starting with a few different values for ${F_1}$, and see what happens over the next 10 or so values of $n$. For which starting values do the values of the sequence increase, and for which do they decrease?

Without trying the numbers, say what will happen for the following starting values, based on what you noticed in part a — will the sequence’s values increase, decrease, or stay the same? The starting values are: 1, 1/10, ½, .99.

State and justify the “rule” you were using to make decisions in part b.

The recursive rule for a sequence $\{ {T_n}\} $ is that each term equals 30 more than the (positive) square root of the previous term.

If $T_1 = T_2$, find the number they must equal — call it $C$.

If ${T_1} > C$, what will happen to the value of ${T_n}$ as $n$ increases? How sure are you?

What if ${T_1} < C$? Are you sure?

Investigate what happens with the rule ${T_n} = \frac{{{{({T_{n - 1}})}^2}}}{n}$ when you use different starting values. You should find at least 3 different types of behavior.

For each of the sequences below an explicit equation is given. Start at $n = 1$ and figure out what happens to each sequence eventually — as $n$ gets larger and larger.

${A_n} = 1 + \frac{1}{n}$

${B_n} = {(1 + \frac{1}{n})^2}$

${C_n} = {(1 + \frac{1}{n})^3}$

${D_n} = {(1 + \frac{1}{n})^{10000}}$

Based on your answers to problem 35, what would you expect to happen to the following sequence eventually? After your guess, go ahead and check carefully on your calculator.

${E_n} = {(1 + \frac{1}{n})^n}$

You might have been a bit surprised by the answer you got for problem 36. This number happens to be quite an important number in mathematics — so important in fact that it has a special name and your calculator has a special button dedicated to it. The number is e. Check it out on your calculator.

Two animal populations are interdependent, because the predators (P) feed on the prey (Y). Here are recursive equations for the sizes of each population, in terms of time $t$ (in years):

${Y_t} = (1.03 - .001{P_{t - 1}}){Y_{t - 1}}$${P_t} = (.99 + .00002{Y_{t - 1}}){P_{t - 1}}$

If the starting population of predators is 0 and the starting population of prey is 100 (at time $t = 0$), what will happen to the prey population over time? Why does this make sense in context of the situation?

If on the other hand $Y_0 = 0$ but $P_0 = 50$, what will happen to the predator population over time? Why does this make sense?

If the starting populations are $Y_0 = 450$ and $P_0 = 45$, track what happens in the first ten years.

What should the starting populations be, for both populations to remain stable? Use what you saw in part c, or look at the equations themselves to figure it out.

You invest in a stock through a broker. ${M_t}$ is how much money you have after $t$ years. Every year, the value of your stock increases by 9%, but your stockbroker also charges a fee at the end of each year — $\$100$ the 1st year, $\$200$ the 2nd year, $\$300$ the third year, and so on.

If you invest $\$3000$ initially, how much money do you have each year over the next five years? What’s the trend?

Write a recursive equation for $\{ {M_t}\} $.

How much money would you have to start with, so that after 1 year you have exactly the same amount of money?

If you invested more at the beginning, would your money always grow, or would it still eventually decrease?

Don’t use a calculator for this problem.

Solve for $x$: ${x^2} - 6x = - 2$

Simplify $\frac{\sqrt{6} \sqrt{15}}{\sqrt{10}}$

Simplify ${\left( {\frac{{2{x^2}{y^{ - 3}}}}{{3{x^{ - 1}}{y^4}}}} \right)^{ - 2}}$

Add $\frac{x}{5} + \frac{4}{x}$

Simplify $\frac{{\sqrt {48} }}{8}$

In each of the following datasets, it appears that $y$ increases at a faster and faster rate as $x$ increases. Which of them are exponential?

When a rock is dropped from the top of a large cliff, it falls to the Earth in a very predictable way. Assuming air resistance is negligible (for the first few seconds at least, not a ridiculous assumption), here is a chart of time vs. distance fallen in the previous second. For example, at $t = 3$ seconds, the rock fell 80 feet in the previous second.

Can you write an equation that relates total distance fallen (i.e. distance fallen from the top of the cliff) to time elapsed?

Suppose that you had the following data on the number of downloads $D$ of Lady Gaga’s latest single, as a function of time $t$ in days since it came out.

Fit an exponential function to the data provided, and use your equation to predict the number of downloads on the 100th day after release.

Now, fit a power function to the data, and use that equation to predict $D(100 \ {\rm{ days}})$.

How much confidence do you have in each of these models? Explain.

Graph $y = {\left( {{\raise0.5ex\hbox{$\scriptstyle 3$} \kern-0.1em/\kern-0.15em \lower0.25ex\hbox{$\scriptstyle 5$}}} \right)^x}$ in the standard window on your calculator. It appears that this graph eventually touches the $x$-axis. Estimate at what value of $x$ this happens.

In the previous problem, you probably saw that as $x$ gets larger and larger, the graph of $y = (\frac{3}{5})^x$ and the $x$-axis become nearly indistinguishable. When this happens, we say that the graph of $y = (\frac{3}{5})^x$ and the $x$-axis are asymptotic to each other. We can also say that the $x$-axis is an asymptote of the graph of $y = (\frac{3}{5})^x$ .

Is the graph of every equation of the form $y = {b^x}$ asymptotic to the $x$-axis? Explain.

The $x$-axis is a horizontal asymptote of $y = (\frac{3}{5})^x$ . What vertical line is the graph of $y = (\frac{3}{5})^x$ asymptotic to?

It’s hard to experience it without going into space, but it turns out that your weight actually depends on how far you are from the center of the earth. Here are some data showing how an individual’s weight would vary:

These data can actually be modeled by a power function. Using that fact, and the definition of a power function, find an equation for the data.

According to your equation, how would your weight change if you doubled your present distance away from the center of the earth? (Note: the radius of Earth is about 3969 miles… but does that even matter?)

How far up would you have to go in order for your weight to be 1% of what it is on the Earth’s surface?

Graph the equation you found in part a. Does it have any asymptotes? If so, what do they mean in terms of the situation being modeled?

The equation you found in the previous problem is an example of an inverse power function — that is, a function of the form $y = a{x^n}$, where $n$ is negative. Experiment with a few different values of $a$ and $n$ to get a sense for what inverse power functions can look like. Is it true that every inverse power function is asymptotic to both axes? Why?

The following data show the number of hours of sunlight in northern Maine based on the number of days since the winter solstice, which in 2009 was on December 21. (So, for example, the first row shows the number of hours of sunlight on December 21, the shortest day of the year.)

(data from http://astro.unl.edu/classaction/animations/coordsmotion/daylighthoursexplorer.html)

One night, at their vacation home in Maine, Brad Pitt and Angelina Jolie had a fight. Brad couldn’t sleep that night, and so he was up when the sun rose at 7:04am. By the time it set at 4:22pm, they still hadn’t made up. Using the data in the table, is it possible to say which day of the year Brangelina had their fight?

How many vertical asymptotes does the graph of $y = 2{x^5}$ have?

Does $y = \log x$ have any vertical or horizontal asymptotes? Explain.

Google and others roughly measure the popularity of a given website based on the number of other pages on the Internet that link to the site. The following dataset shows how many blogs there are at different levels of popularity. As you might expect, there are significantly more unpopular blogs than there are popular ones.

Find a power function that fits these data.

Based on your equation, how does the number of blogs with 1000 people linking to them compare
with the number of blogs 500 people linking them?

Is the asymptotic nature of inverse power functions relevant to the situation being modeled? Explain.

According to this equation, how many links would the single most popular blog have?

Come up with a function whose graph is
asymptotic to the line $y = 3$. Can you make one that is also asymptotic to the line $x = 5$ ?

In the chart below, there are four functions ($f$, $g$, $h$, and $j$) that are either “regular” power functions ($y=k{x^n}$, $n$ positive) or inverse power functions ($y=k{x^n}$, $n$ negative). For each function in the chart, determine which of these types of functions it is, and then find $k$ and $n$.

If you graphed the data and equations in the previous problem, you can clearly see four distinct shapes that a power function can have, depending on whether the power is even, odd, negative, or positive. The data below have yet another shape — and this data, too, can be modeled by a power function. Find an equation for the data. Does the graph of your equation have a horizontal asymptote?

The following data from the 2006 census shows the distribution of wealth in the United States. The second row, for example, says that there are 8,138,000 households having an income of $60-70 thousand dollars per year.

(Data from: http://pubdb3.census.gov/macro/032006/hhinc/new06_000.htm.)

Based on what you know about the shapes of different functions, what types of functions could model these data? Does one type seem more promising?

Find an equation that accurately models the data above.

Using your equation, predict how many U.S. households have an income of $80,000.

Check out this visualization of the data above: http://www.visualizingeconomics.com/2006/11/05/2005-us-income-distribution/

The data set below comes from a study of how often different words appear in a large sample of English text. The first column represents a certain level of rarity or commonness for a word, and the second column shows how many words had appeared with that frequency. So, for example, there were 586 words that appeared around 200 times, whereas there were only 73 words that appeared 600 times.

(Data from: http://www.americannationalcorpus.org/frequency.html)

Is there evidence directly in the data above to suggest whether this situation would be modeled better with an exponential or a power function?

Find an equation that models the data above.

Use your equation to predict how many words would appear approximately 2010 times in the sample text.

You probably know that as you gain altitude, the temperature decreases. Here’s some data that provides detail on this phenomenon for a particular location.

(Data from: http://www.usatoday.com/weather/wstdatmo.htm)

If you wanted to fit an equation to these data, what type of function do you think you should try first?

Find an equation for the data, and use it to predict the temperature at an altitude of 7 kilometers above sea level.

At 10:00 am Tim left his hot cup of tea on the table in his classroom. The air conditioning in the room was on, so the temperature of the tea dropped fairly quickly, as indicated in the table below. The time is in minutes after 10:00 am and the temperature is in °F.

Plot these data on a coordinate axis system. To what temperature does the tea’s temperature appear to be converging?

According to Newton’s Law of Cooling, the temperature should be an exponential function of time. Try to fit an exponential equation to the data above. What happens? Why?

Find an equation that accurately models the given data. Based on your equation, predict the time at which Tim’s tea will be within 1 degree of room temperature.

Sketch a graph of the equation you came up with in the previous problem. Now, estimate the slope of this curve at four different points.

What are the units of your slope values? What do these numbers mean about Tim’s cup of tea?

Newton’s Law of Cooling is actually stated thus: the rate of heat loss of an object is directly proportional to the difference between the object’s temperature and room temperature. Do some calculations to verify this, using your answers to part a.

Suppose that the following data shows the height of a soccer ball as a function of time. As you probably learned in physics, these data should be parabolic, and therefore can be modeled using a quadratic equation.

Find an equation that accurately models the data.

Mick Jagger, who was watching the game, took a picture on his cell phone when the ball was 22 meters above the field. How many seconds after the ball was kicked did Mick take the photo?

Is it possible to write a single equation that gives you $t$ as a function of $h$?

For each of the relationships in problem 26 that you decided was a function, determine whether or not it has an inverse function.

The 1000 employees of the Acme Utensil Factory have been playing an absurdly long game of Blammo. They collected the following data on the number of surviving players on few different days.

Based on what you know about the shapes of different functions, what types of functions $could$ model these data?

Find an equation that models the data above.

RJ hypothesizes that the death rate in Blammo games is directly proportional to the population. Use your equation to estimate the Blammo death rate on days 1, 3, 10, and 12, and then test RJ’s hypothesis.

Don’t use a calculator for this problem.

Find $x$ if ${\log _2}x = 6$.

Solve for $x$: $(x - 1){(x - 3)^2}(x + 4) = 0$

Subtract: $\dfrac{3}{a} - \dfrac{{7 - b}}{{ab}}$

Simplify: $\dfrac{{\frac{x}{y} + 1}}{{2 - \frac{x}{y}}}$

$\sqrt[{3{\kern 1pt} {\kern 1pt} }]{{162}}$ can be written in the form $a\sqrt[{3{\kern 1pt} {\kern 1pt} }]{b}$ , where $a$ and $b$ are integers and $b$ is as small as possible. What are $a$ and $b$?

In the beginning of this lesson, you saw that the inverse of an exponential function is a logarithmic function. Now, prove that the inverse of a power function is always a power function.

Prove that every equation of the form $y=a{\log _b}x+c$ can be written in the form $y = {\log _B}x + c$ .

Look back at the equation you wrote for $h$ as a function of $t$ in problem 38. Using that equation…

Write an equation that tells you $t$ as a function of the height $h$ of the ball on its way up to its highest point.

Write an equation that tells you $t$ as a function of the height of the ball on the way down.

Why isn’t there only a single answer to the question “What angle has a sine of .4221”?

Your answer to the previous problem implies that the sine function does not have an inverse function. If that is the case, what the heck is your calculator doing when you do ${\sin ^{ - 1}}$ ?

Is it possible to have an inverse function for just part of the sine function? What part?