Results 1 to 5 of 5

Math Help - Find the mysterious number

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    british columbia
    Posts
    14

    Find the mysterious number

    if a collection of pencils is placed in rows of 4, there are 2 left; if placed in row of 5, there are 3 left; and if placed in rows of 7, there are 5 left. what is the smallest possible number of pencils in the collection? please explain how you get the answer
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Feb 2011
    Posts
    83
    Thanks
    2

    Re: Find the mysterious number

    You need to use the Chinese Remainder Theorem. You can translate the problem in 3 seperate congruences mod 4, mod 5, and mod 7.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    british columbia
    Posts
    14

    Re: Find the mysterious number

    what is the chinese remainder theorem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466

    Re: Find the mysterious number

    If you don't know that you probably don't know what congruences are either so I will answer in more elementary terms.

    Let n be the number of pencils.

    "if a collection of pencils is placed in rows of 4, there are 2 left"
    Let i be the number of rows. So n= 4i+ 2 for some integer i.

    "if placed in rows of 5, there are 3 left"
    Now let j be the number of rows here. So n= 5j+ 3 for some integer j

    "and if placed in rows of 7, there are 5 left."
    Let k be the number of rows this time. So n= 7k+ 5

    We want to solve n- 7k= 5. One obvious answer is n= 5, k= 0. However, if we put 5 pencils in "rows of 5" there would be no pencil left over, not three, so we need to note that n= 5+ 7p, k= p would also give n- 7k= 5+7p- 7p= 5 for any integer p. The number of pencils is of the form n= 5+ 7p where p can be any non-negative integer.

    If we take p= 1, n= 5+ 7= 12 and if we divide that into "rows of 5" we have 2 left, not 3. If we take p= 2, n= 5+ 14= 19 and if we divide that into "rows of 5" we have 4 left over, not 3. If we take p= 3, n= 5+ 21= 26 and if we divide that into "rows of 5" we have one left over, not 3. If we take p= 4, n= 5+ 28= 33 and if we divide that into "rows of 5" we have 3 left over!

    But if we divide 33 pencils into "rows of 4" we have one pencil left over, not 2. So have to continue looking. In order not to interfere with the previous results, we need to add multiple of both 7 and 5: n= 33+ 35q. If we take q= 1, n= 33+ 35= 68. If we divide that into "rows of 4", we have no pencils left over. If we take q= 2, n= 33+ 70= 103. If we divide that into "rows of 4" we have 3 pencils left, not 2. If we take q= 3, n= 33+ 105= 138. If we divide that into "rows of 4", we have 34 rows with two pencils left. There must be at least 138 pencils left.

    (138 plus any multiple of 4(5)(7)= 140 will also work.)

    The Chinese Remainder Theorem essentially says that if you have a series of "congruence" equations, modulo n_1, n_2, ..., n_i, then all solutions will differ by multiples of the least common multiple of n_1, n_2, ..., n_i/
    Last edited by HallsofIvy; March 4th 2013 at 10:13 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,735
    Thanks
    642

    Re: Find the mysterious number

    Hello, JojoZ!

    Here is a rather primitive solution.


    If a collection of pencils is placed in rows of 4, there are 2 left;
    if placed in rows of 5, there are 3 left;
    and if placed in rows of 7, there are 5 left.
    What is the smallest possible number of pencils in the collection?

    Let N = the number of pencils.

    We are told: . \begin{Bmatrix}N \:=\:4a+2 & [1] \\ N \:=\:5b + 3 & [2] \\ N \:=\:7c + 5 & [3] \end{Bmatrix}\;\text{ for integers }a,b,c.

    Equate [1] and [2]: . 4a+2 \,=\,5b+3 \quad\Rightarrow\quad a \:=\:\frac{5b+1}{4}\;\;[3]

    Equate [2] and [3]: . 5b+3 \,=\,7c+5 \quad\Rightarrow\quad b \,=\,\frac{7c+2}{5}\;\;[4]
    . . . b \,=\,c + \frac{2c+2}{5} \quad\Rightarrow\quad b \:=\:c+ \frac{2(c+1)}{5}

    Since b is an integer, 2(c+1) must be divisible by 5.
    This happens when c = 4 + 5k

    Substitute into [4]: . b \:=\:\frac{7(5k+4)+2}{5} \quad\Rightarrow\quad b \:=\:7k+6

    Substitute into [3]: . a \:=\:\frac{5(7k+6)+1}{4} \:=\:\frac{35k+31}{4}\;\;[5]
    . . . . . . . . . . . . . . . a \:=\:8k+7 + \frac{3k+3}{4} \quad\Rightarrow\quad a \:=\:8k+7 + \frac{3(k+1)}{4}

    Since a in an integer, 3(k+1) must be divisible by 4.
    This first happens when k=3.

    Substitute into [5]: . a \:=\:\frac{35(3)+31}{4} \quad\Rightarrow\quad a \,=\,34

    Substitute into [1]: . N \:=\:4(34)+2 \quad\Rightarrow\quad \boxed{N \:=\:138}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the mysterious number
    Posted in the Peer Math Review Forum
    Replies: 1
    Last Post: March 4th 2013, 05:44 AM
  2. Angle between planes has mysterious absolute value
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: November 20th 2012, 06:37 PM
  3. Mysterious Property When Translating Graphs
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 28th 2011, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum