• Support PF! Buy your school textbooks, materials and every day products Here!

Proving the number of solutions to |a|+|b|= k

  • Thread starter brztgkj
  • Start date
  • #1
2
0

Homework Statement


Prove that there are 4k solutions to the equation |a|+|b| = k, i.e. 4k pairs of a and b such that |a|+|b|=k.

Homework Equations


none


The Attempt at a Solution


I've written out the first few:
for k = 0, the only solution is (0,0)
for k =1, we have (-1,0) (0, -1) (0,1)(1,0)
for k =2, we have (1,1) (-1, -1)(-1,1)(1,-1) (0,2)(2,0)(-2,0)(0,-2)
for k =3, we have (2,1)(1,2)(-2,1)(1,-2)(2,-1)(-1,2)(-1,-2)(-2,-1)(0,3)(3,0)(0,-3)(-3,0)

The pattern seems to involve looking at the order/sign permutations of the pairs. The total number of solutions seems to be:

4(for the permutations made by sign changes and flipping the order of the (0,k) pair) + n*8(where n is the number of pairs where a doesn't equal b and neither a nor b equals 0, and 8 is the number of permutations made by sign changes and flipping the order)+4 (if there is a pair where a=b (i.e. if k is even) for the sign/ordering permutations).

Then I would need to prove that n=(k-1)/2 rounded down, and prove k=0 and k=1 separately. I think proving what n equals could be accomplished by arguing that the first pair (in which the two elements are not equal) must be either ((k/2)+1, (k/2)-1) (if k is even) or ((k-1)/2, (k+1)/2) (if k is odd), and that there are only k/2 rounded down more pairs.
It seems like there should be an easier way of doing this, but I'm stuck at the moment. Any suggestions?
 

Answers and Replies

  • #2
828
2

Homework Statement


Prove that there are 4k solutions to the equation |a|+|b| = k, i.e. 4k pairs of a and b such that |a|+|b|=k.

Homework Equations


none


The Attempt at a Solution


I've written out the first few:
for k = 0, the only solution is (0,0)
for k =1, we have (-1,0) (0, -1) (0,1)(1,0)
for k =2, we have (1,1) (-1, -1)(-1,1)(1,-1) (0,2)(2,0)(-2,0)(0,-2)
for k =3, we have (2,1)(1,2)(-2,1)(1,-2)(2,-1)(-1,2)(-1,-2)(-2,-1)(0,3)(3,0)(0,-3)(-3,0)

The pattern seems to involve looking at the order/sign permutations of the pairs. The total number of solutions seems to be:

4(for the permutations made by sign changes and flipping the order of the (0,k) pair) + n*8(where n is the number of pairs where a doesn't equal b and neither a nor b equals 0, and 8 is the number of permutations made by sign changes and flipping the order)+4 (if there is a pair where a=b (i.e. if k is even) for the sign/ordering permutations).

Then I would need to prove that n=(k-1)/2 rounded down, and prove k=0 and k=1 separately. I think proving what n equals could be accomplished by arguing that the first pair (in which the two elements are not equal) must be either ((k/2)+1, (k/2)-1) (if k is even) or ((k-1)/2, (k+1)/2) (if k is odd), and that there are only k/2 rounded down more pairs.
It seems like there should be an easier way of doing this, but I'm stuck at the moment. Any suggestions?
I would think about this in 2 cases:
Case 1) neither a nor b is 0.
Case 2) either a or b is 0.


Now, let's look at Case 1.
First, let's just consider the case where a and b are both positive. So, how many ways can we write k as the sum of two strictly positive integers. Write k like this:
[tex]k=1 + 1 + \cdots + 1[/tex]

So now, realize that there are k-1 gaps between the 1's. Put an imaginery divider between each of these gaps and regard all the 1's to the left of the gap to be a and all of the 1's to the right of the gap to be b. There are k-1 different gaps, so there are k-1 different ways to pick two POSITIVE integers whose sum is k. But that isn't all of the story for Case 1 because for each (a,b) the pairs (-a,b), (-a,-b), (a,-b) are all solutions, so there are 4(k-1) solutions for Case 1.

Now think about Case 2.

Also, I would probably clean up what I wrote a little and try to fit it all in to 1 case (which can be done, btw).
 
  • #3
2
0
I would think about this in 2 cases:
Case 1) neither a nor b is 0.
Case 2) either a or b is 0.


Now, let's look at Case 1.
First, let's just consider the case where a and b are both positive. So, how many ways can we write k as the sum of two strictly positive integers. Write k like this:
[tex]k=1 + 1 + \cdots + 1[/tex]

So now, realize that there are k-1 gaps between the 1's. Put an imaginery divider between each of these gaps and regard all the 1's to the left of the gap to be a and all of the 1's to the right of the gap to be b. There are k-1 different gaps, so there are k-1 different ways to pick two POSITIVE integers whose sum is k. But that isn't all of the story for Case 1 because for each (a,b) the pairs (-a,b), (-a,-b), (a,-b) are all solutions, so there are 4(k-1) solutions for Case 1.

Now think about Case 2.

Also, I would probably clean up what I wrote a little and try to fit it all in to 1 case (which can be done, btw).
Yes--I see how Case 2 fits in conceptually at least. I'm thinking about it as [tex]k=0 + 1 + 1 + \cdots + 1 + 0[/tex]
and then the same argument for gaps between 1s, but for the gaps between a zero and a one, there are only 2 solutions (a, 0) and (-a, 0) for the 0+1+... gap and (0, -a) and (0, a) for the ...+1+0 gap?

btw, I think that that was a beautiful solution, and I'm not going to use it on my homework because I wouldn't have gotten there by myself. Do you have any advice for coming up with simple solutions like that instead of the confusing mess that I did?
 
  • #4
828
2
Yes--I see how Case 2 fits in conceptually at least. I'm thinking about it as [tex]k=0 + 1 + 1 + \cdots + 1 + 0[/tex]
and then the same argument for gaps between 1s, but for the gaps between a zero and a one, there are only 2 solutions (a, 0) and (-a, 0) for the 0+1+... gap and (0, -a) and (0, a) for the ...+1+0 gap?

btw, I think that that was a beautiful solution, and I'm not going to use it on my homework because I wouldn't have gotten there by myself. Do you have any advice for coming up with simple solutions like that instead of the confusing mess that I did?
Yes, you got it. As far as advice, just try to break stuff down to things that you know or think you can figure out. So, |a|+|b|=k is kind of whacky at first, but I just thought about it in terms of positive integers, which I knew how to handle (or at least, knew I could figure it out). But, as you might have seen, this can be generalized, for example how many solutions are there to:
[tex]x_1 + x_2 + \cdots + x_n = k[/tex]

where all the [tex]x_i[/tex]'s are positive?
 

Related Threads on Proving the number of solutions to |a|+|b|= k

  • Last Post
Replies
4
Views
899
Replies
5
Views
1K
Replies
13
Views
2K
  • Last Post
Replies
21
Views
2K
Replies
5
Views
3K
  • Last Post
Replies
5
Views
2K
Replies
5
Views
393
Replies
2
Views
1K
Replies
5
Views
3K
  • Last Post
Replies
0
Views
2K
Top