Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: where's the math?
Posted:
Apr 22, 1995 2:57 AM
|
|
Susan,
Of course, just because I don't see the connection, doesn't mean
there isn't one. I should have phrased my post more temperately.
(On the other hand, the existence of a construction on Pascal's
triangle that has something in common with a construction on the real
line that leads to the Cantor set, doesn't mean that Pascal's triangle
is "connected" to the Cantor set, only that both admit a certain type
of construction.)
"Dr. Susan Addington" <addington@gallium.csusb.edu> writes:
>Here's a homework problem for you:
>
>Write out a large section of Pascal's triangle.
>Pick a prime (say, 7).
>Highlight all the entries of Pascal's triangle that are
>divisible by 7.
>Find a pattern.
>Explain why it happens.
>What would you get if you used a really big section of P's triangle,
>say, 100 rows or more?
>What would happen if you used *all* of Pascal's triangle?
I hope it's ok to do my homework on the net. (And I'd as soon skip to
the general pattern. I make no claims for efficiency of my proof -- I
just put the baby to bed and I sort of want to join him -- but I'll
edit out any major false starts):
Actually, rather than do it in complete generality, let me leave
7 in. We can go back later and replace it by an arbitrary prime.
using nCm for n!/(m!(n-m)!) and
[x] for greatest integer less than or equal to x.
the number of powers of 7 dividing n! is
[n/7] + [n/7^2] + [n/7^3] + ....
similarly, the number of powers of 7 dividing m! is
[m/7] + [m/7^2] + [m/7^3] + ...
and, for (n-m), it's
[(n-m)/7] + [(n-m)/7^2] + [(n-m)/7^3] + ...
Now, since [a] + [b] is always less than or equal to [a+b],
[n/7^k] is greater than or equal to [m/7^k] + [(n-m)/7^k]
for all k. If equality holds for all k, then nCm will not be
divisible by 7. So the question becomes: For what (n,m) is there
a k for which
[n/7^k] > [m/7^k] + [(n-m)/7^k] ?
OH! I think I see where this is going. The digits of
an integer n in base 7 are also given by these terms.
I guess the units digit is n - 7*[n/7], the "7"s digit is
given by [n/7] - 7*[n/7^2] and so forth. If for k=1,...,j
we have [n/7^k] = [m/7^k] + [(n-m)/7^k], then
[n/7^(k-1)] - 7*[n/7^k]
will equal
[m/7^(k-1)] - 7*[m/7^k] + [(n-m)/7^(k-1)] - 7*[(n-m)/7^k]
for k=1...j. That is, the base 7
representation of n,m, and n-m will be such that the sum
n = m + (n-m) adds without any "carries" for the smallest
j digits. (I guess another way to say it is that the smallest j
digits of m will be less than or equal to the smallest j digits of n.)
However, for the first value of k (if there is one) for which
[n/7^k] > [m/7^k] + [(n-m)/7^k]
this will fail!
[n/7^(k-1)] - 7*[n/7^k]
will be less than
[m/7^(k-1)] - 7*[m/7^k] + [(n-m)/7^(k-1)] - 7*[(n-m)/7^k],
so there will have had to be a "carry".
So, my solution is that nCm is divisible by 7 precisely when the base
7 representation of m has at least one digit larger than the
corresponding digit in the base 7 representation of n. Equivalently,
nCm will NOT be divisible by 7 if every digit of the base 7 rep. of n
is at least as big as the corresponding digit in the base 7 rep. of m.
OK. I see why I have to use a prime for 7 (the very first step,
counting powers of 7 that divide n! relies on it).
It's probably easier to generate the pairs (n,m) for which nCm
is NOT divisible by 7... That is, write the base 7 expansion of n,
then look at all the numbers which can be written using only the same
or smaller digit in each corresponding location.
I suppose one can also start by fixing an m and then see which numbers
can be written using only the same or LARGER digit in each
corresponding location (including extra digits in places larger than
those that occur in m). Obviously, if a given nCm is not divisible by 7,
then replacing n with n + any multiple of any power of 7 larger than m
will still yield a term not divisible by 7.
For values of n of the form 7^k - 1, nCm will not be divisible by 7 for
any m. For values of n of the form 7^k, nCm will be divisible by 7
for all m except m=0 and m=n. For most others, the values for which
nCm is divisible by 7 will occur in big clumps, since if one
digit in m is bigger than the corresponding digit, all the other digits
can be anything at all (this is a bit imprecise, as how much of a "clump"
it is will depend on which place the larger digit is in -- if it's the unit
digit, there's no clumping at all -- that is, for n = 7^k + 5,
nCm will be divisible by 7 only when m is congruent to 6 mod 7. But for
n=7^100 + 5*7^3, say any m with a 6 in the 7^3 place will work, no matter
what the other digits are -- so in this case, you can have up to
7^3 consecutive values of m for which nCm is divisible by 7).
The values for which nCm is NOT divisible by 7 will occur in smaller
clumps, since they must satisfy a condition on every digit (though
again this is imprecise: if n=k*7^6 + 7^5 - 1, than values of m for
which nCm is not divisible by 7 will occur in clumps of size 7^5).
I apologize for the imprecision of these last two paragraphs --
but as a first statement of the clumpiness, I hope it's reasonably clear.
Obviously, there's at least some analogy between these numbers and the
Cantor set construction, as we're avoiding specific digits in specific
places (One characterization of the Cantor set is all numbers between
0 and 1 whose trinary expansion contains no "1"s.). These numbers
(n,m) are only integers, with finitely many places in their base 7
expansion -- but perhaps the comparison is to the finite steps in the
Cantor-set construction. Then, too, they aren't quite as disconnected
(this is the clumpiness issue alluded to above) -- though if one tried
to push this off into the 7-adics, say (in what sense? look at pairs
of 7-adic integers (n,m) for which every digit of m was less than or
equal to the corresponding digit of m?), it looks a lot more similar.
In particular, for most (7-adic) values of n, the set of m that work
will be closed and totally disconnected and the set of points (n,m) in
the (7-adic) plane that work will be closed and totally disconnected.
This is a little different than what you see on Pascal's triangle,
though, since points are close in the p-adics precieely when their
difference is divisible by ENORMOUS powers of 7.
Ted Alper
alper@epgy.stanford.edu
|
|
|
|
