Wednesday, March 21, 2007

Searching continued...Another Challenging Combinatorial Problem

The 'answers' to the problems below are now posted in the comments...

[Update: I modified today's problems for my 9th grade group. An excerpt from the handout is shown at the bottom. How do you think they did? These are youngsters who need very precise instructions and find math more challenging. Guess how they did?]

How many 4-digit numbers have exactly 2 identical digits?

Today's questions were inspired by a Google search from one of the viewers of this blog. No matter how many of these types our students may attempt, there is no substitute for a systematic approach and clear thinking. Professional mathematicians who have done numerous problems of this type and are therefore likely to know an efficient method still can make careless logic errors. Imagine how our students do! They're looking for a quick and dirty approach, one short-cut method or formula that covers all kinds. Not likely!!

There's an interesting semantics problem with this question: Does 3232 count as a possible answer? Your first instinct might be to say, "Of course, it doesn't count!" But how many identical digits does it really have? For this reason, I will reword today's question to:

How many 4-digit positive integers have exactly one pair of identical digits?

[Note: Someone will probably argue about the semantics here as well but I'll let it stand!]
I'll post the result I obtained later but, for now, how many different approaches do you think your students could come up with? I thought of at least 3 not to mention writing a short program to count them!]

I see this kind of problem as appropriate for middle school and high school. For the middle grades, students should begin with the 3-digit version (see worksheet below) and be encouraged to make an organized list. By high school, they should be able to move on to more powerful counting methods but we know some are stuck at the 4th grade level of counting in an unorganized manner. In fact, from my observations, most high schoolers start in the 1000's, count those and multiply by 9. This is actually a fine method but should they know other approaches by the time they complete Algebra 2?

The following is a portion of the worksheet I gave to my group today. It worked out well. Any thoughts? Notice that I modified the 4-digit problem to make it more accessible for them. It provided an easier extension.


Totally_clueless said...

A related question: How many 4-digit numbers have increasing digits?


Dave Marain said...

Nice, tc!
How about 9C4 for your question? For 'increasing' numbers, we can eliminate zero digits. For each combination of digits like 5,2,3,7 there is only one possible 'increasing' number that can be formed, in this case, 2357. Let me know if that makes sense or I made a logic error...
I trust your judgment - what do you think happened with the handout I displayed. I had to walk each of them through every step or some could go off and do it?

Eric Jablow said...

Have you considered giving them labs on:
a) Benford's Law?
b) Probability distributions in sports?
bi) Do the number of MLB no-hitter thrown in a year follow a Poisson distribution?
bii) Do players or teams really go on "hot streaks" above the statistically-expected? Does it depend on the sport?

Dave Marain said...

thanks for the ideas which i'll share with our stats teachers; i really like the concept of the statistical significance of a hot streak

Answers to Problems:
Original 4-digit problem (exactly one pair of identical digits): 3888

1st Problem on Worksheet (3-digit, exactly 2 digits the same): 243

2nd problem on Worksheet (4-digit, 3 digits the same): 324

Comments: Two young ladies, K.C. and K.C. both got the first one and nearly completed the 2nd; in explaining her method to the first one, one wrote: "There were 27 numbers in the 100's, 27 in the 200's, so I multiplied 27x9, since there are 9 equal groups."

Other comments: I chose to highly structure each problem since many in our group struggle with directions and often give up early if the problem doesn't make sense right away. The examples certainly made the directions clearer but students who lack confidence in problem-solving tend to shut down part of their brain when they see questions like this. They need a way to get started and as they begin to be successful, they relax and build momentum until they get stuck somewhere else. I move continually from student to student monitoring and guiding. They worked the entire period and seemed to enjoy this. They're getting more used to these daily open-ended problems. I'm currently building the curriculum around these.

Comments about the problems:
Although there are several combinatorial approaches, working in groups of hundreds or thousands seemed to make the most sense to the students. Although I did not develop the Multiplication Principle for them yet, they were grasping it as you can see from K.C.'s explanation (9 equal groups of 27). With a more advanced group, I'd explore combinations further. By the way, by starting in the range 1000-1999 for the 4-digit problems, you avoid the typical sticky issues of the leading zero.

Here's the beginning of a more complicated approach using combinatorics. The method described above seems far superior:
1. 9C1 = 9 ways to choose non-zero repeating digit
2. 4C2 = 6 ways to place the repeating digit in 2 of the 4 'places'
3. If the repeating non-zero digit is in positions 1 and something else there are 9x8 = 72 ways to choose remaining digits, etc.

I'm sure someone will find another more straightforward approach!

Dave Marain said...

I should also add that one of the young ladies who solved it, commented: "These weren't really that hard -- you just have to think..."

Totally_clueless said...

Combinatorial method:
For n digit numbers, only 1 digit is repeated k times, no other digit is repeated.

Choose the repeating digit : 10 ways.
Choose the non-repeating digits: C(9,n-k) ways.
Number of non-unique permutations of these = n!/k!

By symmetry 9/10 of these possibilities do not begin with a zero.

Thus, the answer is C(9,n-k)*(n!/k!)*9

It becomes much more complicated if we allow repetitions in the other digits too, and I'll try that if I get more time.

Also, Dave, I see you had taken quite a bit of trouble in making the exercise as clear and unambiguous as possible, so am surprised that some students required the level of help that you mentioned. In your observation, is this because math scares them to begin with, or due to a general lack of interest, or something else totally?


Totally_clueless said...

Also, a more complicated related problem: How may 4 digit numbers have non-decreasing digits?

jonathan said...

I think it is worth teaching kids to make organized lists, even long lists, before pointing them towards any combinatorial shortcuts. I find that very few are much good at listing things, but many pick it up relatively quickly.

Sometimes, as they make lists, they develop some combinatorial insight. I've seen that happen in the decreasing digits problem.