Sets and Integer PairsDate: 6/10/96 at 18:47:53 From: Suryadie Gemilang 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/