- #1
- 22,183
- 3,321
August is already well underway, so time for some nice challenges! This thread contains both challenges for high schoolers and college freshmen, and for more advanced people. Also some previously unsolved challenges are omitted.
Ranking here: https://www.physicsforums.com/threads/micromass-big-challenge-ranking.879070/
RULES:
1. a) SOLVED BY stevendaryl, disregardthat, mfb Prove there is a unique function ##f:\mathbb{R}\rightarrow \mathbb{R}## such that ##f(1) = 2## and such that for all ##x,y\in \mathbb{R}## holds ##f(x+y) = f(x)f(y)## and such that ##f## is continuous in at least one point.
b) SOLVED BY Erland Prove that uniqueness fails if we drop the continuity condition.
2. SOLVED BY mfb In probability theory, a scale estimator is a function ##s## that takes in ##n## data points and provides an estimate for the variability of the data. The standard deviation is a famous example of a scale estimator. Let ##s## be a scale estimator on ##n## given data points ##Y_1##, ..., ##Y_n##. We say that the explosion value of ##s## is ##x\%## if we can replace ##x\%## of the data points by arbitrary chosen values in order to make the scale estimate arbitrarily large, while we cannot do the same by replacing less than ##x\%##..
As an example, when computing the standard deviation of ##n## data points ##Y_1##, ..., ##Y_n##, we can replace the ##n##th data point by ##c##. By taking ##c\rightarrow +\infty##, we see clearly that the standard deviation of ##Y_1##, ..., ##Y_{n-1}## and ##c## also diverges to ##+\infty##. So the standard deviation on ##n## data points explodes already by replacing ##1## data point: the explosion value is ##100/n \%##.
Consider the following scale estimator:
[tex]s(Y_1,...,Y_n) = \text{median}\{|x_i - x_j|~\vert~1\leq i,j\leq n\}[/tex]
Compute the explosion value.
3. SOLVED BY Krylov Notice that the set of ##n\times n##-matrices is linearly isomorphic to ##\mathbb{R}^{n^2}##. By using this isomorphism, we can talk about distances in the set of ##n\times n##-matrices, that is: ##M_{n,n}(\mathbb{R})## is a metric space. Show that the set of all nilpotent matrices (i.e. matrices ##N## such that ##N^k = 0## for some ##k\in \mathbb{N}##) is closed in this metric space.
4. SOLVED BY Erland Let ##X## denote the set of all bounded real-valued sequences. Prove that a generalized limit exists for any such sequence. A generalized limit is any function function ##L:X\rightarrow \mathbb{R}## such that
1) ##L((x_n + y_n)_n) = L((x_n)_n) + L((y_n)_n)##
2) ##L((\alpha x_n)_n) = \alpha L((x_n)_n)##
3) ##\liminf_n x_n \leq L((x_n)_n)\leq \limsup_n x_n##
4) If ##x_n\geq 0## for all ##n##, then ##L((x_n)_n)\geq 0##.
5) If ##y_n = x_{n+1}##, then ##L((x_n)_n) = L((y_n)_n)##
6) If ##x_n\rightarrow x##, then ##L((x_n)_n) = x##.
5. SOLVED BY Krylov Let ##f:[0,+\infty)\rightarrow [0,+\infty)## be increasing and satify ##f(0)=0## and ##f(x)>0## for all ##x>0##. Let ##(X,d)## be a metric space. Show that if ##f''\leq 0##, then ##(X,f\circ d)## also is a metric space.
6. SOLVED BY Krylov, disregardthat Let ##(\Omega,\mathcal{F},\mathbb{P})## be a probability space. That is: ##\Omega## is a set, ##\mathcal{B}## is a ##\sigma##-algebra on ##\Omega##, and ##\mathbb{P}:\mathcal{B}\rightarrow [0,1]## satisfies that ##\mathbb{P}(\Omega) = 1## and ##\mathbb{P}\left(\bigcup_{k=1}^{+\infty} A_k\right) = \sum_{k=1}^{+\infty} \mathbb{P}(A_k)## whenever ##A_i\cap A_j =\emptyset## for all ##i\neq j##.
This probability space is called nonatomic if ##\mathbb{P}(A)>0## implies that there is a ##B\subseteq A## such that ##0<\mathbb{P}(B)<\mathbb{P}(A)##.
Prove that in a nonatomic probability space, for each ##\mathbb{P}(A)>0## and for each ##p_1,p_2,...\geq 0## with ##\sum p_k = 1##, then ##A## can be decomposed in a disjoint union ##A = \bigcup A_k## such that ##\mathbb{P}(A_n) = p_n\mathbb{P}(A)##.
7. SOLVED BY TeethWhitener Let ##p## be a prime number. Let ##r## and ##s## be natural numbers. We write ##r = \sum r_k p^k## and ##s = \sum s_k p^k## the base ##p## representations of ##r## and ##s##. Show
[tex]\binom{r}{s} = \prod_{k=0}^{+\infty} \binom{r_k}{s_k}~~\text{(mod p)}[/tex]
Note that the above product is a finite product.
8. Take a wire stretched between two posts, and have a large number of birds land on it at random. Take a bucket of yellow paint, and for each bird, paint the interval from it to its closest neighbour. The question is: what proportion of the wire will be painted. More strictly: as the number of birds goes to infinity, what is the limit of the expected value of the proportion of painted wire, assuming a uniform probability distribution of birds on the wire.
9. SOLVED BY Krylov Let ##(X,d)## and ##(Y,d')## be metric spaces with ##X## compact. Let ##f:X\rightarrow Y## and ##g:Y\rightarrow X## be isometries (= distance preserving functions). Prove that ##f## and ##g## are bijections.
PREVIOUS UNSOLVED ADVANCED CHALLENGES:
1. SOLVED BY fresh_42 Let ##G## be a finite group and let ##p## be the smallest prime number which divide ##|G|##. Prove that every subgroup ##H## of ##G## such that ##p|H| = |G|## is normal. Use this to find all groups of order ##pq## with ##p## and ##q## (not necessarily distinct) primes.
Hint: consider a homomorphism ##G\rightarrow \text{Sym}(G/H)##.
2. In a village of ##2016## people, prove that the probability that exactly ##m## days (ignore leap years) are not a birthday can be approximated by a Poisson distribution.
Hint: Let ##p(m,r,n)## be the probability that putting ##r## balls in ##n## boxes leaves ##m## boxes empty. Show that if we put ##\lambda = ne^{r/n}##, then if ##n\rightarrow +\infty## and ##r\rightarrow \infty## in such a way that ##\lambda## remains fixed, prove that ##p(m,r,n)- e^{-\lambda}\frac{\lambda^m}{m!}\rightarrow 0##.
CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. SOLVED BY Math_QED Let ##a## be a fixed number in ##[0,1]##. Let ##x_n = n(1 - a + ae^{1/n})^n - ne^a##. Find ##\lim_{n\rightarrow +\infty} x_n##.
2. SOLVED BY Biker Find all places on Earth so that can you walk one mile north, one mile west and one mile south then end up back where you started?
3. On a table are ##2016## bells standing in a sequence. At every turn you have to pick ##2## bells, ring them and then exchange their place.
For example, if there were only ##4## bells, they stand initially as ##A-B-C-D##. In turn ##1##, you pick bells ##A## and ##D##, ring them and exchange them to get ##D-B-C-A##. In turn ##2##, you pick bells ##D## and ##B##, ring them and exchange them to get ##B-D-C-A##.
The goal of the bell ringer is to take ##n## turns after which the sequence of bells is reversed. For example an easy way to reverse the order in ##A-B-C-D## is first to ring ##A## and ##D## to get ##D-B-C-A## and then to ring ##B## and ##C## to get ##D-C-B-A##. We have reversed the bells in ##2## turns.
Show that it is impossible to reverse ##2016## bells in an odd number of turns.
4. SOLVED BY Math_QED Prove that there exists ##2016## consecutive natural numbers, none of which is prime.
5. Find all ##10##-digit numbers such that
a) each digit ##\{0,1,2,3,4,5,6,7,8,9\}## is used exactly once
b) the first ##n## digits form a number divisible by ##n## (##n\in \{1,2,3,4,5,6,7,8,9,10\}##).
For example, if my number would be ##1234567890##, then ##1## must be divisble by ##1##, ##12## must be divisible by ##2##, ##123## must be divisible by ##3## and so on.
6. Find all 10-digit numbers where the first digit is how many zeros are in the number, the second digit is how many 1s are in the number etc. until the tenth digit which is how many 9s are in the number.
PREVIOUS CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. Let ##p\neq 0## be a real number. Let ##x_1,...,x_n## be positive real numbers, we define the ##p##-mean as
[tex]M_p(x_1,...,x_n) = \sqrt[p]{\frac{1}{n}\sum_{i=1}^n x_i^p}[/tex]
Note that ##M_1(x_1,...,x_n)## is the usual mean.
Prove that for all ##p,q\in \mathbb{R}\cup \{- \infty,+\infty\}## has that ##p\leq q## implies ##M_p(x_1,...,x_n)\leq M_q(x_1,...,x_n)##.
2. Take rational numbers ##\frac{a}{c}<\frac{b}{d}## with ##a,b,c,d\in \mathbb{N}##.
Prove that if ##bc - ad = 1##, then ##\frac{a+b}{c+d}## is the simplest fraction in ##\left(\frac{a}{c},\frac{b}{d}\right)## in the sense of having the smallest denominator.
3. SOLVED BY Pro7 Find
[tex]\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + 4\sqrt{1 + ...}}}}[/tex]
4. SOLVED BY Biker A donkey is tied with a ##50m## long rope. The rope is tied to the corner of a ##20m## by ##10m## barn. What is the total area that the donkey is capable of grazing?
Here is a sketch:
Ranking here: https://www.physicsforums.com/threads/micromass-big-challenge-ranking.879070/
RULES:
- In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
- It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
- If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
- You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
1. a) SOLVED BY stevendaryl, disregardthat, mfb Prove there is a unique function ##f:\mathbb{R}\rightarrow \mathbb{R}## such that ##f(1) = 2## and such that for all ##x,y\in \mathbb{R}## holds ##f(x+y) = f(x)f(y)## and such that ##f## is continuous in at least one point.
b) SOLVED BY Erland Prove that uniqueness fails if we drop the continuity condition.
2. SOLVED BY mfb In probability theory, a scale estimator is a function ##s## that takes in ##n## data points and provides an estimate for the variability of the data. The standard deviation is a famous example of a scale estimator. Let ##s## be a scale estimator on ##n## given data points ##Y_1##, ..., ##Y_n##. We say that the explosion value of ##s## is ##x\%## if we can replace ##x\%## of the data points by arbitrary chosen values in order to make the scale estimate arbitrarily large, while we cannot do the same by replacing less than ##x\%##..
As an example, when computing the standard deviation of ##n## data points ##Y_1##, ..., ##Y_n##, we can replace the ##n##th data point by ##c##. By taking ##c\rightarrow +\infty##, we see clearly that the standard deviation of ##Y_1##, ..., ##Y_{n-1}## and ##c## also diverges to ##+\infty##. So the standard deviation on ##n## data points explodes already by replacing ##1## data point: the explosion value is ##100/n \%##.
Consider the following scale estimator:
[tex]s(Y_1,...,Y_n) = \text{median}\{|x_i - x_j|~\vert~1\leq i,j\leq n\}[/tex]
Compute the explosion value.
3. SOLVED BY Krylov Notice that the set of ##n\times n##-matrices is linearly isomorphic to ##\mathbb{R}^{n^2}##. By using this isomorphism, we can talk about distances in the set of ##n\times n##-matrices, that is: ##M_{n,n}(\mathbb{R})## is a metric space. Show that the set of all nilpotent matrices (i.e. matrices ##N## such that ##N^k = 0## for some ##k\in \mathbb{N}##) is closed in this metric space.
4. SOLVED BY Erland Let ##X## denote the set of all bounded real-valued sequences. Prove that a generalized limit exists for any such sequence. A generalized limit is any function function ##L:X\rightarrow \mathbb{R}## such that
1) ##L((x_n + y_n)_n) = L((x_n)_n) + L((y_n)_n)##
2) ##L((\alpha x_n)_n) = \alpha L((x_n)_n)##
3) ##\liminf_n x_n \leq L((x_n)_n)\leq \limsup_n x_n##
4) If ##x_n\geq 0## for all ##n##, then ##L((x_n)_n)\geq 0##.
5) If ##y_n = x_{n+1}##, then ##L((x_n)_n) = L((y_n)_n)##
6) If ##x_n\rightarrow x##, then ##L((x_n)_n) = x##.
5. SOLVED BY Krylov Let ##f:[0,+\infty)\rightarrow [0,+\infty)## be increasing and satify ##f(0)=0## and ##f(x)>0## for all ##x>0##. Let ##(X,d)## be a metric space. Show that if ##f''\leq 0##, then ##(X,f\circ d)## also is a metric space.
6. SOLVED BY Krylov, disregardthat Let ##(\Omega,\mathcal{F},\mathbb{P})## be a probability space. That is: ##\Omega## is a set, ##\mathcal{B}## is a ##\sigma##-algebra on ##\Omega##, and ##\mathbb{P}:\mathcal{B}\rightarrow [0,1]## satisfies that ##\mathbb{P}(\Omega) = 1## and ##\mathbb{P}\left(\bigcup_{k=1}^{+\infty} A_k\right) = \sum_{k=1}^{+\infty} \mathbb{P}(A_k)## whenever ##A_i\cap A_j =\emptyset## for all ##i\neq j##.
This probability space is called nonatomic if ##\mathbb{P}(A)>0## implies that there is a ##B\subseteq A## such that ##0<\mathbb{P}(B)<\mathbb{P}(A)##.
Prove that in a nonatomic probability space, for each ##\mathbb{P}(A)>0## and for each ##p_1,p_2,...\geq 0## with ##\sum p_k = 1##, then ##A## can be decomposed in a disjoint union ##A = \bigcup A_k## such that ##\mathbb{P}(A_n) = p_n\mathbb{P}(A)##.
7. SOLVED BY TeethWhitener Let ##p## be a prime number. Let ##r## and ##s## be natural numbers. We write ##r = \sum r_k p^k## and ##s = \sum s_k p^k## the base ##p## representations of ##r## and ##s##. Show
[tex]\binom{r}{s} = \prod_{k=0}^{+\infty} \binom{r_k}{s_k}~~\text{(mod p)}[/tex]
Note that the above product is a finite product.
8. Take a wire stretched between two posts, and have a large number of birds land on it at random. Take a bucket of yellow paint, and for each bird, paint the interval from it to its closest neighbour. The question is: what proportion of the wire will be painted. More strictly: as the number of birds goes to infinity, what is the limit of the expected value of the proportion of painted wire, assuming a uniform probability distribution of birds on the wire.
9. SOLVED BY Krylov Let ##(X,d)## and ##(Y,d')## be metric spaces with ##X## compact. Let ##f:X\rightarrow Y## and ##g:Y\rightarrow X## be isometries (= distance preserving functions). Prove that ##f## and ##g## are bijections.
PREVIOUS UNSOLVED ADVANCED CHALLENGES:
1. SOLVED BY fresh_42 Let ##G## be a finite group and let ##p## be the smallest prime number which divide ##|G|##. Prove that every subgroup ##H## of ##G## such that ##p|H| = |G|## is normal. Use this to find all groups of order ##pq## with ##p## and ##q## (not necessarily distinct) primes.
Hint: consider a homomorphism ##G\rightarrow \text{Sym}(G/H)##.
2. In a village of ##2016## people, prove that the probability that exactly ##m## days (ignore leap years) are not a birthday can be approximated by a Poisson distribution.
Hint: Let ##p(m,r,n)## be the probability that putting ##r## balls in ##n## boxes leaves ##m## boxes empty. Show that if we put ##\lambda = ne^{r/n}##, then if ##n\rightarrow +\infty## and ##r\rightarrow \infty## in such a way that ##\lambda## remains fixed, prove that ##p(m,r,n)- e^{-\lambda}\frac{\lambda^m}{m!}\rightarrow 0##.
CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. SOLVED BY Math_QED Let ##a## be a fixed number in ##[0,1]##. Let ##x_n = n(1 - a + ae^{1/n})^n - ne^a##. Find ##\lim_{n\rightarrow +\infty} x_n##.
2. SOLVED BY Biker Find all places on Earth so that can you walk one mile north, one mile west and one mile south then end up back where you started?
3. On a table are ##2016## bells standing in a sequence. At every turn you have to pick ##2## bells, ring them and then exchange their place.
For example, if there were only ##4## bells, they stand initially as ##A-B-C-D##. In turn ##1##, you pick bells ##A## and ##D##, ring them and exchange them to get ##D-B-C-A##. In turn ##2##, you pick bells ##D## and ##B##, ring them and exchange them to get ##B-D-C-A##.
The goal of the bell ringer is to take ##n## turns after which the sequence of bells is reversed. For example an easy way to reverse the order in ##A-B-C-D## is first to ring ##A## and ##D## to get ##D-B-C-A## and then to ring ##B## and ##C## to get ##D-C-B-A##. We have reversed the bells in ##2## turns.
Show that it is impossible to reverse ##2016## bells in an odd number of turns.
4. SOLVED BY Math_QED Prove that there exists ##2016## consecutive natural numbers, none of which is prime.
5. Find all ##10##-digit numbers such that
a) each digit ##\{0,1,2,3,4,5,6,7,8,9\}## is used exactly once
b) the first ##n## digits form a number divisible by ##n## (##n\in \{1,2,3,4,5,6,7,8,9,10\}##).
For example, if my number would be ##1234567890##, then ##1## must be divisble by ##1##, ##12## must be divisible by ##2##, ##123## must be divisible by ##3## and so on.
6. Find all 10-digit numbers where the first digit is how many zeros are in the number, the second digit is how many 1s are in the number etc. until the tenth digit which is how many 9s are in the number.
PREVIOUS CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
1. Let ##p\neq 0## be a real number. Let ##x_1,...,x_n## be positive real numbers, we define the ##p##-mean as
[tex]M_p(x_1,...,x_n) = \sqrt[p]{\frac{1}{n}\sum_{i=1}^n x_i^p}[/tex]
Note that ##M_1(x_1,...,x_n)## is the usual mean.
Prove that for all ##p,q\in \mathbb{R}\cup \{- \infty,+\infty\}## has that ##p\leq q## implies ##M_p(x_1,...,x_n)\leq M_q(x_1,...,x_n)##.
2. Take rational numbers ##\frac{a}{c}<\frac{b}{d}## with ##a,b,c,d\in \mathbb{N}##.
Prove that if ##bc - ad = 1##, then ##\frac{a+b}{c+d}## is the simplest fraction in ##\left(\frac{a}{c},\frac{b}{d}\right)## in the sense of having the smallest denominator.
3. SOLVED BY Pro7 Find
[tex]\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + 4\sqrt{1 + ...}}}}[/tex]
4. SOLVED BY Biker A donkey is tied with a ##50m## long rope. The rope is tied to the corner of a ##20m## by ##10m## barn. What is the total area that the donkey is capable of grazing?
Here is a sketch:
Last edited: