Close

# Functions and Algorithms Homework

## Session 3, Homework

### Problem H1

Invent a number game like the one from Problem D1. Draw a network that lets you figure out the output for any number. Draw another network that lets you find someone’s original number if you know his or her final result. Try out your game on someone else.

Here’s a number game:

• Pick a number
• Subtract 4
• Finally, multiply by 3

### Problem H2

Tell whether each example below is a function, and explain how you decided.

1. Input: a circle. Output: the ratio of the circumference to the diameter.
2. Input: a soccer team. Output: a member of the team.
3. Input: a CD. Output: a song on the CD

Tip: Remember, a function is any relationship in which each input leads to exactly one output, and the same output may be repeated more than once for different inputs. A rule is not a function when the same input can lead to multiple outputs.

### Problem H3

Gabriela and Ben are trying to decide whether the rule y = x4 is a function. Represented as an algorithm, the equation y = x4 is equivalent to starting with a number, then multiplying that number by itself four times. For example:

Input: x = 2
Output: y = 2 x 2 x 2 x 2 = 16. Who is correct, Ben or Gabriela? Is y = x4 a function? Explain how you know.

Tip: Pick a number. Add one. Add one again. Again. Again. By doing this, you’re iterating the “add one” function. The “his father before him” function is frequently iterated in conversation.

Problems H4-H7 involve iteration, a process that can be done to any function where the output is the same type as the input. When you iterate a function, you apply it again and again, each time using the previous output as the new input. Iteration is a very important technique for solving equations approximately when typical algebraic methods can’t be used, and it is also used to model many real-world problems like population growth and the change of weather.

Here’s an example:

Input: a real number
Output: half that number

Start with an input of 20. The first output is 10. Now, use that output as the new input. The second output is 5. Use 5 as the next input, and you get an output of 2.5. And so on.

### Problem H4

Use the function described above, starting with an input of -16. What are the first five outputs as you iterate the function? What will happen to the value if the iteration continues forever?

Tip: The first output is -8, then use -8 as the next input.

### Problem H5

Build a network of function machines that adds 1 to an input and then divides by 3. Now iterate the function. Try three different original inputs, and iterate the function at least 10 times for each input. What is going on?

Tip: What happens to the values “in the end,” after many iterations? For what numbers does this happen? Can you explain why?

A “fixed point” of an iteration is a value of the input that produces itself as an output. For example, if your algorithm subtracts 3 from an input, then multiplies by 2, the input value 6 has output 6, so it is a fixed point.

### Problem H6

Find any fixed points for these algorithms. There may not be any, or there may be more than one.

1. Add 1, and divide by 3
2. Subtract 6, and multiply by 3
4. Square the input.
5. Add 12, and divide by 4
6. Square the input, then subtract 6

Tip: If a fixed point’s input is n, what would its output have to be?

You can also iterate functions that act on geometric shapes. Here’s a new function:

Start with a right-side-up triangle; that is, a triangle with one base horizontal. Find the midpoints of each side of the triangle, and connect them to each other. Repeat this process on each right-side-up triangle in the output.

Here’s the start of the iteration for this function: ### Problem H7

Draw your own triangle. Iterate the function above at least three times. Describe how the outputs relate to each other.

### Solutions

Problem H2

1. Yes, the output is always Π, but there is exactly one output for any input.
2. No, the same team can have lots of different members.
3. No, the same CD can have many different songs.

Problem H3

Gabriela is correct. The number of matching outputs is not important (witness the “3” function!), only that there is exactly one output each time.

Problem H4

The outputs are -8, -4, -2, -1, and -1/2. The iterates get closer and closer to zero.

Problem H5

No matter what you start with, the inputs will get closer and closer to 1/2.

Problem H6

In each case, the output value must equal the input, so writing the rule and making it equal n is one way to solve the problem.

Problem H7

Each output is three half-sized copies of the input, with a hole in the middle. The pattern can repeat itself indefinitely.