Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Accessible problems
Posted:
Apr 26, 1995 9:13 PM
|
|
The Collatz problem comes to mind.
take any integer n
if it is odd, replace it with (3n+1)/2
if it is even, replace it with n/2.
iterate this procedure.
The conjecture is that for all integers, the sequence
eventually reaches one.
There are a lot of partial results, and the truth of the conjecture
has been established for a LARGE number of integers, but the general
result is not known. (There was a good survey article on this in
the American Math Monthly vol 92 (1985), no 1 pages 3-23 -- author
Lagarias) It's a well-known problem, so there are probably lots
of other references around for it -- and the AMM article includes
an extensive bibliography. Collatz died in 1990, I think.
(Also known as the Syracus/Kakutani/Hasse/or Ulam problem)
--------------------------------------------------------------
A problem I have some personal interest in is related to the
Van der Waerden/Szemerdi results on arithmetic progressions
within subsets of the integers. A (very) condensed introduction:
Van der Waerden proved (in 1927, or thereabouts) that for any
(positive) integer k, there is an integer N so large that if you take
the integers 1,2,3,...., N and divide them into two sets A and B, at
least one of those sets must contain an arithmetic progression of
length k. (actually, he proved something a bit more general than
this, but this captures the idea -- also once you have an N that works
for some k, any number larger than N also works).
Szemeredi proved (in 1975) a particular extension of this, that for
any integer k and any postive percentage r (0 < r < 1), there is an
integer N so large that any subset of N that contains at least r*N
integers will contain an arithmetic sequence of length k. (again, he
proved something a bit more general than this, but this is an
immediate consequence)
Some extensions of these ideas that are as yet unproven:
Given an (infinite) set of integers the sum of whose reciprocals
diverges, must there be arbitrarily long (albeit finite) arithmetic
sequences in the set? Must there even be an arithmetic sequence of
length 3 in the set?
In particular, are there arbitrarily long arithmetic sequences of
primes? It's easy to find arithmetic sequences of length 5 or so:
5,11,17,23,29. With some work, (and using a common difference of 210,
instead of 6), you can find arithmetic sequences of primes of length
6.The largest known arithmetic sequences of primes are of length
around 20 (the primes involved are somewhat large).
Another problem in this area relates to the GROWTH rate of the
Ven der Waerden function, that is, for each k, let V(k) be the SMALLEST
N that works. How fast does V(k) grow?
There's a pretty direct proof that V(k) > sqrt(k-1)*2^((k-1)/2)
On the other hand, until 1986 or 1987 (and Shelah's proof,
actually introducing a new combinatorial idea), the best
known upper bounds for V(k) were unimaginably ENORMOUS!
Even with Shelah's proof, the bounds are really quite large...
greater than the function
f(k) = 2^2^2^2^2^2^2^...^2 (a tower of exponents k times)
(actually his upper bound is on the order of
f(f(f(f(....f(k)....)))) (i.e., iterate the function f(k) k times).)
Can one do better? There's still a lot of room between the known
upper and lower bounds.
Even for small values of k, the precise value of V(k) is not known.
(though as an exercise, one may verify V(2) = 3, V(3)=9.) There
are some reasonable bounds for small values of V(k). (Sorry, I don't have
more details close at hand -- but I think the latest edition of "Ramsey
Theory" -- Graham et al -- has a good summary.)
The statements of the problems are within the reach of sharp high
school students as are SOME of the proofs. Also, there are other
essentially equivalent formulations of the problem (like the
Hales-Jewett approach, looking at a multidimensional hyper-cube of
side length k... if you think of it as a sort of a multi-dimensional
tic-tac-toe-board, Hales-Jewett theorem gives that, for every k, if
the number of dimensions is sufficiently large than there can be no
cat's-games -- every assignment of Xs and Os to the hypercubes of
length 1 inside the big cube will include a "line" of k in a row with
the same mark).
Ted Alper
alper@epgy.stanford.edu
|
|
|
|
