Results 1 to 7 of 7

Math Help - A logic question!!

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    23

    A logic question!!




    hi all. here is the question:

    there were 17 dogs who found a pile of bones. they decided to divide the bones equally but after they divided the bones, there was 5 extra bones left.

    One dog left so there was 16 dogs left. They decided to divide up the bones again, but this time had 10 extra bones left.

    Another dog left so there were 15 dogs left, when they divided up the bones again, there was 0 extra bones left.

    Two questions:
    1. what is the minimum number of bones in the pile?
    2. what is another possible solution to the number of bones in the pile?

    Answer:

    using brute force of multiples of 15, I found that 90 bones work and it is the smallest number possible. (if you disagree please let me know!)

    what is another number of bones that can work? Also, can someone tell me how to set this question up? I am very confused. Thanks!!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by soyeahiknow View Post



    hi all. here is the question:

    there were 17 dogs who found a pile of bones. they decided to divide the bones equally but after they divided the bones, there was 5 extra bones left.

    One dog left so there was 16 dogs left. They decided to divide up the bones again, but this time had 10 extra bones left.

    Another dog left so there were 15 dogs left, when they divided up the bones again, there was 0 extra bones left.

    Two questions:
    1. what is the minimum number of bones in the pile?
    2. what is another possible solution to the number of bones in the pile?

    Answer:

    using brute force of multiples of 15, I found that 90 bones work and it is the smallest number possible. (if you disagree please let me know!)

    what is another number of bones that can work? Also, can someone tell me how to set this question up? I am very confused. Thanks!!!!
    So

    \displaystyle x \equiv 5\ (\text{mod}\ 17)

    \displaystyle x \equiv 10\ (\text{mod}\ 16)

    \displaystyle x \equiv 0\ (\text{mod}\ 15)

    Since gcd(15,16,17)=1, the Chinese remainder theorem applies (see the link for a constructive algorithm). You already found a solution trough brute force; the general solution is \displaystyle x \equiv 90\ (\text{mod}\ 15\cdot16\cdot17).

    EDIT: I should have said that 15, 16, and 17 are pairwise coprime rather than gcd(15,16,17) = 1.
    Last edited by undefined; July 10th 2010 at 03:20 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    23
    Hi, can you explain further or work the problem out for me a little more? I tried looking at Wikipedia but am confused by the example they gave. Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by soyeahiknow View Post
    Hi, can you explain further or work the problem out for me a little more? I tried looking at Wikipedia but am confused by the example they gave. Thanks!
    The Chinese remainder theorem states that there is a unique solution mod N. You found the solution already through brute force and thus do not need to use the algorithm discussed in Wikipedia for this particular problem.

    The complete solution set is given by x = 90 + (15*16*17)k where k ranges over all integers (actually non-negative integers since we assume that having a negative number of bones doesn't make sense). So to find another solution, use for example, k = 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    23
    Thank you!

    Now so I know if I didn't do it by brute force, I would have to use the Euclidean algorithm correct? I looked up some sample problems with solutions that is where I am getting messed up on. I am not sure how that plays out. Could you shed some light on that?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by soyeahiknow View Post
    Thank you!

    Now so I know if I didn't do it by brute force, I would have to use the Euclidean algorithm correct? I looked up some sample problems with solutions that is where I am getting messed up on. I am not sure how that plays out. Could you shed some light on that?
    The algorithm described in the Wikipedia article involves finding modular inverses, and the typical fast algorithm for this is the extended Euclidean algorithm; also possible is modular exponentiation. For some nice pencil and paper solutions see this thread.

    Here is how your problem plays out, using labels from the Wikipedia article.

    \displaystyle x \equiv 5\ (\text{mod}\ 17)

    \displaystyle x \equiv 10\ (\text{mod}\ 16)

    \displaystyle x \equiv 0\ (\text{mod}\ 15)

    N = 4080

    N / 17 = 240

    N / 16 = 255

    N / 15 = 272

    \displaystyle e_1 is (the modular inverse of 240 mod 17) multiplied by (240).

    \displaystyle e_2 is (the modular inverse of 255 mod 16) multiplied by (255).

    Likewise for \displaystyle e_3.

    We find that

    \displaystyle e_1 = 9\cdot240 = 2160
    \displaystyle e_2 = 15\cdot255 = 3825
    \displaystyle e_3 = 8\cdot272 = 2176

    So the solution is given by (15)(2160) + (10)(3825) + (0)(2176) \displaystyle \equiv 90 (mod N).

    Note that it wasn't actually necessary to calculate \displaystyle e_3 because it just got multiplied by 0.

    To explain modular inverses: The Wikipedia article says "For each i the integers n_i and N / n_i are coprime. Using the extended Euclidean algorithm we can find integers r_i and s_i such that r_i n_i + s_iN / n_i = 1." This means that s_i multiplied by N / n_i plus a multiple of n_i equals 1; in other words, s_i is the modular inverse of N / n_i mod n_i.

    So for \displaystyle e_1 we need to find the modular inverse of 240 mod 17. This is the same as the modular inverse of 2 mod 17. I'll use simplependulum's method from this thread:

    [2^{-1}] = [\frac{1}{2}] = \frac{[9]}{[18]} = [9]

    Now for the modular inverse of 255 mod 16, which is the modular inverse of 15 mod 16.

    [15^{-1}] = [\frac{1}{15}] = \frac{[1]}{[-1]} = \frac{[-1]}{[1]} = [-1] = [15]
    Last edited by undefined; July 10th 2010 at 07:23 PM. Reason: clarity
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2010
    Posts
    23
    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. logic question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 21st 2009, 12:52 AM
  2. Logic question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 8th 2009, 06:46 AM
  3. logic question
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 4th 2009, 06:39 AM
  4. Logic Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 21st 2009, 01:13 PM
  5. logic question
    Posted in the Discrete Math Forum
    Replies: 20
    Last Post: January 25th 2009, 11:51 AM

Search Tags


/mathhelpforum @mathhelpforum