# «Chris Hammer Seth Risinger Keri Sebesta Andrea Zentz Objectives Students will be able to define and develop ideas in discrete mathematics 1.) ...»

Sparse Ruler Module

Lesson Plans in Discrete Mathematics

Chris Hammer

Seth Risinger

Keri Sebesta

Andrea Zentz

Objectives

Students will be able to define and develop ideas in discrete mathematics

1.) Students will begin to work with rulers and begin to understand how to obtain

lengths by sliding/extending it along a number line or ruler.

2.) Specifically students will be able to find, develop, and construct a table of

minimally notched rulers.

3.) The class will formulate strategies to construct minimally notched rulers.

4.) Students will be able to analyze their work in order to conjecture with justification, in regards to patterns and ideas found in their work.

Day 1 (50 minutes) Objective: Students will begin to work with rulers and begin to understand how to obtain lengths by sliding/extending it along a number line or ruler.

Introduction Problem (15 minutes) By the end of this class, students will be able to develop minimally notched rulers.

To start this series of lessons, students will be in groups of 4-5 working on the Die Hard introduction problem. Students should work on the problem for about five minutes, and each group should develop as many solutions and strategies as they can. Then bring the class together to compare strategies and discuss major ideas. If the class is reluctant to share, here are some guiding questions.

-In the beginning, what information were you given? What are you trying to find?

-Is there a direct way to get four gallons from the two buckets?

-Out of the solutions discussed, which method contained the fewest steps?

In the end, be sure to use the discussion and questions to bring it all together. We want students to begin thinking about obtaining the maximal number of differences through a minimal amount of numbers/notches. This activity is included so that students begin to think creatively about solving problems related to measurement.

Rod Activity (35 minutes) This activity will help students begin to construct minimally notched rulers by allowing them to visualize the possible placement of various differences on the ruler. To begin the activity, each group will be divided into 2 smaller groups. Each group will work with a set of rods. Each group will have rods of length 1 through length 6. Now that each pair of students has the necessary supplies, we can begin the activity. As students work with the rods, they will develop a set of minimally notched rulers for lengths 1-6.

To begin the activity, the teacher will lead the students through the first two rulers. First, explain that every length 1 through n, must be a difference on a ruler of length n. This means that for a ruler of length one, it is comprised only of length 1.

Every ruler is a number line with endpoints. (ruler of length 1 will have endpoints 0 and 1). Now place rods of various lengths on the ruler, in order to incorporate all lengths 1 through n. These blocks will designate your lengths or notches on the ruler. This means there will be only one block of length 1 for n=1. Work through a ruler of length 2 as well.

Now place your lengths on the ruler. First, place length 1 on the ruler and then place the rod of 2 above length 1. This allows students to see how the blocks overlap.

Also, be sure to mention that there can be repeat lengths. Add an extra rod of length 1 to the ruler of length 2 to show this concept. (There is a length of 1 between 0 to 1 AND 1 to 2).

After you have worked the ruler of length 2, encourage the students to find rulers for lengths 3, 4, 5, and 6. The students should measure differences with the rods, so they can visualize the various differences across the number line/ruler. As you traverse the classroom, monitor their progress. The following questions can be used amongst individual groups or as part of a larger, whole class discussion.

**Here is an example of the ruler of length 6:**

Notice how the placement of the blocks allows you to measure all lengths 1 through 6 with the notches 0,1,4,6. Be sure to show students how these measurements COULD slide up/down the ruler, if you wanted to have different notches on the ruler.

-How many notches do you have for your rulers?

-Are there repeat distances that could be eliminated?

-Notice how your lengths line up on the ruler, do any of them overlap?

Day 2 (50 minutes) Objective: Students will become comfortable constructing minimally notched rulers and will explore the characteristics that define them.

Today guide the student’s through the activity packet. This lesson is broken into four parts, with three of them being done in class.

Part I Although the students explored the ruler of length six the previous day, they may have not come up with a solution that is minimally notched. If need, adjust the opening problem to a ruler of length seven. This application problem will motivate and provide a different representation of the problem for the students. Allow about 7 minutes of work time and then discuss the results.

Construct a ruler that totals up to six units of length. The ruler must be able to measure all the unit lengths between 0 and 6.

The solutions will vary with some having more notches than others.

Now, pretend that each notch that is built in the ruler will cost $1,000,000. Construct the most cost efficient ruler.

**Ex. Solution:**

**Discussion Notes:**

Discuss which group had the most cost effective ruler. This will lead to showing which ruler is minimally notched. Make sure students are explaining their answer and why their ruler is valid. The class should evaluate the validity of each group’s ruler.

Part II The students will be exploring how many notches can be included in a ruler of length six and seven (change if necessary). The maximum number should be the number of notches needed that includes every notch possible for a ruler of length n. This maximum number is the n +1 because zero is included as a notch. The minimum number is the least amount of notches included in order to measure all lengths between 1 and n.

Draw the ruler of length six that was the most cost effective. In other words which ruler from the class had the minimal number of notches?

Construct a ruler of length 7 with the maximum number of notches included.

This ruler will have all notches from 0 up to 7.

Construct a ruler of length 7 with the minimum number of notches needed.

Answers will vary.

Discuss with your group how to find a maximum and minimum number of notches for a given length. Is there a pattern with the maximum and minimum number of notches needed?

The teacher should allow discussion with the groups and also bring a discussion with the whole class. Do not allow for much time for group discussion and being it together as a class as soon as possible. Ask questions that will lead the discovery of the maximum as n+1.

ex. What would be the easiest way to have every length measured?

Is this method efficient? How would you change the ruler?

Then discuss how to obtain the minimum number of notches needed.

Can you put a notch on a blank ruler that will give you more than one length?

What is an example of this? If we have a notch at one, would it make sense to put a notch at two?

Part III Students will learn that there are multiple minimally notched rulers of the same length. The goal of this part of the lesson is to have students find multiple rulers of the same length. Students will learn that there can be multiple solutions to the same problem, and that there may be more than one way to solve a problem.

Draw a different ruler of length 7 with the minimal number of notches. Make the notches in this new ruler be different from the one you found in Part II.

Answers will vary.

There are twelve possible rulers of length 7 that can be made with the minimal number of notches. Find three more rulers of length seven.

Now, discuss the minimal number of notches needed for a ruler of length 8. Construct three different rulers of length 8 that have the same number of notches as your original.

Part IV This part can be used in class or be assigned for homework. After working with the rulers for two class periods, students will develop their own strategy for finding or solving the rulers. This allows students to communicate their ideas on paper and think critically about the material. The students will also come up with a definition as they think fits.

Write out strategies that you used in finding minimally notched rulers. Why did these work?

Based on your work and class discussion thus far, write a definition of a minimally notched ruler.

Day 3 (50 minutes) Objective: Specifically students will be able to find, develop, and construct a table of minimally notched rulers. Students will also explore extensions of this concept by looking at the concept of a Golomb ruler.

Ruler Tables In the last day of our unit, students will work in groups to further develop their definition of minimally notched rulers. Students will simply work out many rulers up to the length of twenty. Included is an example of the table with some answers. Allow half of the class time to work and discuss this table. Students will be working on the rulers, noting the number of notches, and their varying strategies for solving these rulers. In the end, the class will come together to finalize their definition and discuss strategies. Be sure to focus on the idea that most of these strategies are a form of guess and check.

Students can use their knowledge of these rulers, and finding varying lengths to elevate their strategy to a higher of informed/educated guessing.

Golomb Rulers In this extension of our unit, we will discuss Golomb Rulers. The class will be given a worksheet in order to investigate this topic. The worksheet includes using online resources in order to define a Golomb ruler and find examples and applications of Golomb rulers. A worksheet is included for teacher use with examples of wellconstructed answers to the questions being asked.

Directions: Search online to answer the following questions. Answers should be in complete sentences.

**Here are two very good websites:**

http://en.wikipedia.org/wiki/Golomb_ruler http://www.maa.org/editorial/mathgames/mathgames_11_15_04.html

1) What is a Golomb Ruler?

Definitions may vary.

In mathematics, a Golomb ruler, named for Solomon W. Golomb, is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values.

There is no requirement that a Golomb ruler can measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more ticks. A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists.

2) What is the length of a Golomb Ruler with 4 notches? Draw the ruler.

A Golomb Ruler with 4 notches has a length of 6.

|___|____|___| 3.) Describe the relationship between the sparse ruler of length six and the Golomb ruler with 4 notches. This ruler has a special name. What is it and what makes is special?

They are the same ruler. This ruler is called a perfect ruler because every distance from 1 to 6 is represented exactly once.

4) What is the length of a Golomb Ruler with 16 notches?

A Golomb Ruler with 16 notches has a length of 199.

5) What is the largest Golomb Ruler found to date?

Distributed.net has completed a distributed massively parallel search for optimal orderGolomb rulers, confirming the suspected candidate, and a search for order-25 optimal rulers is currently underway.

6) Find and describe in detail an application of Golomb Rulers.

One practical use of Golomb rulers is in the design of phased array radio antennas such as radio telescopes. Antennae in an [0, 1, 4, 6] Golomb ruler configuration can often be seen at cell sites. Many other applications can be found on the