These problems have been, unsolved, on our website since January 2001!!!

The Clay institute offers a million dollars. I can only offer a million TL!!

A Challenge to all Mathematicians – Amateur and Professional

Here are three mathematical problems that have come up in the course of this term in a couple of computer courses I have been teaching. 

One of the problems is, I think, easy, one is moderately hard, and one, probably, quite difficult. I am looking for solutions.

I am not the Clay Institute, so there is no million dollar prize, but the best (or only) solutions I receive will be displayed on our website.

Mail your solutions to stephenson@bilgi.edu.tr

Problem 1 (easy?)
Proving an important step in the analysis of the “Shellsort” algorithm. Every book that I have consulted says “this proof is outside the scope of this book” or “this proof is left to the reader”. 

Theorem: If a k-ordered array is h-sorted it remains k-ordered.

An array is k-ordered if for all i for which both i and i+k are within the bounds of the array a
a[i] <= a[i+k]
h-sorting is the process of re-ordering the subarrays consisting of elements exactly h positions apart in the array a.

Knuth gives a lemma that should help to prove the result, but leaves the proof of the theorem as an exercise for the reader. This Lemma is here.

Problem 2 (moderate?)

(a) A plane polygon of finite mass is sliding around (and rotating) on a frictionless plane. It hits a straight, frictionless and infinitely hard barrier. How will it bounce? Since the impulse from the barrier to the polygon will not necessarily be directed through the centre of gravity of the polygon, the impact may change the speed (and possibly direction) of rotation of the polygon. Since energy must be conserved, this must also effect the velocity of the polygon. What is the formula that connects the factors at impact, velocity, rotational speed, angle of impact, with the situation after impact.

(b) What if the barrier, instead of being frictionless has an infinite coefficient of friction? 

Problem 3 (hard?)

(a) The polygon of problem 2 is travelling through gravityless three dimensional space and rotating about three axes. It hits a frictionless, infinitely hard plane barrier. How will it bounce?

(b) What if the barrier is sticky as in 2 (b) above?

Mail your solutions to stephenson@bilgi.edu.tr