Mistakes Give Rise To Problems-19

Algebra Level 4

We know the following property of exponents that:

$\left(\dfrac{a}{b}\right)^{c}=\dfrac{a^{c}}{b^{c}},$

but we can't do this in factorials as:

$\left(\dfrac{a}{b}\right)!=\dfrac{a!}{b!}$

In general, doing this will be a Big Mistake. However, this holds for certain integers $a$ and $b.$ For how many ordered pairs of integers $(a,b)$ where $1≤b≤a≤100$ does this hold?

Try this too .

The answer is 199.

1 solution

Tasmeem Reza
Dec 23, 2014

It's easy to see that for each value of $a$ , $b=\left \{ 1,a \right \}$ is a valid solution. Thus we have $2$ choices for each value of $a$ and we get a total of $2 \times 100$ valid solutions. But we counted the pair $\left \{ 1,1 \right \}$ twice. So we have $200-1=199$ valid solutions.

Now, for $b \neq \left \{ 1,a \right \}$ we can rewrite the equation as, (let $k=\left ( \frac{a}{b} \right )$ ) $k!=\frac{a!}{b!}$ $\Rightarrow \frac{a!}{b! \times k!}=1$ $\Rightarrow \binom{a}{b,k} = 1$ As, $\binom{a}{b,k} = \binom{a-1}{b-1,k} + \binom{a-1}{b,k-1}$ , using the fact that every multinomial coefficient is at least $1$ , we can write, $\binom{a-1}{b-1,k} < \binom{a}{b,k}$ $\Rightarrow 1 < \binom{a}{b,k}$

Thus there's no solution for $b \neq \left \{ 1,a \right \}$ and the answer is $\boxed{199}$

If a=b these are also possible cases

Himanshu Goel - 6 years, 5 months ago

Can you explain why "every multinomial coefficient is at least 1"? Is this true even for fractional multinomial coefficients?

Calvin Lin Staff - 6 years, 5 months ago

Oh no! there's an error in my proof. I haven't considered the fractional multinomial coefficients. Following lemmas might help completing my proof.

LEMMA 1: $\binom{n}{n_1,\; n_2,\; n_3,\; ...,\; n_m}$ is an integer if and only if $n_1 + n_2 + n_3 + ... + n_m \leq n$ . The converse of the lemma is also true. $.$ Proof: Let $S$ be a set of $n$ elements with $n_1, n_2, n_3, ... , n_m$ identical elements. Notice that $n_1 + n_2 + n_3 + ... + n_m$ must be less than or equal to $n$ .The number of ways to permute the elements of the set $S$ is $\binom{n}{n_1,\; n_2,\; n_3,\; ...,\; n_m}$ . Thus the term must be an integer because number of permutations can't be a fraction.

$.$

LEMMA 2: every integer multinomial coefficient is at least $1$ .

Proof: Let, an integer multinomial coefficient $\binom{n}{a_1, a_2, a_3,..., a_m}=0$ $\Rightarrow \frac{n!}{a_1! \times a_2! \times a_3! \times ... \times a_m!}=0$

which implies that $n!=0$ . But no solution exists for $n!=0$ . The next integer is $1$ and negative values isn't possible. Thus every multinomial coefficient is at least $1$ .

$.$

As, $\binom{a}{b, k}$ is an integer (that's $1$ ), LEMMA 1 implies $b+k \leq a$ which implies $(b-1)+k \leq a-1$ and $b+(k-1) \leq a-1$ . And again LEMMA 1 implies that $\binom{a-1}{b-1, k}$ and $\binom{a-1}{b, k-1}$ are also integer multinomial coefficient.

As both $\binom{a-1}{b-1, k}$ and $\binom{a-1}{b, k-1}$ are integer multinomial coefficients, both must be greater than or equal to 1. Again, $\binom{a}{b,k} = \binom{a-1}{b-1, k} + \binom{a-1}{b, k-1}$ . which implies, $\binom{a-1}{b-1, k} < \binom{a}{b,k}$ $\Rightarrow 1 < \binom{a}{b,k}$

Sir, is my proof correct, I am still confused.

tasmeem reza - 6 years, 5 months ago

If lemma 1 is in the context of fractional coefficients, then I would disagree with it. If lemma 1 is in the context of integer coefficients, then note that the expression is always an integer. It might possibly be 0, which could be what you are going for?

As for lemma 2, that claim is wrong. If $\sum a_i > n$ , then the coefficient is 0. E.g. there are 0 ways of choosing 2 items from 3 objects.

Calvin Lin Staff - 6 years, 5 months ago

@Calvin Lin – Sir, I've thought of many algebraic manipulations, but all in vein. At last I've come with this number theoretic solution.

If we start from the beginning -- $b=\left \{ 1,a \right \}$ is a valid solution for each value of $a$ . Thus $199$ such pairs.

Now, if we assume some solution exists for $b \neq \left \{ 1,a \right \}$ such that (let, $k = \frac{a}{b}$ ) $\frac{a!}{b!}=k!$ $\Rightarrow \frac{a!}{b!}=a(a-1)(a-2)...(a-(a-b-1))=k!$

Thus $k!$ can be written as a product of $a-b$ positive integers. So we may assume $(a-b)! \mid k!$ . As $(a-b)!$ divides $k!$ , we may assume, $(a-b)! \leq k!$ $\Rightarrow (a-b) \leq k = \frac{a}{b}$ $\Rightarrow ab-b^{2} \leq a$ $\Rightarrow ab-a=a(b-1) \leq b^{2}$ $\Rightarrow a \times \frac{b-1}{b} \leq b\; (\mathrm{dividing\; by\;} b)$ $\Rightarrow a \times \frac{b-1}{b} \leq b \leq a$ $\Rightarrow \frac{b-1}{b} \leq \frac{b}{a} \leq 1 \; (\mathrm{dividing\; by\;} a)$ $\Rightarrow \frac{b}{b-1} \geq \frac{a}{b} \geq 1$ $\Rightarrow \frac{b}{b-1} \geq k \geq 1$ $\Rightarrow b \geq k(b-1) \geq (b-1)$

As both $k$ and $b-1$ are integers, $k(b-1)$ should also be an integer. But notice that, the value of $k(b-1)$ lies between two consecutive integers (that is $b$ and $b-1$ ). Thus we get two cases, that is $\begin{cases} \mbox{either}\quad \quad k(b-1) = (b-1) \\ \mbox{or}\quad \quad \quad \;\; k(b-1) = b \end{cases}$

Solving case 1 with positive integral solutions, we get two solutions, that is - $k=1$ (which implies $a=b$ ) and $b=1$ . These are exactly the solutions which I defined above ( $b=\left\{1,a\right\}$ ).

Solving case 2 with positive integral solutions, we get $k=2$ , $b=2$ thus $a=4$ . But these solutions are invalid because they do not satisfy the original equation. Thus there exists no solution for $b \neq \left \{ 1,a \right \}$

tasmeem reza - 6 years, 5 months ago

By #Tasmeem Reza's way there are 199 ways..But what is both a and b has same values? Then the equation satisfies.So I think there is an additional 99 ways,right? Please reply.

Anandhu Raj - 6 years, 4 months ago

By your way there are 199 ways..But what is both a and b has same values? Then the equation satisfies.So I think there is an additional 99 ways,right?

Anandhu Raj - 6 years, 4 months ago

Mistakes Give Rise To Problems-19

The answer is 199.

1 solution

0 pending reports