Results 1 to 5 of 5

Thread: Testing if a property belongs to all members of a set without trying each one

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    19

    Testing if a property belongs to all members of a set without trying each one

    Assume the following assertions:

    $\displaystyle a$, $\displaystyle b$ and $\displaystyle c$ are positive integers.

    $\displaystyle b > 1$

    $\displaystyle b^{\lceil\log_b(2^a)\rceil} \geq 2^a$

    $\displaystyle 8c \leq a$

    Given $\displaystyle a$ and $\displaystyle b$, is there a way to test that $\displaystyle \lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is true for all possible values of $\displaystyle c$, without trying each one?

    Example 1:
    $\displaystyle a = 32$
    $\displaystyle b = 85$

    The set of possible values for $\displaystyle c$ is $\displaystyle \{1, 2, 3, 4\}$. $\displaystyle 5$ is not valid because $\displaystyle 8{\times}5 > 32$. The condition that $\displaystyle \lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is satisfied by all possible values of $\displaystyle c$.

    Example 2:
    $\displaystyle a = 984$
    $\displaystyle b = 268$

    The set of possible values for $\displaystyle c$ is $\displaystyle \{1, 2, 3, ..., 123\}$. This example does not pass the test; it fails when $\displaystyle c = 122$ because:
    $\displaystyle \lceil\log_{268}(2^{8{\times}122})\rceil = \lceil\log_{268}(2^{8(122+1)})\rceil$


    Any help will be greatly appreciated. Thanks!

    Andre

    P.S. If this is not in the most appropriate thread, please direct me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,880
    Thanks
    1946
    Quote Originally Posted by Andre View Post
    Assume the following assertions:

    $\displaystyle a$, $\displaystyle b$ and $\displaystyle c$ are positive integers.

    $\displaystyle b > 1$

    $\displaystyle b^{\lceil\log_b(2^a)\rceil} \geq 2^a$

    $\displaystyle 8c \leq a$

    Given $\displaystyle a$ and $\displaystyle b$, is there a way to test that $\displaystyle \lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is true for all possible values of $\displaystyle c$, without trying each one?

    Example 1:
    $\displaystyle a = 32$
    $\displaystyle b = 85$

    The set of possible values for $\displaystyle c$ is $\displaystyle \{1, 2, 3, 4\}$. $\displaystyle 5$ is not valid because $\displaystyle 8{\times}5 > 32$. The condition that $\displaystyle \lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is satisfied by all possible values of $\displaystyle c$.

    Example 2:
    $\displaystyle a = 984$
    $\displaystyle b = 268$

    The set of possible values for $\displaystyle c$ is $\displaystyle \{1, 2, 3, ..., 123\}$. This example does not pass the test; it fails when $\displaystyle c = 122$ because:
    $\displaystyle \lceil\log_{268}(2^{8{\times}122})\rceil = \lceil\log_{268}(2^{8(122+1)})\rceil$


    Any help will be greatly appreciated. Thanks!

    Andre

    P.S. If this is not in the most appropriate thread, please direct me.
    Use basic log laws.

    $\displaystyle \log_b{2^{8(c + 1)}} = \log_b{2^{8c + 8}}$

    $\displaystyle =\log_b{(2^{8c}\cdot 2^8)}$

    $\displaystyle =\log_b{2^{8c}} + \log_b{2^8}$.


    Since $\displaystyle \log{x} > 0$ for all $\displaystyle x > 1$, this means $\displaystyle \log_b{2^8} > 0$.


    Therefore $\displaystyle \log_b{2^{8(c + 1)}} > \log_b{2^{8c}}$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    19
    Thank you very much for your helpful response. My confusion arose from the ceiling function in $\displaystyle \lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$.

    You've helped me realize the obvious solution for all $\displaystyle b < 256$ because $\displaystyle \lceil\log_b2^{8c}\rceil < \lceil\log_b{2^{8c}} + \log_b{2^8}\rceil$ for all $\displaystyle c$ where $\displaystyle \log_b{2^8} \geq 1$.

    Still, the other parts of the problem, namely the declaration that $\displaystyle 8c \leq a$, serve to impose a limit on $\displaystyle c$ such that $\displaystyle \lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$ can be satisfied when $\displaystyle b \geq 256$.

    I don't yet understand if there is a way to test that $\displaystyle \lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$ can be satisfied given $\displaystyle a$ and $\displaystyle b$, short of trying each member of the set of all possible values for $\displaystyle c$.

    Discovering a solution to the full problem is less important for me now that I know we can easily prove it for all $\displaystyle b < 256$, which is enough for most practical applications in computer science.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,880
    Thanks
    1946
    You should know that, for ANY base $\displaystyle b$, that

    $\displaystyle \log_b{x} < 0$ for all $\displaystyle x < 1$

    $\displaystyle \log_b{x} = 0$ if $\displaystyle x = 1$

    $\displaystyle \log_b{x} > 0$ if $\displaystyle x > 1$.

    If you don't believe me, try graphing some.


    Since $\displaystyle 2^8 > 1$, then $\displaystyle \log_b{2^8} > 0$.

    No other assumptions need to be made.

    $\displaystyle \log_b{2^{8c}} < \log_b{2^{8c}} + \log_b{2^8}$, thus completing your proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2009
    Posts
    19
    Your statements are correct, of course, but you are ignoring the ceiling function.

    Consider $\displaystyle b = 268$ and $\displaystyle c = 122$:

    While $\displaystyle \log_{268}2^{8\times122} < \log_{268}2^{8\times123}$, when you apply the ceiling function you see that $\displaystyle \lceil\log_{268}2^{8\times122}\rceil = \lceil\log_{268}2^{8\times123}\rceil$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Sep 29th 2010, 06:57 PM
  2. I am hope that my question belongs here.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 15th 2010, 12:06 AM
  3. im not sure if this belongs here
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Feb 9th 2008, 04:47 AM
  4. I think this belongs here??
    Posted in the Algebra Forum
    Replies: 9
    Last Post: May 31st 2007, 06:46 PM
  5. Does line belongs to plane?
    Posted in the Geometry Forum
    Replies: 3
    Last Post: Sep 15th 2006, 01:51 PM

Search Tags


/mathhelpforum @mathhelpforum