# Ponder this

I just discovered this site. It contains all sorts of math/cs/algorithm-related problems. Some of them are beautiful, others so-and-so... But at least in my case, the effects can be already seen - red eyes ðŸ™‚

Here is an really nice challenge:

Ponder This Challenge: This month's puzzle was sent in by Joe Buhler.
It came from a SIGCSE meeting via Eric Roberts.

A read-only array of length n, with address from 1 to n inclusive,
contains entries from the set {1, 2, ..., n-1}.
By Dirichlet's Pigeon-Hole Principle there are one or more duplicated
entries. Find a linear-time algorithm that prints a duplicated value,
using only "constant extra space". (This space restriction is important;

we have only a fixed number of usable read/write
memory locations, each capable of storing an integer between 1 and n.
The number of such locations is constant, independent of n.
The original array entries can not be altered.) The algorithm should
be easily implementable in any standard programming language.

Or this one:

Ponder This Challenge: A large rectangle is partitioned into smaller rectangles, with sides parallel to those of the large rectangle. Each smaller rectangle has at least one side whose length is an integer. (For some rectangles this may be the horizontal side; for others, the vertical side.)

Prove that the same holds true of the large rectangle.

P.S. - please don't post the solutions in the comments so that others can enjoy the problems!

Tags