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 323  author Lagarias) It's a wellknown 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(k1)*2^((k1)/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 HalesJewett approach, looking at a multidimensional hypercube of side length k... if you think of it as a sort of a multidimensional tictactoeboard, HalesJewett theorem gives that, for every k, if the number of dimensions is sufficiently large than there can be no cat'sgames  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



