Results 1 to 8 of 8

Thread: 2 interesting problems

  1. #1
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    2 interesting problems

    1. Let $\displaystyle g(n)$ be the greatest odd divisor of $\displaystyle n$, show that $\displaystyle
      \mathop {\lim }\limits_{n \to + \infty } \tfrac{1}
      {n} \cdot \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}}
      {k}}
      $ exists and find it ( Bulgaria 1985)
    2. Find all $\displaystyle
      k \in \mathbb{Z}\text{ with }k \geq 2
      $ such that $\displaystyle
      n \not|g(k^n+1)
      $, $\displaystyle
      \forall n \in \mathbb{Z}/n > 1
      $ (Olimpíada Rioplatense 2008) - $\displaystyle g(n)$ is defined as in 1 -


    Have fun!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by PaulRS View Post
    1. Let $\displaystyle g(n)$ be the greatest odd divisor of $\displaystyle n$, show that $\displaystyle
      \mathop {\lim }\limits_{n \to + \infty } \tfrac{1}
      {n} \cdot \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}}
      {k}}
      $ exists and find it ( Bulgaria 1985)
    a simple observation shows that $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1.$ the value of $\displaystyle m$ is not important. what we need is to see that $\displaystyle m \rightarrow \infty$ as $\displaystyle n \rightarrow \infty.$

    now since $\displaystyle x-1 < \lfloor x \rfloor \leq x,$ the squeeze theorem gives us: $\displaystyle \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^n \frac{g(k)}{k}=\frac{2}{3}. \ \ \Box$

    the second problem is left for other members to try!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by NonCommAlg View Post
    a simple observation shows that $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1.$ the value of $\displaystyle m$ is not important. what we need is to see that $\displaystyle m \rightarrow \infty$ as $\displaystyle n \rightarrow \infty.$

    now since $\displaystyle x-1 < \lfloor x \rfloor \leq x,$ the squeeze theorem gives us: $\displaystyle \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^n \frac{g(k)}{k}=\frac{2}{3}. \ \ \Box$

    the second problem is left for other members to try!
    How did you obtain $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1$?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by chiph588@ View Post
    How did you obtain $\displaystyle \sum_{k=1}^n \frac{g(k)}{k} = \sum_{k=1}^m \frac{1}{2^{k-1}} \left \lfloor \frac{n+2^{k-1}}{2^k} \right \rfloor,$ where $\displaystyle m=\lfloor \log_2 n \rfloor + 1$?
    First note that: $\displaystyle
    a + 2^{t } \equiv 0\left( {\bmod .2^{t+1} } \right) \Leftrightarrow a \equiv 2^{t} \left( {\bmod .2^{t+1} } \right)
    $ (sum $\displaystyle 2^{t}$ on both sides)

    The idea is that$\displaystyle
    a = 2^t \cdot s{\text{ with }}s \ne \dot 2
    $ iff $\displaystyle a\equiv{2^{t}}(\bmod.2^{t+1})$

    Indeed, to prove this:
    $\displaystyle
    a = 2^t \cdot \left( {2l + 1} \right) \equiv 2^t \left( {\bmod .2^{t + 1} } \right)
    $, conversly if $\displaystyle
    a \equiv 2^t \left( {\bmod .2^{t + 1} } \right)
    $ then $\displaystyle
    \left. {2^t } \right|{a }
    $ and $\displaystyle 2 ^{t+1}\not|a$

    Now since $\displaystyle
    \left\lfloor {\tfrac{n}
    {a}} \right\rfloor - \left\lfloor {\tfrac{{n - 1}}
    {a}} \right\rfloor = \left\{ \begin{gathered}
    1{\text{ if }}\left. a \right|n \hfill \\
    0{\text{ otherwise}} \hfill \\
    \end{gathered} \right.
    $

    It follows easily that: $\displaystyle
    \sum\limits_{k = 1}^\infty {\tfrac{1}
    {{2^{k - 1} }} \cdot \left( {\left\lfloor {\tfrac{{n + 1 + 2^{k - 1} }}
    {{2^k }}} \right\rfloor - \left\lfloor {\tfrac{{n + 2^{k - 1} }}
    {{2^k }}} \right\rfloor } \right)} = \tfrac{{g\left( {n + 1} \right)}}
    {{n + 1}}
    $ (only one of the terms is not 0 )


    My proof of (1) is based on the following observation: $\displaystyle
    \tfrac{{g\left( n \right)}}
    {n} = 2 - \sum\limits_{\left. {2^s } \right|n{\text{ ; }}s \geqslant 0} {\tfrac{1}
    {{2^s }}}
    $ then by a simple counting argument ($\displaystyle 2^j$ appears as many times as multiples of $\displaystyle 2^j$ there are in between 1 and n -both included-, that is $\displaystyle \left\lfloor {\tfrac{n}
    {{2^k }}} \right\rfloor $ ): $\displaystyle
    \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}}
    {k}} = 2 \cdot n - \sum\limits_{k = 0}^\infty {\tfrac{1}
    {{2^k }} \cdot \left\lfloor {\tfrac{n}
    {{2^k }}} \right\rfloor }
    $ ...
    Last edited by PaulRS; Jan 6th 2009 at 03:04 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Sorry to be a bother, but I'm still a bit confused...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by PaulRS View Post
    1. Let $\displaystyle g(n)$ be the greatest odd divisor of $\displaystyle n$, show that $\displaystyle
      \mathop {\lim }\limits_{n \to + \infty } \tfrac{1}
      {n} \cdot \sum\limits_{k = 1}^n {\tfrac{{g\left( k \right)}}
      {k}}
      $ exists and find it ( Bulgaria 1985)
    2. Find all $\displaystyle
      k \in \mathbb{Z}\text{ with }k \geq 2
      $ such that $\displaystyle
      n \not|g(k^n+1)
      $, $\displaystyle
      \forall n \in \mathbb{Z}/n > 1
      $ (Olimpíada Rioplatense 2008) - $\displaystyle g(n)$ is defined as in 1 -


    Have fun!
    Any hints on 2?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by PaulRS View Post
    Find all $\displaystyle
    k \in \mathbb{Z}\text{ with }k \geq 2
    $ such that $\displaystyle
    n \not|g(k^n+1)
    $, $\displaystyle
    \forall n \in \mathbb{Z}/n > 1
    $ (Olimpíada Rioplatense 2008) - $\displaystyle g(n)$ is defined as in 1 -
    Correct me if I am wrong but the question is not clear as stated. Does the question mean to ask

    $\displaystyle
    r \not|g(k^r+1)
    $, $\displaystyle
    \forall r \in \mathbb{Z}/n > 1
    $

    or perhaps

    $\displaystyle
    r \not|g(k^n+1)
    $, $\displaystyle
    \forall r \in \mathbb{Z}/n > 1
    $

    or does it mean to ask

    $\displaystyle
    n\not|g(k^n+1)
    $, $\displaystyle
    \forall n
    $

    the way that for all is used currently doesn't make sense to me, since the quantified variable $\displaystyle n$ is used to define the domain set $\displaystyle \mathbb{Z}/n$.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    The bar there ("/") means "such that". So what I mean is that that should hold for all integers n greater than 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Looks interesting
    Posted in the Math Forum
    Replies: 0
    Last Post: Apr 23rd 2010, 07:46 AM
  2. An interesting problem on C=A+B
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jul 23rd 2009, 12:41 PM
  3. Interesting one!
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Nov 13th 2008, 05:46 AM
  4. Interesting X
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Jun 16th 2008, 03:44 PM
  5. Interesting Problem
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: Jul 16th 2006, 06:29 AM

Search Tags


/mathhelpforum @mathhelpforum