Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question in Discrete Math: Modular Arithmetic

  1. Sep 18, 2003 #1
    Hello,

    I am currently taking a course which has exercises/questions whose solutions are based on discrete mathematics. For anyone interested, the link to the course is:

    http://www.math.ualberta.ca/~tlewis/222_03f/222_03f.html

    We are encouraged to discuss these problems with others since some of the problems can be very challenging. Solutions then may be submitted jointly (or individually as long as credit is given where credit is due).

    I have not been able to find anyone with whom to collaborate. So I post my questions here in hopes to collaborate with those in the forum that like challenging questions. Here is a question under the section of modular arithmetic:


    The inspectors of fair trading found that a wholesaler of golfing equipment was swindling his retailers by including one box of substandard golf balls to every nine boxes of top grade balls he sold them. Each box contained 6 golf balls, and the external appearance of all the balls was identical. However, the substandard balls were each 1 gram too light. The retailers were informed of this discrepancy. The boxes all arrived in packs of ten, each with one substandard box - but which one?

    Phoebe Fivewood, the professional at a prestigious golf course, had just taken delivery of a large order so needed to sort them out quickly. She soon found a way to do this using a pair of scales (not pan balances) which required only one weighing on each scale for each batch of ten boxes. How did she do it? Note that she did not need to know what a golf ball should weigh.

    I am not sure how "Phoebe Fivewood" figured this out. I have done similar question relating to coins in which pan balances were used but the solution or possible solutions to this question are eluding me.

    Any thoughts on how to approach this question would be appreciated.

    Cheers.

    wubie.
     
  2. jcsd
  3. Sep 19, 2003 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you solve some simpler versions?

    What if you only had two boxes of balls and you had to tell which box was substandard?

    What if you knew the exact weight of a standard golf ball?
     
  4. Sep 20, 2003 #3
    Are those questions or hints?

    The weight of the golf ball is not supposed to be an issue.

    As far as two boxes of balls, I simply would weigh one against the other.

    There should be some way to separate the box of substandard balls from the boxes of top grade balls using only the two separate scales and only one weighing per scale.

    As well, I think that a possible solution can be achieved using modular arithmetic. But currently I have yet to figure that one out.
     
  5. Sep 20, 2003 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    They're both. :smile:

    The reason I bring up the case where you know the real weight of a standard golf ball is because the solution I found is a variation of the solution to this classic problem.
     
  6. Sep 20, 2003 #5

    ahrkron

    User Avatar
    Staff Emeritus
    Gold Member

    One further hint: how can you take advantage of each element of the problem?

    Try listing them, and think for a second about each (I know this sounds too general, but I don't want to give away too much just yet).

    Think about Hurkyl's simplified version a little further. You said you'd weigh "one against the other"; keep going. In detail, what will happen once you do that?
     
  7. Sep 20, 2003 #6

    ahrkron

    User Avatar
    Staff Emeritus
    Gold Member

    By the way,

    Very enjoyable notes!!
    ("Everything up to Module 2")
     
  8. Sep 20, 2003 #7
    Well,

    Someone has told me the solution, but I couldn't figure it out for myself. I still can't see the solution. Even with it in front of me.

    :frown:

    I didn't really absorb the answer, so I will forget what I saw and try to go with the hints that everyone here has given me and see if I can figure it out.

    BTW, were you being sarcastic ahrkron? It's hard to tell on a forum sometimes. [?]

    I think it's a neat way to approach discrete mathematics. I am not sure if I will do too well in the course ( I'm not too swift on the uptake), but the text book is a fun read.
     
  9. Sep 20, 2003 #8
    Oh, if anyone is interested in the text that I am using, it can be bought online here:

    http://www.amazon.com/exec/obidos/tg/detail/-/0716719789/102-7358686-1238562?v=glance

    Or perhaps one could find it locally as well. It's pretty cheap - about $8.00 US.

    It's not really a text book. It's more like a puzzle book which challenges one's problem solving skills. No mathematics needed. Although the solutions are rooted in mathematics. It definitely be a fun book to read on the side and discuss amongst friends.
     
  10. Sep 21, 2003 #9
    Hello,

    I told my gf the problem and she figured it out. It is very elementry when one hears the solution. It is late for me so I will relay all the gory details later. I don't think I would have found the answer by myself though.

    Perhaps I will post the solution that was given to me and someone can tell me how the other solution worked.

    Thanks for all the hints everyone.
     
  11. Sep 21, 2003 #10
    My gf found a fairly uncomplicated solution to this problem.

    Divide the group of ten boxes into two groups of five boxes.

    Label each box in a group of five a, b, c, d, e.

    Now create a new group from each group of five by taking one ball out of box a, two out of b, three out of c, etc.

    Weigh the one group of separated balls from one group of five boxes on one scale and weigh the other group of balls from the other five boxes on the other scale.

    Now the heavier of the two weighings will have NO substandard balls. This will be what the ACTUAL weight of the balls should be. The lighter of the two weighings will obviously be the group of five boxes that have the substandard balls.

    By comparing the two weights, the difference in weights should indicate what box has the substandard balls.

    That is if there is a difference of one gram, then only one ball of the group created from the group of five boxes is substandard. Since we only took one ball from box a, then it is box a of the lighter group of five boxes that has the substandard balls.

    Say there was a difference of 4 grams, this would correspond to 4 balls created from the group of five boxes of substandard weight. Since 4 balls were taken from box d of the light group of five boxes, then it is box d of the lighter group of five boxes that has the substandard group of balls.


    I don't know, this seems like a fairly straighfoward solution to me and fairly easy to understand.

    I see now how your hints were supposed to guide me. LOL.



    Thanks for everyone's help. I really appreciate the effort and the input. This was exactly the way I needed to be helped with this problem.

    The gradual release of hints without giving me the total solution helps me to develop my problem solving skills. Besides, nobody will be there to help me during my exam so I have to know how to do it myself.

    :wink:
     
  12. Sep 22, 2003 #11

    ahrkron

    User Avatar
    Staff Emeritus
    Gold Member

    Great!

    That's the spirit!

    (and no, no sarcasm; I really meant it: I enjoyed what I read from the notes)
     
    Last edited: Sep 22, 2003
  13. Sep 22, 2003 #12

    ahrkron

    User Avatar
    Staff Emeritus
    Gold Member

    Actually, you can probably gain something by looking at the problem now, knowing a solution.

    1. Usually, all elements of the problem are important for the solution. There can be of course some distractors around, but let's forget about that for now.

    The fact that there were scales and no one pan balance was important. Also, the fact that they were boxes instead of individual balls (or bricks, or whatever), is almost an invitation to redistribute the balls.

    2. In real life, you may not know which elements are important and which are superfluous; you then need to try hard to squeeze all tools you can get from the situation at hand.
     
  14. Sep 22, 2003 #13
    Those are some great points to consider ahrkron. I will remember that when I tackle the next set of questions.

    Thanks alot for your help.

    And thanks to everyone else who contributed to this thread.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Question in Discrete Math: Modular Arithmetic
  1. Discrete Math Question (Replies: 2)

  2. Modular arithmetic (Replies: 5)

  3. Modular arithmetic (Replies: 7)

Loading...