Problem solving usually involves getting from a set 
In a very vague sense this can be regarded as saying that mathematical reasoning doesn’t obey the triangle inequality: the “distance” from 
I feel that the following almost-funny problem embodies this principle:
Given 51 distinct integers between 1 and 100, prove that two of them are relatively prime.
If you’ve never seen this before and you’re able to solve it within seconds, you’ll have to take my word that this problem can stump good problem solvers for a good number of hours. However, the right
Here’s my candidate: two of the integers must be adjacent. Can you quickly deduce that from the given data? You should be able to… Can you quickly derive the desired conclusion (two of the numbers are relatively prime) from the middle stepping stone (two of them are adjacent)? this is even easier. Done!
The problem deceptively leads the innocent solver down wrong paths, like how various primes may divide the 51 numbers. The right insight is that you can much more easily prove a much stronger statement: not only are two numbers relatively prime, two of them must actually differ by 1, and thus in particular be very much relatively prime.
A similarly confusing problem is to show that every odd prime is the difference of two squares. Can you find the
A similar, yet truly much harder, problem is to prove that among 51 distinct integers in the same range (1 to 100) there must be one who divides another. There is arguably a
Tags: Problem Solving
I’m a lousy problem solver, yet I solved the three problems almost immediately. I feel that “there’s a Z” plus the problems are provable is a hint powerful enough to make the three problems in your post easy to solve. Maybe just as the book How to Solve It: Modern Heuristics explains, the hint sets a problem-solving context, which greatly reduces our search space.
That’s very true – sometimes just knowing (or believing!) that there is a solution helps, and even more so if the solution is known to have be “elementary” in some sense, or to take a certain form. Still, hats off to you – I do believe the third problem is significantly harder than the first two, and solving it instantly is quite remarkable.
Am I missing something here? The difference of two squares is:
a^2 – b^2 = (a+b) . (a-b)
Since, its the product of two quantities – it can’t be prime!
What’s 6^2-5^2?
I think you mean
“Given 51DISTINCT integers between 1 and 100, prove that two of them are relatively prime. “
@ernie that’s right, although since the numbers form a set (rather than a sequence) it is common to omit the “distinct” part. Just to be safe I’ll update the post – thanks for the catch.
Dear Alon, congratulations on joining the mathblogging circles! –Gil
I think many mathematical problems are NP in their nature. They have a short solution which is easy to verify, but it might be quite hard to find the solution. Therefore, I do not like the tendency to look down on short proofs.