Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured Challenge Micromass' big September challenge!

  1. Sep 1, 2016 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    September, schools restart, summer ends, but a new challenge is here:

    Ranking here: https://www.physicsforums.com/threads/micromass-big-challenge-ranking.879070/

    RULES:
    1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
    2) 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.
    3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
    4) 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.

    ADVANCED CHALLENGES:
    1. Show that it is impossible to find four distinct squares as the subsequent elements in an arithmetic progression.

    2. SOLVED BY Strants Show that the ##n## roots of a real/complex polynomial of degree ##n## depend continuously on the coefficients.

    3. SOLVED BY Erland On a subset ##A## of ##\mathbb{R}## we can apply the operations of complementation ##\mathbb{R}\setminus A## and of closure ##\overline{A}##. By doing this repeatedly one can form for example ##\overline{\mathbb{R}\setminus(\mathbb{R}\setminus A)}##. How many different sets can I maximally generate from ##A## in this manner?

    4. SOLVED BY fresh_42 Find the sum of
    [tex]\frac{1}{\binom{4}{3}} - \frac{1}{\binom{6}{3}} + \frac{1}{\binom{8}{3}} - \frac{1}{\binom{10}{3}} + ...[/tex]

    5. SOLVED BY QuantumQuest Let ##a_k,b_k## be positive real numbers for ##1\leq k\leq n##. Show
    [tex]\left(\prod_{k=1}^n a_k\right)^{1/n}+\left(\prod_{k=1}^n b_k\right)^{1/n} \leq \left(\prod_{k=1}^n (a_k+b_k)\right)^{1/n}[/tex]
    When does equality hold?

    6. SOLVED BY Erland The luckless Daniel (D) is thrown into a circular arena of radius ##a## containing a lion L. Initially, the lion is at the centre O of the arena while Daniel is at the perimeter. Daniel's strategy is to run with his maximum speed ##u## around the perimater. The lion's strategy is to run with speed ##u## in such a way that it remains on the (moving) radius OD. What distance did the lion cover before he caught Daniel?

    7. Let ##X## denote the set of all bounded real-valued sequences. As was shown in last challenge, 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##.
    Show that:
    a) SOLVED BY Erland There is more than one generalized limit.
    b) SOLVED BY Erland For a given bounded real sequence ##(x_n)_n##, we have that every generalized limit ##L## assigns the same value ##l## to this sequence if and only if
    [tex]\lim_{p\rightarrow +\infty}\frac{x_n + ... + x_{n+p-1}}{p} = l[/tex]
    uniformly in ##n##.
    In other words if and only if
    [tex]\forall\varepsilon>0:~\exists p_0:~\forall p>p_0:~\forall n:~\left|\frac{x_n + ... +x_{n+p-1}}{p} - L\right|<\varepsilon[/tex]
    c) SOLVED BY Erland Find an example of a sequence that does not satisfy the condition in (b) but for which ##\frac{1}{n}\sum_{i=1}^n x_i## does converge.
    d) SOLVED BY Erland Show that we can find a generalized limit ##L## such that ##L((x_n)_n) = \lim_{n\rightarrow +\infty} \frac{1}{n}\sum_{i=1}^n x_i## if the limit exists.

    8. 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)##.

    9. SOLVED BY Erland 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.

    PREVIOUS UNSOLVED ADVANCED CHALLENGES:
    1. 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.


    CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
    1. SOLVED BY ProfuselyQuarky You meet a man on the street and he says, “I have two children and one is a son born on a Tuesday.” What is the probability that the other child is also a son?

    2. SOLVED BY Math_QED Find and prove a simple formula for the sum
    [tex]\frac{1^3}{1^4 + 4} - \frac{3^3}{3^4 +4} + \frac{5^3}{5^4 + 4} - ... + \frac{(-1)^n (2n + 1)^3}{(2n+1)^4 + 4}[/tex]

    3. SOLVED BY Biker Consider the function
    [tex]f(x)=\left\{\begin{array}{l}
    e^{-1/x}~\text{if}~x>0\\ 0~\text{if}~x\leq 0\end{array}\right.[/tex]
    a) Show that ##f## is infinitely many times differentiable on ##\mathbb{R}##.
    b) Find the Taylor series of ##f## around the point ##0##.

    4. Show that for ##0<\lambda<1## and ##\alpha,\beta\geq 0## holds
    [tex]\alpha^\lambda \beta^{1-\lambda}\leq \lambda \alpha+(1-\lambda)\beta[/tex]

    PREVIOUS CHALLENGES FOR HIGH SCHOOL AND FIRST YEAR UNIVERSITY:
    1. 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.

    2. 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.

    3. 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.

    Good luck and thanks for playing!
     
    Last edited: Sep 18, 2016
  2. jcsd
  3. Sep 1, 2016 #2

    fresh_42

    Staff: Mentor

    Under which conditions? I mean ##a_n = n \cdot d^2## has a lot of squares.
    And may I give the hint on previous HS1 that we have a leap year?
     
    Last edited: Sep 1, 2016
  4. Sep 1, 2016 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The squares have to be the subsequent elements in an arithmetic progression. So ##a##, ##a+d##, ##a+2d## and ##a+3d## are all squares.
     
  5. Sep 1, 2016 #4

    Ygggdrasil

    User Avatar
    Science Advisor

    Here, you must mean four perfect squares, or else the statement is trivially false.
     
  6. Sep 1, 2016 #5

    Math_QED

    User Avatar
    Homework Helper

    High school challenges 2)

    I used a calculator to find the partial sums S0, S1, S2, ... and I found the sequence: 1/5, -2/17, 3/37, -4/65, 5/101, ...
    So, Sn = (-1)^n*(n+1)/(4(n+1)^2+1) = (-1)^n*(n+1)/(4n^2+8n + 5)

    Now, let's proof this using mathematical induction:

    We can say that the equality holds for n = 0, since S0 = 1/5 = (-1)^0*1/5
    Now, suppose the equality holds for n = k, then it must hold for n = k +1.

    So, in particular, we have to proof that Sk+1 = (-1)^(k+1)*(k+2)/(4k^2+16k+17) using Sk =(-1)^k*(k+1)/(4k^2+8k + 5).

    Sk+1 = Sk + (-1)^(k+1)*[2(k+1)+1]^3/([2(k+1)+1]^4+4)
    = (-1)^k(k+1)/(4k^2+8k+5) + (-1)^(k+1)(2k+3)^3/((2k+3)^4+4)

    And here I saw that I would have to use a lot of trivial algebra..., so instead I used wolframalpha.com (http://www.wolframalpha.com/input/?i=((-1)^(k+1)*(2k+3)^3/((2k+3)^4+4))+((-1)^k(k+1)/(4k^2+8k+5))) and I found that this expression is equal to (-1)^(k+1)*(k+2)/(4k^2+16k+17). And this is exactly what we wanted to show. So QED.
     
  7. Sep 1, 2016 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    For number 1 on the high school challenges, there are some debatable issues, which (in my view) are removed by asking direct questions of the man:

    Qu: How many children do you have?
    Ans: 2

    Qu: Do you have a son born on a Tuesday?
    Ans: yes
     
  8. Sep 1, 2016 #7

    Math_QED

    User Avatar
    Homework Helper

    Highschool challenges 3b)

    Not too sure about this one.

    It is well known that e^x = ∑x^n/n!
    Substituting -1/x yields: e^(-1/x) = ∑ (-1/x)^n/n! = ∑ (-1)^n/(x^n*n!) for x > 0

    So, we have,
    [tex]f(x)=\left\{\begin{array}{l}
    ∑(-1)^n/(x^n*n!)~\text{if}~x>0\\ 0~\text{if}~x\leq 0\end{array}\right.[/tex]
     
  9. Sep 1, 2016 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    A Taylor series can't have negative powers of ##x##. What you have computed is a Laurent series, and then only of the positive part.
     
  10. Sep 1, 2016 #9

    Erland

    User Avatar
    Science Advisor

    About Advanced Problem 2:

    I once asked this very question at Usenet, and got an answer, so I know how to prove it. Is it still OK for me give a proof here?

    Anyway, I think you should specify exactly what you mean by "the ... roots ... depend continuously on the coefficients". Continuously according to which topological spaces?

    There might be some alternatives for this, but the proof I received probably can be adjusted to fit any of them.
     
  11. Sep 1, 2016 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    No, sorry.
     
  12. Sep 1, 2016 #11

    Erland

    User Avatar
    Science Advisor

    About Advanced Problem 3: It would of course depend upon ##A##: If ##A=\varnothing## or ##A=\mathbb R##, then the answer is ##2##: ##\varnothing## and ##\mathbb R##. If ##A## is a closed or open bounded interval, then the answer is ##4##: ##A## itself, its interior or closure, and the complements of these two sets.

    But I suppose you mean the maximum taken over all possible subsets ##A## of ##\mathbb R##...?
     
  13. Sep 1, 2016 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I worked a bit on problem 1, and while many individual primes work well, I'm missing some generalization, or the approach does not work at all. I thought I share my work so far, feel free to use it or show me how pointless it was.
    All variables in this post are non-negative integers.
    Start with the observation that, mod 2n, all possible remainders of squares (all quadratic residues) can be expressed as 4k(8m+1). This is a well-known result but you can also find it at Wikipedia.
    In particular, mod 4, the only possible remainders are 0 and 1.

    Assume we have such a progression, consisting of the four numbers X, X+Q, X+2Q and X+3Q. Their remainders mod 2n also form an arithmetric progression, possibly wrapping over (e. g. 10, 13, 0, 3 if we consider them mod 16). If Q is not divisible by 4, then (at least) one remainder mod 4 has to be 2 or 3, which is impossible. Therefore, Q has to be divisible by 4.

    Consider the case that X is even. As X is a perfect square, it is also divisible by 4, which means all four numbers are. We can divide all numbers by 4 to find a smaller arithmetric progression with four squares. We can continue that until the sequence starts with an odd number. If there is such a progression, there is also one with odd X, consider only this case.

    As all four numbers are odd, their remainders mod 2n are also odd. Therefore they all can be written as (8m+1). It also implies Q is a multiple of 8. That's as far as powers of 2 go within that framework.


    The same argument as with divisibility by 4 can also be made with 3: the only quadratic residues are 0 and 1 (does not follow from previous things, but it is trivial to check), the only "arithmetic progressions" in there are "always 0" and "always 1". Therefore Q has to be divisible by 3 as well. If X is divisible by 3, then both X and X+Q are divisible by 9, and we can divide the whole progression by 9 until the four numbers have a remainder of 1 mod 3.

    mod 5: residues 0, 1, 4, no non-trivial progression possible, Q has to be divisible by 5, it is sufficient to consider X not divisible by 5.
    mod 7: 0, 1, 2, 4, Q has to be divisible by 7, ...
    mod 11: 0, 1, 3, 4, 5, 9, Q has to be divisible by 11, ...
    mod 13: 0, 1, 3, 4, 9, 10, 12, Q has to be divisible by 13, ...
    mod 17: 0, 1, 2, 4, 8, 9, 13, 15, 16, here there are progressions possible (15,16,0,1 and 13,15,0,2 and 9,13,0,4,8) so the argument does not work.
     
  14. Sep 1, 2016 #13

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes.
     
  15. Sep 1, 2016 #14

    Charles Link

    User Avatar
    Homework Helper

    #6 with the lion is interesting and I think also not real difficult, but I previously worked a very similar problem so that I am ineligible for that one. ... editing... A little effort in trying to re-work the problem proved unsuccessful, and then I recalled completely the original similar problem, and there are distinct differences that make @micromass version much more difficult. ## \\ ## The original problem was that Capt. Kirk was trapped in the middle of a circular lake by a Romulin who was on shore and could run 4x as fast as Capt. Kirk could swim. The question was, could Capt. Kirk get out of the lake safely? ## \\ ## The solution I worked out was that Capt. Kirk used a more intelligent approach then the lion, and as long as he could, (until his radial location was ## r=(1/4)R ##), he swam in such a manner (and not directly away from the Romulin), so as to keep the ## d \theta /dt ## the same. That way, the Romulin was as far away as possible at the ## r=(1/4)R ## point. He therefore needed to go ## (3/4)R ## before the Romulin went ## \pi R ## and since ## \pi >3 ## he successfully got out. The path inside of ## r=(1/4)R ## as I recall, (I solved this a few years ago) was a simple one. (I believe it was semi-circle, but it wasn't even necessary to solve for the precise path.) ## \\ ## In any case, the lion uses a much less intelligent and mathematically more difficult approach of running directly at the man. I do plan on trying to solve this one, but it appears to be quite difficult...
     
    Last edited: Sep 1, 2016
  16. Sep 1, 2016 #15

    fresh_42

    Staff: Mentor

    This is what I have for AC 4.

    Let ##S## denote the sum and ##a_k = \binom{2k}{3}^{-1} - \binom{2k+2}{3}^{-1}## so ##S = a_2 + a_4 + a_6 + \dots##

    Then we get

    ##a_k = \frac{3! \; (2k-3)!}{(2k)!} - \frac{3! \; (2k-1)!}{(2k+2)!} \\
    = \frac{6}{2k} \Big{(} \frac{1}{(2k-1)(2k-2)} - \frac{1}{(2k+2)(2k+1)} \Big{)} \\
    = \frac{6}{2k} \cdot \frac{(4k^2+6k+2)-(4k^2-6k+2)}{(2k-2)(2k-1)(2k+1)(2k+2)} \\
    = \frac{36}{(2k-2)(2k+2)(2k+1)(2k-1)} \\
    =\frac{9}{(k^2-1)(4k^2-1)} \\
    = \frac{-12}{4k^2-1} + \frac{3}{k^2-1} \\
    = \frac{6}{2k+1} - \frac{6}{2k-1} - \frac{3}{2} \cdot \frac{1}{k+1} + \frac{3}{2} \cdot \frac{1}{k-1} \\##

    With ##k=2n \; (n \geq 1)## we have

    ##S= \sum_{n=1}^{\infty}a_n = \sum_{n=1}^{\infty}\Big{(} \Big{(} \frac{6}{4n+1} - \frac{6}{4n-1}\Big{)} - \Big{(} \frac{3}{2} \cdot \frac{1}{2n+1} - \frac{3}{2} \cdot \frac{1}{2n-1}\Big{)}\Big{)} \\
    \overset{(*)}= 6 \cdot (\frac{\pi}{4} - 1) - \frac{3}{2} \cdot (- \frac{1}{2\cdot 1 - 1}) = \frac{1}{2} (3\pi - 9) ≈ 0.212388980_4##

    where I used for (*) Leibniz' (1682) formula for ##\frac{\pi}{4}## as also used in a previous challenge and the telescope property for the latter (and hopefully avoided typos).
     
    Last edited: Sep 1, 2016
  17. Sep 2, 2016 #16

    jbriggs444

    User Avatar
    Science Advisor

    For problem 1, one assumes that you wish to disallow the trivial arithmetic progression: 0, 0, 0, 0 ...
     
  18. Sep 2, 2016 #17

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I don't know if the lion's plan is less intelligent. After all the mean difference is that in your scenario, the prey starts in the middle. While in my scenario, he starts at the edge. So it's a it different.
     
  19. Sep 2, 2016 #18

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Fixed it, thanks!
     
  20. Sep 2, 2016 #19

    Charles Link

    User Avatar
    Homework Helper

    If you try working the Capt. Kirk problem, (and a urge the readers to do this with a constant ## d \theta/dt ## until he gets to the ## r=(1/4)R ## point), I think they will find it to be quite simple. Meanwhile, the lion problem turns out to be a much more difficult differential equation containing both the coordinates of the man and the coordinates of the lion. I don't know whether I will be able to obtain a solution.
     
  21. Sep 2, 2016 #20

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Assuming you have the correct equation, it does have a nice closed form solution.
    If you do solve it, feel free to post its solution. It doesn't matter that you've seen a similar problem before, as long as this one is new (which it apparently is).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Micromass' big September challenge!
Loading...