Associated Topics || Dr. Math Home || Search Dr. Math

### Sets and Integer Pairs

```
Date: 6/10/96 at 18:47:53
Subject: IMO: Sets and integer pairs

Can you solve problem No.1 and No.4 of International Math Olympiad
'94?  I can't seem to find the  answer on the 'Net. Thank you very
much.

Sg

Problem 1 (proposed by France)

Let m and n be positive integers.  Let a_1, a_2, ..., a_m be distinct
elements of {1, 2, ..., n} such that whenever a_i + a_j <= n for
some i, j, 1 <= i <= j <= m, there exists k, 1 <= k <= m,
with a_i + a_j = a_k. Prove that

a_1 + a_2 + ... + a_m           n + 1
-------------------------  >=  ---------
m                       2
...

Problem 4 (proposed by Australia)
Determine all ordered pairs (m,n) of positive integers such that

n^3 + 1
-------------
mn - 1

is an integer.
```

```
Date: 9/13/96 at 21:21:51
From: Doctor Ceeks
Subject: Re: IMO: Sets and integer pairs

Hi,

Here's a solution to #1:

Let S = { a_1, a_2, a_3, ... , a_m}.

First note that if d is in S, then d+d=2d is in S provided 2d<=n.
But then, 2d+d=3d is in S provided 3d<=n.  Indeed, kd is in S for all
k such that kd <= n.

Let t be the smallest integer in S.  We know all multiples of t less
than or equal to n are in S.  Divide the integers between 1 and n into
t sets, grouping together numbers which leave the same remainder upon
division by t (i.e. congruence classes modulo t).  Note that the
average of the numbers in any such group is at least (n+1)/2 (or
doesn't exist if the group is empty).  This is because the smallest
number, say x, in any such group must be at least t, and if x is in
the group, then x+kt is in the group for all k such that x+kt <= n.
(It's straightforward to see that the average of such numbers is at
least (n+1)/2, because the average of an arithmetic series is the
average of the first and last term.)

Now, using the fact that the average of a disjoint union of finite
collection of finite sets is at least the average of the numbers in
the set with the smallest average, the problem follows.
---

Here's a solution to #4:

We have mn-1 | n^3+1.  Therefore, mn-1 | n^3+1+mn-1=n(n^2+m).
Since n and mn-1 are relatively prime, this implies mn-1 | n^2+m.
But then, we have mn-1 | n^2+m +m(mn-1)=n(n+m^2).  Again, this implies
that mn-1 | n+m^2.  But now we see mn-1 | n+m^2 + m^2(mn-1)=n(m^3+1),
and we conclude that mn-1 | m^3+1.

In other words, if (n,m) is a solution to the problem, so is (m,n).
So without loss of generality, we assume m<=n.

Since mn-1 | n+m^2, we must have that mn-1 <= n+m^2, which rearranges
to n(m-1) <= m^2 +1.

If m is not 1, then we have n <= (m^2+1)/(m-1) = m+1 + 2/(m-1).
If m exceeds 3, this shows that m<=n<=m+1.

So now we just have to check a few cases.

If m=1, we find n=2 or 3.
If m=2, we find n=2 or 5.(Recall m<=n.)
If m=3, we find n=5.
If m>3, then we have to check n=m and n=m+1.
If n=m, we seek m such that m^2-1 | m^2+m, which is only possible
if m^2-1 | m+1...i.e. m=2, a contradiction (to m>3).
If n=m+1, we seek m such that m^2+m-1 | m^2+m+1, which is crazy for
m > 3.

Thus, the solutions are:

(1,2) (2,1) (1,3) (3,1) (2,2) (2,5) (5,2) (3,5) (5,3)

-Doctor Ceeks,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search