(a) Prove that the set $X = (1,2,....100)$ cannot be partitoned into THREE subsets such that two numbers differing by a square belong to different subsets. (b) Prove that $X$ can so be partitioned into $5$ subsets.
Problem
Source: Indian Postal Coaching 2005
Tags: number theory unsolved, number theory
dgreenb801
17.02.2010 09:04
Here is my solution to part a:
Suppose three such subsets exist. Let the subsets be A,B, and C. 26,17, and 1 must all be in different subsets, so we can assume 26 is in A, 17 is in B and 1 is in C (make a list as you read the proof). Then 42 must be in C (42-26=16, 42-17=25). Then 51 must be in B (51-42=9, 51-26=25). Then 2 must be in A (51-2=49, 2-1=1). Then 18 must be in C (18-2=16, 18-17=1). Then 27 must be in B (27-18=9, 27-2=25). Then 43 must be in A(43-42=1, 43-27=16). Then 52 must be in C (52-43=9, 52-51=1). Then 53 must be in A(53-52=1, 53-17=36). Then 78 must be in B(78-53=25, 78-42=36). Then 82 must be in A(82-78=4, 82-1=81). Then 91 must be in B(91-82=9, 91-42=49). But then 91-27=64, and 91 and 27 are both in B! Thus, three subsets cannot exist.
I still wonder if there is a shorter route...
noman
17.02.2010 18:49
i cant realize ur solution sir.plz can u make it more clear?? else is it the general solution???/
dgreenb801
18.02.2010 00:27
What is the first statement I made that you don't understand?
Mystery5
20.02.2010 03:22
I think a shorter route is to notice that for any x in the range 1<=x<=75 we have to have the values x+9 and x+16 in the same subset since x and x+25 have to be in two different subsets and x+9 and x+16 can't be in either of those. This puts the values of 10, 17, 24, ... 87 all in one subset. (x=1 => 10 and 17 are together, x=8 => 17 and 24 are together etc.) In particular we would have to have 10 and 59 in the same subset which is not allowed. I'm curious to know if anyone has a more elegant solution to part b) than I was able to come up. By more elegant, I mean a solution that can be demonstrated without having to list all 100 numbers like I did. Taking the integers in order until a difference of 25 was going to result, and then shifting by 2 (motivated by the fact that no squares are congruent to 2 or 3 mod 5), and then shifting back and forth again as needed, I was able to come up with this (each column is a subset): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 28 29 30 26 27 33 34 35 31 32 38 39 40 36 37 43 44 45 41 42 48 49 50 46 47 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 78 79 80 76 77 83 84 85 81 82 88 89 90 86 87 93 94 95 91 92 98 99 100 96 97