## Sunday, April 13, 2008

### 1,2,2,3,3,3,4,4,4,4,... What is the 2008th term? SAT-type Questions vs. Math Contest Problems

Don't forget to submit the name of our Mystery Mathematician. Contest ends around 4-15-08. Thus far, only one correct submission (emailed of course!). The problem in the title is the math contest version. Knowing the formula for the nth triangular number would be helpful (so might a calculator). Do all middle school and hs students become familiar with triangular and other figurate numbers? Should they? My vote: Yes!

The SAT -type would be:

What is the 56th term of the sequence 1,2,2,3,3,3,4,4,4,4,..., in which each positive integer N occurs N times?

Comment: This is considerably easier than the contest problem as one could do it by listing with or without a calculator. It also may reveal your strong number sense students who will see the idea fairly rapidly. Try it as a warm-up in class!

Another SAT-type (probability, counting) to help students prepare for the May Exam:

Let S be the set of all 3-digit positive integers whose middle digit is zero. If a number is chosen at random from S, what is the probability that the sum of its digits is even?

Note: I wrote this question to demonstrate basic principles of probability and counting. Although one could use the Multiplication Principle (aka, Fundamental Principle of Counting), students should also be encouraged to make an organized list and, by grouping, see why the answer is 1/2.

Joshua Zucker said...

"Let S be the set of all 3-digit positive integers whose middle digit is zero. If a number is chosen at random from S, what is the probability that the sum of its digits is even?"

Well, for this one, it's obvious.
Consider the mapping from S to itself which adds one to the last digit if it's even, and subtracts one if it's odd.

This mapping is one-to-one and onto and maps all numbers whose digit sum is even onto numbers whose digit sum is odd and vice-versa. So clearly the desired set is exactly half of S.

Of course I said that more formally than I would with students, but the idea is a very simple one -- symmetry and parity -- yet very deep and powerful. It's always good to keep coming back to these fundamental strategies and using them again and again. Above all, it's important to identify and NAME them when you use them, so students can start to see the kinds of situations where they come up!

Anonymous said...

The first problem can be solved with the summation formula:

S(n) = 1+2+...+n = n(n+1)/2

One simply needs to find n such that
S(n) =< 56 < S(n+1) is satisfied:

S(n) =< 56 < S(n+1)
<=>
n(n+1) =< 112 < (n+1)(n+2)

Now approximate 112:

10*11 = 110 =< 112 < 11*12 = 132

Therefore the 56th term of the sequence is n = 10.

I'm not shure if there is an effective
way to solve this without the summation
formula. Is there one?

Dave Marain said...

I like that clever mapping approach, Joshua. This type of method is mot often discussed and it should be. I also like your last statement - Naming is part of a classification system of methods for students. What they also need is additional practice with this type of thinking. Too often, I've seen the occasional challenge problem presented as an isolated question. Students do not make connections without a conscious effort on our part.

I post many counting problems on this blog specifically so that teachers can click on the 'Counting Problems' (3 posts) or 'Combinatorial Math' (12 posts) labels in the sidebar and have an immediate problem bank to choose from for class problems and assessments or as ideas for their own questions.

Anonymous said...

We can create a new problem out of the digit problem:

Suppose Alice and Bob are playing a game requiring a coin flip. Alice has a coin, but Bob is worried that it might be weighted. How can Bob ensure that they can make fair choices even if Alice's coin is weighted.

1. If Bob has a fair coin, they can agree that they flip the two coins together and bet on whether they come up the same or different. In fact, this is your digit problem, with Alice's coin being the 100s digit and Bob's the 1s digit.

2. If all they have is Alice's coin, what can they do to get a guarantee of fairness from it? Let the students think for a while.

Answer: Always flip the coin twice. If they come up HH or TT, ignore the pair of flips and flip it again twice, and so on.

If the flips come up HT, call it heads.

If the flips come up TH, call it tails.

You can go on from there to talk about how many pairs of flips it would take to get a result, and then talk about entropy in probability, but that's a more specialized discussion.

Dave Marain said...

Eric --
What a nice connection - relating the parity of the sum of 2 digits with outcomes of 2 coins! To make sense of your idea I needed to consider extreme cases. Assume Alice's coin lands Heads 100% of the time (not much entropy, i.e., uncertainty, there!). Then the probabilities of the 4 possible outcomes of flipping the two coins would be (Alice listed first):
HH: (1)(.5) = 0.5
HT: (1)(.5) = 0.5
TH: (0)(0.5) = 0
TT: (0)(0.5) = 0
Similarly, if Alice's coin lands Tails 100% of the time.
Your re-definition of H and T compensates for these extremes. I need to become more knowledgeable in this area before displaying further ignorance!

Anonymous said...

Dave,

The digit problem has Alice's coin come up heads 5/9 of the time and tails 4/9 of the time. However, that procedure works for any distribution from Alice, even the one you gave.

Do you know the term 'convolution'? Let X and Y be random variables with discrete probability distributions p and q. Then, X+Y has probability distribution

p*q(t) = ∑p(s) q(t−s), summing over s.

To work with our problem, have our random variables take values in Z₂. Heads correspond to odd numbers and tails to even numbers. Then, a fair coin has the probability distribution

f(0) = f(1) = ½.

It turns out that f*p = f for any probability distribution p; f is the 'zero' for convolutions with this domain.

Anonymous said...

Solution to the sequence problem:

Let Fn be the number such that the first occurance of n is in the Fn'th position.

Using the formula for summation of an arithmetic series:

Fn= (n^2-n)/2 + 1

Let a_n represent the a_n'th position in the sequence.

We are trying to find an n such that Fn<=a_n
or Fn-a_n<=0

using the quadratic formula, we see the formula to solve this problem for any a_n is:

n=floor(0.5+sqrt(0.25-2(1-a_n)))

where floor is the function that rounds down to the nearest integer.

so for a_n=56, n=11
and for a_n=2008, n=63

This was verified using a simple brutce force python script.

Cheers.