Please also provide a counter-example if this conjecture is invalid.
Let a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1,a2,⋯,an be positive integers such that a=∑i=1nai\displaystyle a=\sum_{i=1}^na_ia=i=1∑nai.
Prove that: a!∏i=1nai!∈N\frac{a!}{\prod_{i=1}^na_i!}\in\mathbb N∏i=1nai!a!∈N
P.S. I currently have no solution. Help is much appreciated.
Note by Kenny Lau 5 years, 10 months ago
Easy Math Editor
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:
*italics*
_italics_
**bold**
__bold__
- bulleted- list
1. numbered2. list
paragraph 1paragraph 2
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> 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"
\(
\)
\[
\]
2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
This is the expression for the number of Permutations with Repetition, and hence must always be a natural number.
Apart from what Brian suggested (but similar), you can also note that your expression is the multinomial coefficient (aa1,a2,…,an)\dbinom{a}{a_1,a_2,\ldots, a_n}(a1,a2,…,ana) which must be an integer if you use the combinatorial interpretation.
For some purely arithmetical / number-theoretical proofs, see this and choose the answer you find best.
Let's prove, in the first place, that
∀a,n∈N,∏i=1n(a+i)n!∈N\forall a,n \in \mathbb{N}, \displaystyle\frac{\displaystyle\prod_{i=1}^n \left( a+i \right)}{n!} \in \mathbb{N} ∀a,n∈N,n!i=1∏n(a+i)∈N. (1) (1) (1)
Let a∈N a \in \mathbb{N} a∈N.
For that achievement, I will prove that
∀i∈{1,...,n},∃j∈{a+1,...,a+n}:i∣j \forall i \in \{1,...,n \}, \exists j \in \{a+1,..., a+n \}: i|j ∀i∈{1,...,n},∃j∈{a+1,...,a+n}:i∣j.
Let's suppose, in first place, by reductio ad absurdum, that ∄j∈{a+1,...,a+n}:n∣j \nexists j \in \{a+1,..., a+n \}: n|j ∄j∈{a+1,...,a+n}:n∣j. Let m1=max{j∈N:n∣j∧j≤a}m_1= \max \{j \in \mathbb{N}: n|j \land j\leq a \} m1=max{j∈N:n∣j∧j≤a}. Let's consider m1+n m_1+n m1+n. We have that, by hypothesis, ∄j∈{a+1,...,a+n}:n∣j \nexists j \in \{a+1,..., a+n \}: n|j ∄j∈{a+1,...,a+n}:n∣j, so m1+n>a+n m_1+n>a+n m1+n>a+n. By definition of m1 m_1 m1, we have that m1≤a ⟺ −m1≥−am_1 \leq a \iff -m_1 \geq -a m1≤a⟺−m1≥−a. We can conclude that
m1+n>a+n ⟺ n>a+n−m1 ⟹ n>a+n−a ⟹ n>nm_1+n>a+n \iff n>a+n-m_1 \implies n>a+n-a \implies n>n m1+n>a+n⟺n>a+n−m1⟹n>a+n−a⟹n>n
which is an absurdum, so ∃j∈{a+1,...,a+n}:n∣j \exists j \in \{a+1,..., a+n \}: n|j ∃j∈{a+1,...,a+n}:n∣j.
Now, let i∈{1,...,n−1} i \in \{1,...,n-1 \} i∈{1,...,n−1}. Let's suppose, in these conditions, by reductio ad absurdum, that ∄j∈{a+1,...,a+n}:i∣j \nexists j \in \{a+1,..., a+n \}: i|j ∄j∈{a+1,...,a+n}:i∣j. Let m2=max{j∈N:i∣j∧j<a+1}m_2= \max \{j \in \mathbb{N}: i|j \land j<a+1 \} m2=max{j∈N:i∣j∧j<a+1}. By definition of m2 m_2 m2, we have that m2<a+1 ⟺ −m2>−(a+1)m_2<a+1 \iff -m_2>-(a+1) m2<a+1⟺−m2>−(a+1). Now, let's consider m2+im_2+i m2+i. By hypothesis we have that ∄j∈{a+1,...,a+n}:i∣j \nexists j \in \{a+1,..., a+n \}: i|j ∄j∈{a+1,...,a+n}:i∣j, so m2+i>a+nm_2+i>a+n m2+i>a+n. We can conclude that
m2+i>a+n ⟺ i>a+n−m2 ⟹ i>a+n−(a+1) ⟹ i>n−1 ⟹ i∉{1,...,n−1}m_2+i>a+n \iff i>a+n-m_2 \implies i>a+n-(a+1) \implies i>n-1 \implies i \notin \{1,...,n-1 \} m2+i>a+n⟺i>a+n−m2⟹i>a+n−(a+1)⟹i>n−1⟹i∈/{1,...,n−1}
which is an absurdum, as wanted. So we have that
Let's consider, for each i∈{1,...,n}i \in \{1,...,n \} i∈{1,...,n}, Ai={n∈{a+1,...,a+n}:i∣n}A_i= \{ n \in \{a+1,..., a+n \}: i|n \} Ai={n∈{a+1,...,a+n}:i∣n}, and A={Ai:i∈{1,...,n}}A= \{A_i: i \in \{1,...,n \} \} A={Ai:i∈{1,...,n}}. As ∀i∈{1,...,n},Ai≠∅ \forall i \in \{1,...,n \}, A_i \neq \emptyset ∀i∈{1,...,n},Ai=∅, we conclude that A≠∅A \neq \emptyset A=∅. By the Axiom of Choice, we have that
∃f∈F(A,⋃A):∀X∈A,f(X)∈X \exists f \in \mathscr{F} \left( A, \bigcup A \right): \forall X \in A, f(X) \in X ∃f∈F(A,⋃A):∀X∈A,f(X)∈X .
Let f∈F(A,⋃A)f \in \mathscr{F} \left( A, \bigcup A \right) f∈F(A,⋃A) be in that conditions. In these conditions, by the definition of ff f, it is clear that
∏i=1nf(Ai)n!∈N\displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \in \mathbb{N} n!i=1∏nf(Ai)∈N.
Let b∈N b \in \mathbb{N} b∈N be such that b=∏i=1nf(Ai)n! b= \displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} b=n!i=1∏nf(Ai) and let Y={f(Ai):i∈{1,...,n}}Y= \{f(A_i): i \in \{1,...,n \} \} Y={f(Ai):i∈{1,...,n}}. We have that
∏i=1n(a+i)n!=∏i=1nf(Ai)n!⋅(∏ai∈{a+1,...,a+n}∖Y(ai))=b⋅(∏ai∈{a+1,...,a+n}∖Y(ai))∈N\displaystyle\frac{\displaystyle\prod_{i=1}^n \left( a+i \right)}{n!}=\displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \cdot \left(\displaystyle\prod\nolimits_{a_i \in\{a+1,..., a+n \}\setminus Y} \left( a_i \right)\right)=b \cdot \left(\displaystyle\prod\nolimits_{a_i \in\{a+1,..., a+n \}\setminus Y} \left( a_i \right)\right) \in \mathbb{N} n!i=1∏n(a+i)=n!i=1∏nf(Ai)⋅(∏ai∈{a+1,...,a+n}∖Y(ai))=b⋅(∏ai∈{a+1,...,a+n}∖Y(ai))∈N
As wanted.
Now, let's prove that
∀(ai)i∈{1,...,n}∈Nn,(∑i=1nai)!∏i=1nai!∈N \forall {\left( a_i \right)}_{i \in \{1,...,n\} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} ∀(ai)i∈{1,...,n}∈Nn,i=1∏nai!(i=1∑nai)!∈N.
Let C={n∈N:∀(ai)i∈{1,...,n}∈Nn,(∑i=1nai)!∏i=1nai!∈N}C= \Bigg\{n \in \mathbb{N}: \forall {\left( a_i \right)}_{i \in \{1,...,n \} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\sum_{i=1}^n a_i \right)! }{\prod_{i=1}^n a_i !} \in \mathbb{N} \Bigg\} C={n∈N:∀(ai)i∈{1,...,n}∈Nn,∏i=1nai!(∑i=1nai)!∈N}. Let a1∈Na_1 \in \mathbb{N} a1∈N. We have that
(∑i=11ai)!∏i=11ai!=a1!a1!=1∈N\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^1 a_i \right)! }{\displaystyle\prod_{i=1}^1 a_i !}=\displaystyle\frac{a_1!}{a_1!}=1 \in \mathbb{N} i=1∏1ai!(i=1∑1ai)!=a1!a1!=1∈N
So, 1∈C 1 \in C 1∈C. Now, let's suppose, by induction hypothesis, that n∈N n \in \mathbb{N} n∈N. Let (ai)i∈{1,...,n+1}∈Nn+1 {\left( a_i \right)}_{i \in \{1,...,n+1 \} } \in {\mathbb{N}}^{n+1} (ai)i∈{1,...,n+1}∈Nn+1. We have that
(∑i=1n+1ai)!∏i=1n+1ai!=((∑i=1nai)+an+1)!(∏i=1nai!)⋅an+1!=(∑i=1nai)!∏i=1nai!⋅∏k=1an+1((∑i=1nai)+k)an+1!\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^{n+1} a_i \right)! }{\displaystyle\prod_{i=1}^{n+1} a_i !}=\displaystyle\frac{ \left(\left(\displaystyle\sum_{i=1}^n a_i \right)+a_{n+1}\right)! }{\left(\displaystyle\prod_{i=1}^n a_i !\right) \cdot a_{n+1}!}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !}\cdot \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!} i=1∏n+1ai!(i=1∑n+1ai)!=(i=1∏nai!)⋅an+1!((i=1∑nai)+an+1)!=i=1∏nai!(i=1∑nai)!⋅an+1!k=1∏an+1((i=1∑nai)+k)
By induction hypothesis, we have that
(∑i=1nai)!∏i=1nai!∈N\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} i=1∏nai!(i=1∑nai)!∈N. Let d∈Nd \in \mathbb{N} d∈N be such that d=(∑i=1nai)!∏i=1nai!d=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} d=i=1∏nai!(i=1∑nai)!. Let v=an+1v=a_{n+1} v=an+1 and S=(∑i=1nai)S= \left(\displaystyle\sum_{i=1}^n a_i \right) S=(i=1∑nai). It is clear that
∏k=1an+1((∑i=1nai)+k)an+1!=∏k=1v(S+k)v! \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!}= \displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!}an+1!k=1∏an+1((i=1∑nai)+k)=v!k=1∏v(S+k)
Applying (1) (1) (1), we conclude that
∏k=1v(S+k)v!∈N\displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!} \in \mathbb{N} v!k=1∏v(S+k)∈N. Let p∈Np \in \mathbb{N} p∈N be such that p=∏k=1v(S+k)v!p=\displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!} p=v!k=1∏v(S+k). In these conditions we have that
(∑i=1n+1ai)!∏i=1n+1ai!=(∑i=1nai)!∏i=1nai!⋅∏k=1an+1((∑i=1nai)+k)an+1!=(∑i=1nai)!∏i=1nai!⋅∏k=1v(S+k)v!=d⋅p∈N \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^{n+1} a_i \right)! }{\displaystyle\prod_{i=1}^{n+1} a_i !}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !}\cdot \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \cdot \displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!}=d \cdot p \in \mathbb{N} i=1∏n+1ai!(i=1∑n+1ai)!=i=1∏nai!(i=1∑nai)!⋅an+1!k=1∏an+1((i=1∑nai)+k)=i=1∏nai!(i=1∑nai)!⋅v!k=1∏v(S+k)=d⋅p∈N, because d,p∈Nd,p \in \mathbb{N} d,p∈N.
In these conditions we can conclude that n+1∈Cn+1 \in C n+1∈C. In sum, C=NC= \mathbb{N} C=N; so,
QED
Log in to reply
Where is a complete proof from zero very justified. Hope you enjoy!
Do you find my proof clear?
Problem Loading...
Note Loading...
Set Loading...
Easy Math Editor
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
This is the expression for the number of Permutations with Repetition, and hence must always be a natural number.
Apart from what Brian suggested (but similar), you can also note that your expression is the multinomial coefficient (a1,a2,…,ana) which must be an integer if you use the combinatorial interpretation.
For some purely arithmetical / number-theoretical proofs, see this and choose the answer you find best.
Let's prove, in the first place, that
∀a,n∈N,n!i=1∏n(a+i)∈N. (1)
Let a∈N.
For that achievement, I will prove that
∀i∈{1,...,n},∃j∈{a+1,...,a+n}:i∣j.
Let's suppose, in first place, by reductio ad absurdum, that ∄j∈{a+1,...,a+n}:n∣j. Let m1=max{j∈N:n∣j∧j≤a}. Let's consider m1+n. We have that, by hypothesis, ∄j∈{a+1,...,a+n}:n∣j, so m1+n>a+n. By definition of m1, we have that m1≤a⟺−m1≥−a. We can conclude that
m1+n>a+n⟺n>a+n−m1⟹n>a+n−a⟹n>n
which is an absurdum, so ∃j∈{a+1,...,a+n}:n∣j.
Now, let i∈{1,...,n−1}. Let's suppose, in these conditions, by reductio ad absurdum, that ∄j∈{a+1,...,a+n}:i∣j. Let m2=max{j∈N:i∣j∧j<a+1}. By definition of m2, we have that m2<a+1⟺−m2>−(a+1). Now, let's consider m2+i. By hypothesis we have that ∄j∈{a+1,...,a+n}:i∣j, so m2+i>a+n. We can conclude that
m2+i>a+n⟺i>a+n−m2⟹i>a+n−(a+1)⟹i>n−1⟹i∈/{1,...,n−1}
which is an absurdum, as wanted. So we have that
∀i∈{1,...,n},∃j∈{a+1,...,a+n}:i∣j.
Let's consider, for each i∈{1,...,n}, Ai={n∈{a+1,...,a+n}:i∣n}, and A={Ai:i∈{1,...,n}}. As ∀i∈{1,...,n},Ai=∅, we conclude that A=∅. By the Axiom of Choice, we have that
∃f∈F(A,⋃A):∀X∈A,f(X)∈X .
Let f∈F(A,⋃A) be in that conditions. In these conditions, by the definition of f, it is clear that
n!i=1∏nf(Ai)∈N.
Let b∈N be such that b=n!i=1∏nf(Ai) and let Y={f(Ai):i∈{1,...,n}}. We have that
n!i=1∏n(a+i)=n!i=1∏nf(Ai)⋅(∏ai∈{a+1,...,a+n}∖Y(ai))=b⋅(∏ai∈{a+1,...,a+n}∖Y(ai))∈N
As wanted.
Now, let's prove that
∀(ai)i∈{1,...,n}∈Nn,i=1∏nai!(i=1∑nai)!∈N.
Let C={n∈N:∀(ai)i∈{1,...,n}∈Nn,∏i=1nai!(∑i=1nai)!∈N}. Let a1∈N. We have that
i=1∏1ai!(i=1∑1ai)!=a1!a1!=1∈N
So, 1∈C. Now, let's suppose, by induction hypothesis, that n∈N. Let (ai)i∈{1,...,n+1}∈Nn+1. We have that
i=1∏n+1ai!(i=1∑n+1ai)!=(i=1∏nai!)⋅an+1!((i=1∑nai)+an+1)!=i=1∏nai!(i=1∑nai)!⋅an+1!k=1∏an+1((i=1∑nai)+k)
By induction hypothesis, we have that
i=1∏nai!(i=1∑nai)!∈N. Let d∈N be such that d=i=1∏nai!(i=1∑nai)!. Let v=an+1 and S=(i=1∑nai). It is clear that
an+1!k=1∏an+1((i=1∑nai)+k)=v!k=1∏v(S+k)
Applying (1), we conclude that
v!k=1∏v(S+k)∈N. Let p∈N be such that p=v!k=1∏v(S+k). In these conditions we have that
i=1∏n+1ai!(i=1∑n+1ai)!=i=1∏nai!(i=1∑nai)!⋅an+1!k=1∏an+1((i=1∑nai)+k)=i=1∏nai!(i=1∑nai)!⋅v!k=1∏v(S+k)=d⋅p∈N, because d,p∈N.
In these conditions we can conclude that n+1∈C. In sum, C=N; so,
∀(ai)i∈{1,...,n}∈Nn,i=1∏nai!(i=1∑nai)!∈N.
QED
Log in to reply
Where is a complete proof from zero very justified. Hope you enjoy!
Do you find my proof clear?