# The number of Odd integral solutions to a multi-variable, linear equation

Q) Find the number of solutions in $\textbf{odd}$ positive integers to:

$\large{x_1+x_2+x_3+.....+x_r=N}$

$SOL^{n}$ FIRSTLY: Note that all $x_i$ would have odd solutions iff $N-r=even$

This is actually trivial: as we have $odd+odd=even$ and $even+odd=odd$ we can add $odd$ numbers an even number of times to get an $even$ number. and add them $odd$ number of times to get odd numbers. in short: $N=odd \implies r=odd$ and $N=even \implies r=even$ in both cases $N-r=even$

So, to the solution:

I don't know if this is possible to prove by multinomial theorem, but simple application of stars and bars(or in this case, the binary set of $0$'s and $1$'s) work:

I am going to do a brief explaining to those who aren't well aware of this method The idea is to create a set which has a correspondance with the solution set:

among the different arrangements,each type of arrangement of the numbers in the binary set corresponds to a solution.

Example: if we had to find the total number of positive integral solutions (indefinite as to odd or even) to $a+b+c=7$

We would create a set with $7$ one's and $3-1=2$ zeroes as partitions. For a more visual explanation: one arrangement of our set may look like:

$\large{\underbrace{{110101111}}_\text{two 0's, seven 1's}}$

and more importantly: this set will correspond to a the solution triple $(2,1,4)$

thus, different arrangements would correspond to different solution sets, and thus we are reduced to finding the number of different arrangements of the $0's$ and $1's$ in our binary element set.

Basically this is the stars and bars principle

In this method: we use ${r-1}$ $zeroes$ as partitions between the $r$ numbers and each $1$ represents....well each $1$ . So, we have $N$ $one$'s and $r-1$ $zeroes$.

Now, since the least odd positive integer is $1$, we, at first separate $r$ $1's$ because they would $\text{always be included in our binary set}$.

after addition of $r$ fixed $1's$, we have our set looking like:

$\large{ \underbrace{{1010101.....101,111....111}}_\text{r-1 zeroes and r ones,N-r ones}}$

By our previous arguements, $N-r$ is $even$. SO:

We group the $N-r$ $\text{ones in sets of two}$ i.e : $\large{\underbrace{11,11,11.....,11}_{\frac{N-r}{2} \text{ones}}}$

Writing $\frac{N-r}{2}=a$ and noting that each $a$ corresponds to a numerical value of $2$ . and since we already have $r$ ones fixed for each variable, the addition of any number of $2's$ or, in this case, $a's$ would result in the formation of odd numbers ($even+odd=odd$)

$\therefore$The required no. of solutions in odd positive integers for the given equation is

$\text{the no. arrangements of} \frac{N-r}{2} \text{ a's and } (r-1) \text{ zeroes and } r \text{ fixed ones}$

This is the permutation of a total $\dfrac{N-r}{2}+(r-1)=\dfrac{N+r-2}{2}$ objects, out of which: $\frac{N-r}{2}$ objects are of one kind($a's$), and $(r-1)$ other objects of the same kind ($zeroes$).

This is equal to: $\LARGE{\dfrac{(\frac{N+r-2}{2})!}{(r-1)!(\frac{N-r}{2})!}}$

OR:

$\LARGE{\binom{\frac{N+r-2}{2}}{r-1}}$

An example to remove all doubts:

Find the odd positive solutions in $a,b,c$ to the equation:

$a+b+c=7$

In This case: we have $r=3$, $N=7$ $\implies N-r=7-3=4=even$ . therefore, solutions are actually possible.

Next step, is to create the set with $2$ zeroes and $7$ ones:

$\large{S=\underbrace{10101,1111}_\text{2 zeroes and 3 ones, 4 ones}}$

next, write the $4$ ones as $\text{two groups of 2:}$$\large{\underbrace{11,11}_\text{ two '11's or 2 'a's}}$

$\therefore$ We have to find the no. of arrangements of $2$ zeroes and $2$ $a$'s

this is equal to: $\large{\dfrac{4!}{2!2!}=\boxed{6}}$

We now see that these are the only solutions:

$\underbrace{(1,1,5),(1,5,1),(5,1,1),(3,3,1),(1,3,3),(3,1,3)}$ Note by Aritra Jana
6 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

## Comments

Sort by:

Top Newest

Variable replacement would do our job put : . $2{y}_{i}+1={x}_{i}$

Our equation becomes :

$2({y}_{1}+{y}_{2}+.........+{y}_{r})=n-r$

Simplifying a little bit

${y}_{1}+{y}_{2}+..............{y}_{r}=\frac{n-r}{2}$

Now the work is very simple apply multinomial theorom to get :

No. if integral solutions $\Large =\binom{r+\frac{n-r}{2}-1}{r-1}=\binom{\frac{n+r-2}{2}}{r-1}$

So I believe multinomial theorom is a better way to analyze things.(It's my favourite theorom in combinatorics).

- 6 years, 6 months ago

Log in to reply

ahh..well yes... i prefer using a more visual explanation to things.. thus, the method :D

- 6 years, 6 months ago

Log in to reply

It would be much simplier if we use generating functions

- 6 years, 6 months ago

Log in to reply

obviously.. but the main intention of my post was to explain this using simple logic, which everyone would understand. for that very reason, i even fairly explained the stars and bars method in my post

- 6 years, 6 months ago

Log in to reply

yes,you are right,everyone must know the basic....the stars and bars method is really a classic method

- 6 years, 6 months ago

Log in to reply

I would see it as trying to arrange N balls in r buckets, where each bucket has an odd number of balls. Clearly, none of these buckets can be empty since 0 is an even number. So each bucket contains at least one ball. So we throw one ball into each bucket, leaving us with N-r balls to distribute. Now since the number of balls in each bucket can't be even, we tie the N-r balls into pairs. Now we have (N-r)/2 blocks to distribute onto r buckets. There are (r-1 + [(N-r)/2] ) C (r-1) ways of doing this. C stands for combination.

Not really sure about the last line though

Sorry I don't know how to use latex.

- 6 years, 5 months ago

Log in to reply

this is exactly what i tried to say :D

- 6 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...