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.
Markdown
Appears as
*italics* or _italics_
italics
**bold** or __bold__
bold
- bulleted - list
bulleted
list
1. numbered 2. list
numbered
list
Note: you must add a full line of space before and after lists for them to show up correctly
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 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
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
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
Sort by:
Top NewestThis is the expression for the number of Permutations with Repetition, and hence must always be a natural number.
Log in to reply
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.
Log in to reply
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!
Log in to reply
Do you find my proof clear?
Log in to reply