superprismatic 11 Posted July 19, 2012 Report Share Posted July 19, 2012 For an integer n≥2, let O_{n} = {1,3,5,...,2n-1}. Prove that n^{2}-2 cannot be written as a sum of distict elements of O_{n}. Quote Link to post Share on other sites

0 curr3nt 23 Posted July 19, 2012 Report Share Posted July 19, 2012 The sum of O_{n} is equal to n^{2}. Since 2 is not within O_{n} there is no way to get n^{2}-2. The closest possible would be n^{2}-1 or n^{2}-3. Quote Link to post Share on other sites

0 jim 1 Posted July 19, 2012 Report Share Posted July 19, 2012 I would like to propose an extension of this problem. Same conditions. Show every number from one to n squared can be expressed as a sum of distinct odd integers from 1 to 2n-1 except for the numbers 2 and n squared - 2 Quote Link to post Share on other sites

0 EventHorizon 15 Posted July 20, 2012 Report Share Posted July 20, 2012 I would like to propose an extension of this problem. Same conditions. Show every number from one to n squared can be expressed as a sum of distinct odd integers from 1 to 2n-1 except for the numbers 2 and n squared - 2 First, an obvious symmetry. Since they all sum to n^2, if you can show x as a sum of distinct odd integers from 1 to 2n-1, then n-x is simply the sum of all the other integers besides those used to sum to x. This means if I prove I can find sums for the first half of them, I can find sums for the second half based on the sums from the first half. For the odd numbers up to 2n-1, obviously you have the number already in the set. For the even numbers up to 2n, the odd number just below it is in the set, so add in 1. This doesn't work for getting 2 due to the distinct element restriction. If I add in 2n-1 to all those sums (except the two that used 2n-1), I can get all the way up to 4n-3, except for the value 2n-1+2=2n+1, due to not being able to get a sum for 2. Ignore this for now. If I add in the 2n-1 and 2n-3 to all the sums from 1 to 2n-4, I can get all the way to <doesn't really matter for the proof> while missing only 2n-1+2n-3+2=4n-2. Using this pattern of adding in the next largest element will work, but gives us a sequence of missed numbers. This sequence is easy to find a sum for as follows: (2n-1)+2 = (2n-3)+3+1 (2n-1)+(2n-3)+2 = (2n-1)+(2n-5)+3+1 etc So I take the smallest one included and use the next smallest. This gives a difference of 4 to make up... which 1 and 3 will do. The problem occurs when the smallest element included is 5, since this would require two 3's. For n>3, I've already passed halfway, so I can use the first thing I showed to give sums for the rest (except for n^2-2, which there isn't one for as shown by curr3nt). So I simply need to show it works for 0<n<=3. n=1 {1} for 1 n=2 {1} for 1 none for 2, which in this case is the same as n^2-2 {3} for 3 {1,3} for 4 n=3 {1} for 3 none for 2 {3} for 3 {1,3} for 4 {5} for 5 {1,5} for 6 none for 7 since 3^2-2=7 {3,5} for 8 {1,3,5} for 9 I should probably include that summing no elements results in a sum of 0, and summing them all gives n^2. A proof of the latter is achieved by pairing up the elements into pairs that sum to 2n, and seeing how many pairs there are. For even numbers, there are n/2 pairs. n/2 * 2n = n^2. For odd numbers there are (n-1)/2 pairs and one element left.... which is n itself. (n-1)/2 * 2n + n = n(n-1) + n = n^2 - n + n = n^2. Quote Link to post Share on other sites

0 jim 1 Posted July 20, 2012 Report Share Posted July 20, 2012 Event Horizon-- I think your proof is essentially the same as mine, but formulated in a different fashion. I basically used induction. We can do 3=3 and 4=3+1. Let m be the smallest number greater than 2 which we cannot do. It must be at least 5 so m-2 is at least 3 and as a smaller number greater than 2 we can do it. We adjust the solution for m-2 by increasing one of the odd numbers by two, replacing it with an odd nuimber not already included in the set of m-2. Since the solution for m-2 is not the null set, we can always do this unless the solution for m-2 is of the form U(j) which is all the allowable odd numbers from j upwards for some j less than or equal to 2n-1. But in this case we can replace j with 1 and 3 and j-2 which we can always do as long as j>5. If j=5 we get our sum m-2 = n^2 - 4 so m = n^2 -2 which is in fact the smallest non-solution except for 2. j=3 and j=1 give us m-2 = n^2 -1 and n^2 which in either case give us m> n^2 which we can also not do because they are too large. Quote Link to post Share on other sites

## Question

## superprismatic 11

For an integer n≥2, let O

_{n}= {1,3,5,...,2n-1}. Prove thatn

^{2}-2 cannot be written as a sum of distict elements of O_{n}.## Link to post

## Share on other sites

## 4 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.