Math Challenge - September 2021

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
15,441
13,481
Summary: Gamma function. Combinatorics. Stochastic. Semisimple Modules. Topological Groups. Metric spaces. Logarithmic inequality. Stochastic. Primes. Approximation theory.


1. (solved by @julian and @benorin ) Let ##f## be a function defined on ##(0,\infty)## such that ##f(x)>0## for all ##x>0.## Suppose that ##f## has the following properties:
  1. ##\log f(x)## is a convex function.
  2. ##f(x+1)=x\cdot f(x)## for all ##x>0.##
  3. ##f(1)=1.##
Then ##f(x)=\displaystyle{\lim_{n \to \infty}\dfrac{n!n^x}{x(x+1)\cdots (x+n)}}=:\Gamma(x)## for all ##x>0.##


2. (solved by @TeethWhitener ) Let ##T = (x_1, x_2, \ldots , x_m)## be a sequence of not necessarily distinct reals. For any positive ##b##, define
$$
T_b := \{(x_i, x_j ) \,|\, 1 \leq i, j \leq m, |x_i-x_j | \leq b\}.
$$
Show that for any sequence ##T## and for every integer ##r>1,##
$$|T_r| < (2r-1)|T_1|.$$

3. Let ##X,Y## be two independent identically distributed real random variables. For a positive ##b,## define ##p_b:=\operatorname{prob}\left(|X-Y|\leq b\right).## Then for every integer ##r,## ##p_r\leq (2r-1)p_1.## Thus
$$
\operatorname{prob}\left(|X-Y|\leq 2\right) \leq 3\cdot \operatorname{prob}\left(|X-Y|\leq 1\right)
$$

4. Let ##\mathbb{F}## be a field and ##G## a finite group, such that ##\operatorname{char}\mathbb{F}\,\nmid\,|G|.## Prove that ##\mathbb{F}G## is semisimple, and show that this is not true if ##\operatorname{char}\mathbb{F}\,\mid\,|G|.##


5. A group ##G## together with a topology, such that the mapping on ##G\times G## (equipped with the product topology) to ##G## given by ##(x,y)\longmapsto xy^{-1}## is continuous, is called a topological group (e.g. a Lie group). Prove
  1. (solved by @jbergman ) ##G## is a topological group if and only if inversion and multiplication are continuous.
  2. (solved by @jbergman ) The mappings ##x\longmapsto xg## and ##x\longmapsto gx## are homeomorphisms for each ##g\in G.##
  3. (solved by @jbergman ) Each open subgroup ##U\leq G## is closed, and each closed subgroup ##U\leq G## of finite index is open. If ##G## is compact, then each open subgroup is of finite index.
  4. (solved by @jbergman ) Let ##H \leq G## be a subgroup equipped with the subspace topology, ##K\trianglelefteq G## a normal subgroup, and ##G/K## equipped with the quotient space topology. Then ##H## and ##G/K## are again topological groups and the projection ##\pi\, : \,G \twoheadrightarrow G/K## is open.
  5. ##G## is Hausdorff if and only if ##\{1\}## is a closed set in ##G.## ##G/K## is Hausdorff for a normal subgroup ##K\trianglelefteq G,## if and only if ##K## is closed in ##G.## If ##G## is totally disconnected, then ##G## is Hausdorff.
  6. Let ##G## be a compact topological group and ##\{X_j \;(j\in I)\}\subseteq G## a family of closed subsets such that for all ## i ,j\in I## there is a ##k\in I## with ##X_k\subseteq X_i\cap X_j.## Then we have for any closed subset ##Y\subseteq G##
    $$Y\cdot \left(\bigcap_{i\in I}X_i\right) = \bigcap_{i\in I} YX_i $$

6. Let ##(X_n,d_n)_{n\in \mathbb{N}_0}## be a sequence of complete metric spaces, and let ##(f_n)_{n\in \mathbb{N}_0}## be a sequence of continuous functions ##f_n:X_{n+1}\longrightarrow X_n## such that the image ##f_n(X_{n+1}) \subseteq (X_n,d_n)## is dense for all ##n\in \mathbb{N}_0##. Then
$$
M_0:= \left\{v_0\in X_0\,|\,\exists\,(v_n)_{n\in \mathbb{N}} \,\forall\,n\in \mathbb{N}\, : \,v_n\in X_n\,\wedge \,f_{n-1}(v_n)=v_{n-1} \right\}
$$
and
$$
M_0\subseteq M:= \bigcap_{n=0}^\infty(f_0\circ f_1\circ\ldots\circ f_n)(X_{n+1})
$$
are dense in ##(X_0,d_0).## In particular ##M\neq \emptyset## in case ##X_0\neq \emptyset.##


7. (solved by @julian ) Prove for all ##x>-1##
$$
x-(1+x)\log (1+x)\leq -\dfrac{3x^2}{2(x+3)}
$$

8. Let ##(\Omega, \mathcal{A},\mathcal{P})## be a probability space, ##B,T,\sigma ## positive real numbers, and ##n\in \mathbb{N}.## For independently distributed random variables ##X_1,\ldots,X_n\, : \,\Omega \longrightarrow \mathbb{R}## with expectation values ##E(X_k)=0## and ##E(X_k^2)\leq \sigma^2##, and boundary ##\|X_k\|_\infty \leq B## for all ##k=1,\ldots,n ## prove
$$
P\left(\dfrac{1}{n}\sum_{k=1}^nX_k \geq \sqrt{\dfrac{2\sigma^2 T}{n}}+\dfrac{2BT}{3n}\right) \leq e^{-T}.
$$

9. Let ##\mathbb{P}## be the set of all primes, ##p\in \mathbb{P},## and ##n\in \mathbb{N}## a positive integer. ##\operatorname{ord}_p(N)## denotes the number of primes ##p## which occur as divisor in ##\{1,2,\ldots,N\}## counted by multiplicity. E.g. ##N=24=4!## and ##p=3## yields in ##\{3=3^1,6=3^1\cdot 2,9=3^2,12=3^1\cdot 4,15=3^1\cdot 5,18=3^2\cdot 2,21=3^1\cdot 7,24=3^1\cdot 8\}##
$$
\operatorname{ord}_3(24) = 1+1+2+1+1+2+1+1=10
$$
Prove
  1. (solved by @TeethWhitener ) ##\displaystyle{\operatorname{ord}_p(n)=\sum_{k\geq 1}\left\lfloor \dfrac{n}{p^k}\right\rfloor}##
  2. (solved by @TeethWhitener )##2\left.\,\right|\binom{2n}{n}## and ##p\left.\,\right|\binom{2n}{n}## for all ##n<p\leq 2n##
  3. (solved by @TeethWhitener ) ##p\geq 3\,\wedge \,2n/3 <p\leq n \,\Longrightarrow \,p\,\nmid\,\binom{2n}{n}##
  4. (solved by @julian ) ##p^r\left.\,\right|\binom{2n}{n}\,\Longrightarrow \,p^r\leq 2n##
  5. (solved by @julian ) ##\dfrac{2^{2n-1}}{n}\leq \binom{2n}{n}\leq 2^{2n-1}##
  6. (solved by @julian ) ##\displaystyle{\prod_{p\leq n}p<4^n}##


10. Let ##K## be compact and ##C(K):=\{f:K\to \mathbb{R} \text{ or }\mathbb{C}\,|\,f \text{ is continuous}.## A ##n-##dimensional subspace ##M\subseteq C(K)## is called Haar space, if all ##f\in M-\{0\}## have at most ##n-1## zeros. Linear independent functions ##S:=\{\varphi_1,\ldots,\varphi_n \}\subseteq C(K)## are called a Chebyshev- or Haar-system, if ##\operatorname{span}(S)## is a Haar space. We denote the (compact) unit circle ##\mathbb{T} := \{e^{2\pi it} \,|\, t\in [0,1)\}.## Let ##K\subseteq \mathbb{R}## be compact or ##K=\mathbb{T}\, , \,f\in C(K).##

We call a point ##\xi \in K## with ##f(\xi)=0## a simple zero of ##f## if ##\xi## is either on the boundary of ##K## or ##f## changes sign in ##\xi.## If ##f(\xi -t)f(\xi +t)>0## in a neighborhood of ##\xi,## then we speak of a double zero.
  1. A subspace ##M\subseteq C(K)## with ##\dim M=n## is a Haar space if and only if each ##f\in M-\{0\}## that has ##j\in \mathbb{N}_0## simple zeros and ##k\in \mathbb{N}_0## double zeros holdsSo each element $f\in M-\{0\}$ has at most $n-1$ different zeros.
    $$j+2k<n. $$ So each element ##f\in M-\{0\}## has at most ##n-1## different zeros.
  2. The space of all real-valued trigonometric polynomials on ##[0,1)## of degree at most ##n## is a Haar space of dimension ##2n+1.##
  3. Let ##n\in \mathbb{N}_0,\;p\in T_n,## and ##x\in \mathbb{T}.## Then
    $$
    \left|p'(x)\right|\leq 2\pi n\sqrt{\|p\|^2_\infty -|p(x)|^2}.
    $$
    Remark: Consider the linear differential operator ##D(p)=p'## on ##T_n.## From ##|D(\sin(2\pi nx))|=|2\pi n\cos(2\pi nx)|## we conclude that
    $$
    2\pi n \leq \|D\|=\sup_{\|p\|_\infty \leq 1}\|p'\|_\infty=\sup_{\|p\|_\infty = 1}\sup_{x\in \mathbb{T}}|p'(x)| <\infty
    $$
    because ##T_n## is finite-dimensional.



1606835746499-png-png-png-png-png.png


High Schoolers only (until 26th)



11.
(solved by @Not anonymous ) Let ##S## be a set of real numbers that is closed under multiplication (that is, if ##a## and ##b## are in ##S##, then so is ##ab##). Let ##T## and ##U## be disjoint subsets of ##S## whose union is ##S##. Given that the product of any three (not necessarily distinct) elements of ##T## is in ##T## and that the product of any three elements of ##U## is in ##U##, show that at least one of the two subsets ##T,U## is closed under multiplication.


12. (solved by @Not anonymous ) Suppose we have a necklace of ##n## beads. Each bead is labeled with an integer and the sum of all these labels is ##n-1.## Prove that we can cut the necklace to form a string whose consecutive labels ##x_1, x_2,\ldots, x_n## satisfy
$$
\sum_{i=1}^k x_i \leq k-1 \quad (k=1,\ldots,n).
$$

13. (solved by @Not anonymous ) Let ##d:=d_1d_2\ldots d_9## be a number with not necessarily distinct nine decimal digits. A number ##e:=e_1e_2\ldots e_9## is such that each of the nine digit numbers formed by replacing just one of the digits ##d_j## by the corresponding digit ##e_j## is divisible by ##7## for all ##1\leq j\leq 9.## A number ##f:=f_1f_2\ldots f_9## is formed the same way by starting with ##e,## i.e. each of the nine numbers formed by replacing a ##e_k## by ##f_k## is divisible by ##7.## Example: If ##d=20210901## then ##e_6\in \{0,7\}## since ##7\,|\,20210001## and ##7\,|\,20210701 \,.##
Show that, for each ##j,## ##d_j-f_j## is divisible by ##7.##


14. An ellipse, whose semi-axes have lengths ##a## and ##b##, rolls without slipping on the curve ##y=c\sin(x/a).## How are ##a,b,c## related, given that the ellipse completes one revolution when it traverses one period of the curve?


15. (solved by @Not anonymous ) For a partition ##\pi## of ##N:=\{1,2,\ldots\, , \,9\}##, let ##\pi(x)## be the number of elements in the part containing ##x.## Prove that for any two partitions ##\pi_1## and ##\pi_2,## there are two distinct numbers ##x## and ##y## in ##N## such that ##\pi_j(x)=\pi_j(y)## for ##j=1,2.##
 
Last edited:
  • Like
Likes Not anonymous, jbergman and berkeman

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
18,295
9,970
I was confused by number 15, but I think I understand it now.
 
  • #3
martinbn
Science Advisor
2,409
849
Small nitpicking: I don't agree that a topological group and a Lie group are the same thing.
 
  • #4
15,441
13,481
Small nitpicking: I don't agree that a topological group and a Lie group are the same thing.
Me neither. I said for example, and I hope you agree that a Lie group is indeed a topological group.
 
  • #5
martinbn
Science Advisor
2,409
849
Me neither. I said for example, and I hope you agree that a Lie group is indeed a topological group.
I see.
 
  • #7
benorin
Homework Helper
Insights Author
1,323
120
#1) "Um, I'll take what is the Bohr-Mollerup Theorem for 200 points, Alex."

I want you honest opinions here, what do you think of my new signature? Simple yet amazing truth but is it too long?
 
  • #9
15,441
13,481
#1) "Um, I'll take what is the Bohr-Mollerup Theorem for 200 points, Alex."

I want you honest opinions here, what do you think of my new signature? Simple yet amazing truth but is it too long?
I take Gauß for 500. (He defined it that way.)
 
  • #10
benorin
Homework Helper
Insights Author
1,323
120
I meant ##\ln##. I just think that ##\log ## has become common if no basis is noted.
In Computer Science ##\log := \log _2##, in algebra 2 ##\log := \log _{10}##, in Analysis ##\log := \ln ##.
 
  • #11
LCSphysicist
2020 Award
424
93
I am really puzzled about the exercise 7. I think the use of calculus can simplify a lot the demonstration of the inequalitty, but i ask myself (and of course it is more elegante if it exist) if there is a way to show it without calculus (not derivatives basically)...
 
  • #12
15,441
13,481
I am really puzzled about the exercise 7. I think the use of calculus can simplify a lot the demonstration of the inequalitty, but i ask myself (and of course it is more elegante if it exist) if there is a way to show it without calculus (not derivatives basically)...
I don't know. My solution uses derivatives. At least it is rather short.
 
  • #13
TeethWhitener
Science Advisor
Gold Member
2,076
1,555
Here's my completely non-rigorous first stab at problem 2:
Thought process: try to make the right side as small as possible and the left side as big as possible and show the inequality still holds.

(NB--I'm pretty sure we can assume WLOG that ##x_1\leq x_2\leq\dots\leq x_m##, so that's what I'll be doing)

For any given sequence ##T = (x_1,x_2,\dots,x_m)##, we have ##\min(|T_1|)=m##. Such a situation occurs, e.g., for ##T=(2,4,6,8,10)##. Here the only members of ##T_1## are the pairs where ##i=j##; that is: ##T_1=\{(x_1,x_1),(x_2,x_2),\dots,(x_m,x_m)\}##. For this case to hold, it must be true that ##\forall i \neq j, |x_i-x_j|>1##. Using the assumption above that the sequence ##T## is ordered low to high, we'll let ##|x_i-x_{i+1}|=1+\epsilon_{i}, \epsilon_{i}>0##. This means that, in this case, ##\max(|x_i-x_j|)=(m-1)(1+\max(\epsilon_i))##, because there are ##m-1## gaps between the ##m## members of the sequence, and each gap is less than or equal to ##1+\max(\epsilon_i)##.

We also have ##\max(|T_r|)=m^2##. This arises in the case where all possible pairs are present in ##T_r##. However, for the maximum case to hold, it must be the case that ##r\geq\max(|x_i-x_j|)##. Keeping with the theme of my thought process from earlier, we want to make ##r## and ##|T_1|## as small as possible. So we have ##r\geq (m-1)(1+\max(\epsilon_i))## and we choose to make ##\epsilon_i\ll 1## to get ##r## as small as possible. Now, we know that ##r## is an integer, and that ##r>m-1##, so that means ##\min(r)=m##.

If we then plug into the inequality ##\max(|T_r|)=m^2##, ##\min(r)=m##, and ##\min(|T_1|)=m##, we get
$$m^2<(2m-1)m$$
or
$$m>1$$
To finish up, when ##m=1##, we have ##|T_r|=|T_1|=1## for all ##r##, and the inequality holds trivially.

I'm not sure this constitutes a full proof, because I'm not sure if it properly excludes some intermediate values of ##|T_1|##, ##r##, and ##|T_r|## that could mess things up.
 
  • #14
15,441
13,481
Here's my completely non-rigorous first stab at problem 2:
Thought process: try to make the right side as small as possible and the left side as big as possible and show the inequality still holds.

(NB--I'm pretty sure we can assume WLOG that ##x_1\leq x_2\leq\dots\leq x_m##, so that's what I'll be doing)

For any given sequence ##T = (x_1,x_2,\dots,x_m)##, we have ##\min(|T_1|)=m##. Such a situation occurs, e.g., for ##T=(2,4,6,8,10)##. Here the only members of ##T_1## are the pairs where ##i=j##; that is: ##T_1=\{(x_1,x_1),(x_2,x_2),\dots,(x_m,x_m)\}##. For this case to hold, it must be true that ##\forall i \neq j, |x_i-x_j|>1##. Using the assumption above that the sequence ##T## is ordered low to high, we'll let ##|x_i-x_{i+1}|=1+\epsilon_{i}, \epsilon_{i}>0##. This means that, in this case, ##\max(|x_i-x_j|)=(m-1)(1+\max(\epsilon_i))##, because there are ##m-1## gaps between the ##m## members of the sequence, and each gap is less than or equal to ##1+\max(\epsilon_i)##.

We also have ##\max(|T_r|)=m^2##. This arises in the case where all possible pairs are present in ##T_r##. However, for the maximum case to hold, it must be the case that ##r\geq\max(|x_i-x_j|)##. Keeping with the theme of my thought process from earlier, we want to make ##r## and ##|T_1|## as small as possible. So we have ##r\geq (m-1)(1+\max(\epsilon_i))## and we choose to make ##\epsilon_i\ll 1## to get ##r## as small as possible. Now, we know that ##r## is an integer, and that ##r>m-1##, so that means ##\min(r)=m##.

If we then plug into the inequality ##\max(|T_r|)=m^2##, ##\min(r)=m##, and ##\min(|T_1|)=m##, we get
$$m^2<(2m-1)m$$
or
$$m>1$$
To finish up, when ##m=1##, we have ##|T_r|=|T_1|=1## for all ##r##, and the inequality holds trivially.

I'm not sure this constitutes a full proof, because I'm not sure if it properly excludes some intermediate values of ##|T_1|##, ##r##, and ##|T_r|## that could mess things up.
Looks ok to me. My solution uses induction on ##m## and intervals ##[x_i-1,x_i+1].##
 
  • Like
Likes TeethWhitener
  • #15
TeethWhitener
Science Advisor
Gold Member
2,076
1,555
For problem 9 part 1, I think you meant ##\displaystyle{\operatorname{ord}_p(n!)=\sum_{k\geq 1}\left\lfloor \dfrac{n!}{p^k}\right\rfloor}##? If so, I think I have a bead on parts 1 and 2--maybe.
##\displaystyle{\operatorname{ord}}_p(N)## counts the number of times a prime appears in the divisor list of ##\{1,2,\dots,N\}## along with the multiplicity. But let's consider a different operator ##\overline{\displaystyle{\operatorname{ord}}}_m(N)## that is the same as ##\displaystyle{\operatorname{ord}}_p(N)## except it doesn't count multiplicity, and ##m\in\mathbb{N}## doesn't have to be prime. If we look, e.g., at ##\overline{\displaystyle{\operatorname{ord}}}_2(n!)##, we add 1 every time we pass an even number in ##\{1,2,\dots,n!\}##, which means ##\overline{\displaystyle{\operatorname{ord}}}_2(n!)=\left\lfloor\frac{n!}{2}\right\rfloor##. Similarly, ##\overline{\displaystyle{\operatorname{ord}}}_3(n!)=\left\lfloor\frac{n!}{3}\right\rfloor##, ##\overline{\displaystyle{\operatorname{ord}}}_4(n!)=\left\lfloor\frac{n!}{4}\right\rfloor##, etc., and generally
$$\overline{\displaystyle{\operatorname{ord}}}_m(n!)=\left\lfloor\frac{n!}{m}\right\rfloor$$
To go from ##\overline{\displaystyle{\operatorname{ord}}}_m(n!)## to ##\displaystyle{\operatorname{ord}}_p(n!)##, we note that
$$\displaystyle{\operatorname{ord}}_p(n!)=\sum_{k\geq1}{\overline{\displaystyle{\operatorname{ord}}}_{p^k}(n!)}=\sum_{k\geq 1}{\left\lfloor \dfrac{n!}{p^k}\right\rfloor}$$
##p|\binom{2n}{n}## is really easy. Since ##p>n##, there is no ##p## in the denominator of ##\binom{2n}{n}##. But since ##p\leq 2n##, there is a ##p## in the numerator. So ##p|\binom{2n}{n}##.

##2|\binom{2n}{n}## is trickier. I think the point is to use the result from part 1, but I'm pretty sure it's easier via induction. Denoting ##n!=2^xa## and ##(2n)!=2^yb##, where ##2\nmid a## and ##2\nmid b##, we have that
$$\binom{2n}{n}=\frac{(2n)!}{n!n!}=\frac{2^yb}{2^{2x}a}$$
(This is where I start to lose rigor and question my approach.)
We can map each even number in the set ##\{1,2,\dots,n\}## to its double in the set ##\{1,2,\dots,2n\}##. We can map each multiple of 4 in the original set to its double in the larger set, and do the same for each multiple of 8, etc., or ##2^k## generally. This mapping lets us write ##y\geq (x+\left\lfloor\frac{n}{2}\right\rfloor)##. But this mapping isn’t surjective: we haven’t accounted for the factors of 2 in ##(2n)!## of the form ##4j+2##. When we do that, we get that ##y\geq (x+n)##.

To show that ##\binom{2n}{n}## is divisible by 2, we have to show that ##y>2x##, or equivalently, ##x<n##. Edit: the following is all incorrect. We do this by induction by proving: ##n!<2^na, \forall a\in\mathbb{N}##.
Base step:
##1!=1<2a, \forall a\in\mathbb{N}##
Inductive step:

Let ##n!<2^na, \forall a\in\mathbb{N}##. Then ##(n+1)!=(n+1)n!<(n+1)2^na##. Since ##(n+1)2^n<2^{n+1}##, we have ##(n+1)!<2^{n+1}a##.
Edit: crap, ignore. Found an error in problem 9 part 2. May work on it later.
 
Last edited:
  • #16
15,441
13,481
For problem 9 part 1, I think you meant ##\displaystyle{\operatorname{ord}_p(n!)=\sum_{k\geq 1}\left\lfloor \dfrac{n!}{p^k}\right\rfloor}##? If so, I think I have a bead on parts 1 and 2--maybe.
Uhm, no. Consider my example: ##10=8+2+0##. ##24!## has many, real many more divisors ##3^k.##
Edit: crap, ignore. Found an error in problem 9 part 2. May work on it later.
 
  • #17
TeethWhitener
Science Advisor
Gold Member
2,076
1,555
Uhm, no. Consider my example: ##10=8+2+0##. ##24!## has many, real many more divisors ##3^k.##
##\displaystyle{\operatorname{ord}_3(4!)=\sum_{k\geq 1}\left\lfloor \dfrac{4}{3^k}\right\rfloor}=1##? I think it has to be factorial, or else I'm really missing something.
 
  • #18
15,441
13,481
##\displaystyle{\operatorname{ord}_3(4!)=\sum_{k\geq 1}\left\lfloor \dfrac{4}{3^k}\right\rfloor}=1##? I think it has to be factorial, or else I'm really missing something.
Oops, you're right. I confused ##4!=24## with ##24!##, sorry. I will correct the OP.
 
Last edited:
  • Like
Likes TeethWhitener
  • #19
TeethWhitener
Science Advisor
Gold Member
2,076
1,555
Thanks for the clarification. I still think my problem 9 part 1 is right. I think half of problem 9 part 2 is right too, but I'll have to work on the other half (I've struck through the wrong part in post 15).
 
  • #20
15,441
13,481
Thanks for the clarification. I still think my problem 9 part 1 is right. I think half of problem 9 part 2 is right too, but I'll have to work on the other half (I've struck through the wrong part in post 15).
It would be nice if you wrote it again for ##n## instead of the faculty, and if possible with ##n## and ##p## fixed. It's actually quite easy, which is why I gathered so many parts.
 
  • #21
117
48
12. Suppose we have a necklace of beads. Each bead is labeled with an integer and the sum of all these labels is ##n-1##. Prove that we can cut the necklace to form a string whose consecutive labels ##x_1, x_2, \ldots, x_n## satisfy $$
\sum_{i=1}^k x_i \leq k-1 \, \, (k=1,...,n).
$$

Does "cut the necklace to form a string" mean any rearrangement of the individual beads is allowed, or does it only mean making at most one cut anywhere in the necklace and swapping the 2 resulting parts to form a new sequence (meaning, for e.g., (1, 2, 3, 4, 5) →(3, 4, 5, 1, 2) is allowed but not (5, 2, 1, 4, 3))? If any reordering of beads is allowed, here is my attempted solution.

Let ##A = (a_1, a_2, ..., a_n)## be the original sequence of integer-valued labels of the necklace's beads. We create a new sequence ##X = (x_1, x_2, ..., x_n)## using only values from ##A## (also, if some value is repeated in ##A##, that value will be repeated the same number of times in the new sequence too, but the order may differ, i.e. cardinality of values is retained) but arranged in ascending (more precisely, non-decreasing) order, i.e. ##x_i \leq x_{i+1} \, \forall i \in \{1,...,n-1\}##.

Define ##S_k = \sum_{i=1}^k x_k, \, k=(1,...,n)##. Since ##X## contains the same values as ##A## and with same cardinality, the sums of all values in ##X## must be the same as that for ##A##. Hence ##S_n = \sum_{i=1}^k a_k = n-1##. ∴ ##S_k## meets the condition ##S_k \leq k-1## when ##k=n##, and this becomes the initial case for induction.

Inductive step: We now show that if ##S_k \leq k-1## for ##k=j## where integer ##j > 1##, then it must be true for ##k=j-1## too.

Proof by contradiction: Suppose ##S_{j-1} > j-1##. Since ##S_j = S_{j-1} + x_j##, ##S_{j-1} > j-1## implies that ##x_j = S_j - S_{j-1} < (j-1) - (j-1) \Rightarrow x_j < 0##. (C1)

But if ##S_{j-1} > (j-1)## as assumed, it follows that ##S_{j-1}## is a positive integer (since ##j > 1##) and therefore there must be at least one positive integer in ##(x_1, ..., x_{j-1})## since ##S_{j-1}## is the sum of these values by definition. (C2)

Conditions (C1) and (C2) cause a contradiction since ##x_j < 0## and ##(x_1, ..., x_{j-1})## containing a positive value imply that the values in ##(x_1, ..., x_{j-1}, x_{j})## do not follow a non-decreasing order as required by the definition of the sequence ##X##. Since this contradiction eventually arises from the assumption that ##S_{j-1} > j-1##, it must be the case that this assumption is incorrect and we must have ##S_{j-1} \leq j-1## instead. Hence the inductive step is proved, and by the method of induction, it follows that $$
S_k = \sum_{i=1}^k x_i \leq k-1 \, \, \forall k \in \{1,..., n\}
$$. Hence, the beads can be rearranged as required.
 
  • #22
15,441
13,481
Does "cut the necklace to form a string" mean any rearrangement of the individual beads is allowed, or does it only mean making at most one cut anywhere in the necklace and swapping the 2 resulting parts to form a new sequence (meaning, for e.g., (1, 2, 3, 4, 5) →(3, 4, 5, 1, 2) is allowed but not (5, 2, 1, 4, 3))? If any reordering of beads is allowed, here is my attempted solution.
Cut means one cut, i.e. we make a string out of the circle and can so determine ##x_n##. Order and given labels remain unchanged.
 
  • #23
TeethWhitener
Science Advisor
Gold Member
2,076
1,555
Here it is rewritten without the factorial. I wasn't quite sure what you meant by n and p fixed.
##\displaystyle{\operatorname{ord}}_p(N)## counts the number of times a prime appears in the divisor list of ##\{1,2,\dots,N\}## along with the multiplicity. But let's consider a different operator ##\overline{\displaystyle{\operatorname{ord}}}_m(N)## that is the same as ##\displaystyle{\operatorname{ord}}_p(N)## except it doesn't count multiplicity, and ##m\in\mathbb{N}## doesn't have to be prime. If we look, e.g., at ##\overline{\displaystyle{\operatorname{ord}}}_2(n)##, we add 1 every time we pass an even number in ##\{1,2,\dots,n\}##, which means ##\overline{\displaystyle{\operatorname{ord}}}_2(n)=\left\lfloor\frac{n}{2}\right\rfloor##. Similarly, ##\overline{\displaystyle{\operatorname{ord}}}_3(n)=\left\lfloor\frac{n}{3}\right\rfloor##, ##\overline{\displaystyle{\operatorname{ord}}}_4(n)=\left\lfloor\frac{n}{4}\right\rfloor##, etc., and generally
$$\overline{\displaystyle{\operatorname{ord}}}_m(n)=\left\lfloor\frac{n}{m}\right\rfloor$$
To take into account multiplicity and go from ##\overline{\displaystyle{\operatorname{ord}}}_m(n)## to ##\displaystyle{\operatorname{ord}}_p(n)##, we note that
$$\displaystyle{\operatorname{ord}}_p(n)=\sum_{k\geq1}{\overline{\displaystyle{\operatorname{ord}}}_{p^k}(n)}=\sum_{k\geq 1}{\left\lfloor \dfrac{n}{p^k}\right\rfloor}$$
I also found another error in 9-2, but I haven't figured out how to complete the problem yet. I'll think on it some more.
 
  • #24
15,441
13,481
Here it is rewritten without the factorial. I wasn't quite sure what you meant by n and p fixed.
##\displaystyle{\operatorname{ord}}_p(N)## counts the number of times a prime appears in the divisor list of ##\{1,2,\dots,N\}## along with the multiplicity. But let's consider a different operator ##\overline{\displaystyle{\operatorname{ord}}}_m(N)## that is the same as ##\displaystyle{\operatorname{ord}}_p(N)## except it doesn't count multiplicity, and ##m\in\mathbb{N}## doesn't have to be prime. If we look, e.g., at ##\overline{\displaystyle{\operatorname{ord}}}_2(n)##, we add 1 every time we pass an even number in ##\{1,2,\dots,n\}##, which means ##\overline{\displaystyle{\operatorname{ord}}}_2(n)=\left\lfloor\frac{n}{2}\right\rfloor##. Similarly, ##\overline{\displaystyle{\operatorname{ord}}}_3(n)=\left\lfloor\frac{n}{3}\right\rfloor##, ##\overline{\displaystyle{\operatorname{ord}}}_4(n)=\left\lfloor\frac{n}{4}\right\rfloor##, etc., and generally
$$\overline{\displaystyle{\operatorname{ord}}}_m(n)=\left\lfloor\frac{n}{m}\right\rfloor$$
To take into account multiplicity and go from ##\overline{\displaystyle{\operatorname{ord}}}_m(n)## to ##\displaystyle{\operatorname{ord}}_p(n)##, we note that
$$\displaystyle{\operatorname{ord}}_p(n)=\sum_{k\geq1}{\overline{\displaystyle{\operatorname{ord}}}_{p^k}(n)}=\sum_{k\geq 1}{\left\lfloor \dfrac{n}{p^k}\right\rfloor}$$
I also found another error in 9-2, but I haven't figured out how to complete the problem yet. I'll think on it some more.
Yes, but you had not to define ##\overline{ord}##. The same argument at the end works with ##\left\lfloor \dfrac{n}{p}\right\rfloor\, , \,\left\lfloor \dfrac{n}{p^2}\right\rfloor\, , \,\left\lfloor \dfrac{n}{p^3}\right\rfloor,\ldots## from the start.
 
  • Like
Likes TeethWhitener
  • #25
TeethWhitener
Science Advisor
Gold Member
2,076
1,555
It occurred to me as I was falling asleep that I was going about this problem in the most roundabout way possible.
To show that ##2\,|\binom{2n}{n}##, we proceed via induction, which we should’ve just done from the beginning. We’re trying to establish that $$\frac{(2n)!}{n!n!}$$ is divisible by 2.
Base step (##n=1##):
$$\frac{2!}{1!1!}=2$$
Inductive step:
Let ##\frac{(2n)!}{n!n!}## be divisible by 2. Then consider $$\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n+2)(2n+1)}{(n+1)(n+1)}\frac{(2n)!}{n!n!}$$ We have two cases:
1) ##n+1## is odd. In this case, the denominator doesn’t acquire any additional factors of 2, and we assumed that ##\frac{(2n)!}{n!n!}## was divisible by 2, so the whole expression is divisible by 2.
2) ##n+1## is even. In this case, the denominator acquires a factor of 4 which must be canceled in the numerator for the whole expression to remain divisible by 2. We see that if ##n+1## is even, then ##n=2k+1## for some integer ##k##, and the numerator can be written as ##(4k+2)!(4k+3)(4k+4)##. Thus we have explicitly a factor of 4 in the numerator to cancel the 4 in the denominator and the inductive step goes through.
 

Related Threads on Math Challenge - September 2021

Replies
39
Views
8K
Replies
52
Views
7K
Replies
67
Views
4K
Replies
56
Views
3K
  • Last Post
5
Replies
114
Views
3K
Replies
86
Views
6K
Replies
93
Views
2K
Replies
102
Views
3K
Replies
38
Views
4K
Replies
28
Views
4K
Top