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 Basic Math Challenge - September 2018

  1. Sep 1, 2018 #1

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    Summer is coming and brings a new basic math challenge! Enjoy! For more advanced problems you can check our other intermediate level math challenge thread!

    RULES:

    a) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
    b) 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.
    c) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
    d) 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.
    e) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted.

    We have quite a couple of old problems, which are still open. As we think that most of them aren't too difficult, we want to give them another try. One reason is, we want to find out why they have been untouched. So in case you need a hint or two in order to tackle them, don't hesitate to ask! We've also some new questions. Our special thanks go to @Infrared who contributed some new questions.

    QUESTIONS:

    1. Let ##f## be a differentiable function in ##\mathbb{R}##. If ##f'## is invertible and ##(f')^{-1}## is differentiable in ##\mathbb{R}##, show that ##[I_A (f')^{-1} - f \circ [(f')^{-1} ]]' = (f')^{-1}## where ##I_A## with ##I_A(x) = x## is the identity function ##I_A : A \to A##

    Hint: Let ##y = f'(x)## then ##(f')^{-1}(y) = x##. By differentiating, we can get to a useful result including the second derivative of ##f(x)##. Next, we can utilize ##[f\circ (f')^{-1}]'## and incorporate the identity function ##I_A##.

    2. (solved by @nuuskur ) Given a nonnegative, monotone decreasing sequence ##(a_n)_{n \in \mathbb{N}}\subseteq \mathbb{R}\,.## Prove that ##\sum_{n \in \mathbb{N}}a_n## converges if and only if ##\sum_{n \in \mathbb{N}_0}2^na_{2^n}## converges.

    3. Let's consider complex functions in one variable and especially the involutions
    $$
    \mathcal{I}=\{\, z\stackrel{p}{\mapsto} z\; , \; z\stackrel{q}{\mapsto} -z\; , \;z\stackrel{r}{\mapsto} z^{-1}\; , \;z\stackrel{s}{\mapsto}-z^{-1}\,\}
    $$
    We also consider the two functions $$\mathcal{J}=\{\,z\stackrel{u}{\longmapsto}\frac{1}{2}(-1+i \sqrt{3})z\; , \;z\stackrel{v}{\longmapsto}-\frac{1}{2}(1+i \sqrt{3})z\,\}$$
    and the set ##\mathcal{F}## of functions which we get, if we combine any of them: ##\mathcal{F}=\langle\mathcal{I},\mathcal{J} \rangle## by consecutive applications. We now define for ##\mathcal{K}\in \{\mathcal{I},\mathcal{J}\}## a relation on ##\mathcal{F}## by
    $$
    f(z) \sim_\mathcal{K} g(z)\, :\Longleftrightarrow \, (\forall \,h_1\in \mathcal{K})\,(\exists\,h_2\in \mathcal{K})\,: f(h_1(z))=g(h_2(z))
    $$
    • Show that ##\sim_\mathcal{K}## defines an equivalence relation.
    • Show that ##\mathcal{F}/\sim_\mathcal{I}## admits a group structure on its equivalence classes by consecutive application.
    • Show that ##\mathcal{F}/\sim_\mathcal{J}## does not admit a group structure on its equivalence classes by consecutive applications.
    Hint: Determine the groups ##F=\langle \mathcal{F}\rangle\, , \,I=\langle \mathcal{I} \rangle\, , \,J=\langle \mathcal{J} \rangle## and what distinguishes ##F/I## from ##F/J\,.##

    4. There are ##r## sports 'enthusiasts' in a certain city. They are forming various teams to bet on upcoming events. A pair of people dominated last year, so there are new rules in place this year. The peculiar rules are:
    • each team must have an odd number of members
    • each and every 2 teams must have an even number of members in common.
    For avoidance of doubt, nothing in the rules say a given player can only be on one team.
    With these rules in place, is it possible to form more than ##r## teams?

    Hint: Model these rules with matrix multiplication and select a suitable field.

    5. We define an equivalence relation on the topological two-dimensional unit sphere ##\mathbb{S}^2\subseteq \mathbb{R}^3## by ##x \sim y \Longleftrightarrow x \in \{\,\pm y\,\}## and the projection ##q\, : \,\mathbb{S}^2 \longrightarrow \mathbb{S}^2/\sim \,.## Furthermore we consider the homeomorphism ##\tau \, : \,\mathbb{S}^2 \longrightarrow \mathbb{S}^2## defined by ##\tau (x)=-x\,.## Note that for ##A \subseteq \mathbb{S}^2## we have ##q^{-1}(q(A))= A \cup \tau(A)\,.## Show that
    • ##q## is open and closed.
    • ##\mathbb{S}^2/\sim ## is compact, i.e. Hausdorff and covering compact.
    • Let ##U_x=\{\,y\in \mathbb{S}^2\,:\,||y-x||<1\,\}## be an open neighborhood of ##x \in \mathbb{S}^2\,.## Show that ##U_x \cap U_{-x} = \emptyset \; , \;U_{-x}=\tau(U_x)\; , \;q(U_x)=q(U_{-x})## and ##q|_{U_{x}}## is injective. Conclude that ##q## is a covering.
    Hint: For (a) consider ##O\cup \tau(O)## for an open set ##O\,.## For (b) use part (a) and that ##\mathbb{S}^2## is Hausdorff. For (c) a covering map is a local homeomorphism, so we need continuity, openess, closedness and bijectivity. Again use the previous parts.

    6.
    (solved by @PeroK ) Two Tennis players have a match that consists of just one set. Larry will serve in the first game and the first player to get ##12## games wins the match (whether ahead by only ##1## game or ##2+## games - either way wins the match).
    Larry, and Moe have chances of ##0.75## and ##0.70##, respectively, of winning when they serve. Since Moe doesn't serve in the very first game, he gets to choose: should the servers alternate game by game or should the winner of a given game serve in the next game. What's the best choice for Moe?

    7. How many times a day is it impossible to determine what time it is, if you have a clock with same length (identical looking) hour and minutes hands, supposing that we always know if it's morning or evening (i.e. we know whether it's am or pm).

    8. For the class of ##n \times n## matrices whose entries, (if flattened and sorted) would be ##1, 2, 3, ..., n^2 -1 ,n^2## prove that there always exists two neighboring entries (in same row or same column) that must differ by at least ##n##.

    9. (solved by @Math_QED ) A fixed point of a function ##f:X\to X## is an element ##x\in X## satisfying ##f(x)=x##. Let ##f:\mathbb{R}\to\mathbb{R}## be a continuous function with no fixed points. Show that ##f\circ f## also has no fixed points.

    10. (solved by @nuuskur ) Let ##f:\mathbb{R}\to\mathbb{R}## be differentiable and let ##a,b## be real numbers with ##a<b##. Show that if ##f'(a)<m<f'(b)##, then there exists some ##c\in (a,b)## such that ##f'(c)=m.##
     
    Last edited: Oct 8, 2018
  2. jcsd
  3. Sep 2, 2018 #2
    I will solve Problem 7
    I combine the hours and minutes to form a time that ranges from 0 to 1 over 12 hours: t = (h + m/60)/12 for h hours and m minutes. I will also set the range of hour-hand and minute-hand positions to be 0 to 1. Thus,
    • Hour hand: position a = t
    • Minute hand: position a = 12 t
    I will generalize the minute hand's position to use an arbitrary positive integer R: a = R t.

    If same-sized hour and minute hands give two valid times, then the hour hand for time t1 is the minute hand for time t2, and vice versa. Thus
    • ## t_1 = R t_2 \mod 1##
    • ## R t_1 = t_2 \mod 1##
    Modulo-1 arithmetic is being able to add an arbitrary integer:
    • ## t_1 = R t_2 + n_1##
    • ## R t_1 = t_2 + n_2##
    This is a system of linear equations in the two times, and it has the solution
    • ## t_1 = (R n_2 - n_1)/(R^2 - 1)##
    • ## t_2 = (n_2 - R n_1)/(R^2 - 1)##
    To summarize, ##t = N/(R^2 - 1)##, where N is an integer at least 0 and less than ##R^2 - 1##. It can thus have ##R^2 - 1## values.

    We must exclude times of day when the hands' positions coincide. That happens when ##t = N/(R - 1)##, where N is an integer at least 0 and less than ##R - 1##. There are thus ##R - 1## such values, and the number of ambiguous-interpretation times is thus ##(R^2 - 1) - (R - 1) = R(R - 1)##.

    For R = 12, the number of ambiguous-interpretation times is 132, and the number of coincident-hand times is 11.
     
  4. Sep 2, 2018 #3

    StoneTemplePython

    User Avatar
    Science Advisor
    Gold Member

    In general the train of thought seems to work though the stated answer is wrong. There are simpler approaches.

    Incidentally, I read this statement many times and could not figure out what it means. These are hour and minute hands on a non-broken clock so I don't understand the purpose of "valid times". I couldn't figure out how to interpret ##t_1## vs ##t_2## vs ##t##. Defining ##t_1## and ##t_2## before using them, would be quite helpful here.
     
  5. Sep 2, 2018 #4
    In this problem, we want to find times for which the two hands' positions can be interpreted as being for two different times. These times I called t1 and t2. Let us call one of the hands h1 and the other one h2. At time t1, h1 is the hour hand and h2 is the minute hand, and at time t2, h1 is the minute hand and h2 is the hour hand.
     
  6. Sep 4, 2018 #5
    Suppose [itex]a_n\geq 0, n\in\mathbb N[/itex] is monotone decreasing. Assume [itex]\sum _{k=0}^\infty 2^k a_{2^k} <\infty[/itex]. Due to monotonicity we have an upper bound
    [tex]
    \begin{align*}
    \sum_{k=1}^\infty a_k &= a_1 + (a_2 + a_3) + \ldots + \left (a_{2^n} + a_{2^n+1} +\ldots + a_{2^{n+1}-1}\right ) + \ldots \\
    &\leq a_1 + (a_2 + a_2) + \ldots + 2^n a_{2^n} + \ldots = \sum_{k=0}^\infty 2^ḱ a_{2^k}<\infty .
    \end{align*}
    [/tex]
    Thus [itex]\sum _{k=1}^\infty a_k<\infty[/itex]. Now, assume [itex]\sum _{k=1}^\infty a_k <\infty[/itex]. By further manipulating and using monotonicity
    [tex]
    \begin{align*}
    \sum_{k=0}^\infty 2^ḱ a_{2^k} &= a_1 + (a_2 + a_2) + \ldots + \left (\underbrace{a_{2^{n+1}} + \ldots + a_{2^{n+1}}}_{2^{n+1} \text{ additives}}\right )+\ldots\\ &(\text{now move brackets to the left by one unit if that makes sense}) \\
    &= (a_1 + a_2) + (a_2 + a_4 + a_4 + a_4) + \ldots + \left ( \underbrace{a_{2^n} + a_{2^{n+1}} + \ldots + a_{2^{n+1}} }_{2^{n+1} \text{ additives}}\right )+\ldots \\
    &\leq (a_1 + a_1) + (a_2 + a_2 + a_3 + a_3) + \ldots + \left ( 2a_{2^n} + 2a_{2^n +1} + \ldots + 2a_{2^{n+1}-1}\right ) + \ldots = 2\sum _{k=1}^\infty a_k <\infty.
    \end{align*}
    [/tex]
    Not sure if the sum of the augmented series can be better estimated than with a factor of two.
    This is a fun one. Spent the whole lecture on some numerical methods mumbo jumbo trying to manipulate with some series. Just as I was finished the lector walked past and said "..aah, Cauchy condensation". Sure enough, then I googled it and it gave me exactly the same thing. :confused: Could have saved quite a bit of time :(
     
    Last edited: Sep 4, 2018
  7. Sep 4, 2018 #6

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    I could have said that it's Cauchy's condensation criterion, but I didn't want to, :-p

    Your proof is correct, although I think that working with partial sums instead of infinite many dots would have been a bit more professional.
     
  8. Sep 4, 2018 #7
    @fresh_42
    It was easier to visualise if I had all the additives written out. By partial sums do you mean something like
    [tex]
    \sum_{k=1}^\infty a_k = \sum _{j = 0}^\infty \sum_{k=2^j}^{2^{j+1} -1} a_{2^k}\quad ?
    [/tex]
     
  9. Sep 4, 2018 #8

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    No I mean ##S_{n}=\sum_{k=1}^{n}a_k## and ##S_{2^n}## so convergence of the series is convergence of the sequence of partial sums.
     
  10. Sep 5, 2018 #9

    Math_QED

    User Avatar
    Homework Helper

    If you would have googled on that term, you would have found a proof without any doubt. It is a classic theorem, and is often used to show convergence/divergence of the hypergeometric series (IMO more elegant that integral test).
     
  11. Sep 5, 2018 #10

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    You should have added that geometric series are basically the only application - at least what I have read.
     
  12. Sep 5, 2018 #11

    Math_QED

    User Avatar
    Homework Helper

    It is also useful to deduce convergence/divergence of series with logarithms. For example, it can also be used to show convergence/divergence of the Bertrand series.
     
  13. Sep 5, 2018 #12

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    Nice idea for a future problem, thanks. :smile:
     
  14. Sep 15, 2018 #13

    Math_QED

    User Avatar
    Homework Helper

    Solution for (9):

    Assume ##f## has no fixed point. Then the graph of ##f## must lie either above or either below the line ##y=x##, or otherwise the intermediate value theorem for continuous functions would imply the existence of a fixed point of ##f##. More formally, we can apply this theorem to ##g: x \mapsto f(x) - x## to deduce the existence of a zero.

    Wlog, assume the graph of ##f## lies above the line ##y=x##. I.e., ##g >0##. Then ##f\circ f(x) = f(f(x)) > f(x) > x## for every x. In particular, ##f \circ f(x) = x## for no x.
     
  15. Sep 15, 2018 #14

    Infrared

    User Avatar
    Gold Member

    Yep, this is correct.
     
  16. Sep 19, 2018 #15

    Math_QED

    User Avatar
    Homework Helper

    This is wrong. ##f ## is differentiable does not imply that ##f'## is continuous.

    For a counterexample, see ##f: \mathbb{R} \to \mathbb{R}: x \mapsto \begin{cases} x^2 \sin(\frac{1}{x}) \quad x \neq 0 \\ 0 \quad x = 0 \end{cases}##
     
  17. Sep 19, 2018 #16

    Math_QED

    User Avatar
    Homework Helper

    Continuously differentiable isn't needed in (10). Differentiability is enough.
     
  18. Sep 19, 2018 #17
    Yes, I realised that, my bad :sorry:
     
  19. Sep 19, 2018 #18
    oh thanks, i'll delete my solution
     
  20. Sep 19, 2018 #19

    Math_QED

    User Avatar
    Homework Helper

    It seems to be a common mistake, so maybe let it be so other users can learn from it :)
     
  21. Sep 19, 2018 #20
    too late wops
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted