A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

imqwerty

  • one year ago

REALLY fun question

  • This Question is Closed
  1. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    you have got 32 ball and all of them have different weights and you also have a scale to weigh them.What is the minimum number of weighings in which you can find the second heaviest ball?

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    nasty XD

  3. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    :)

  4. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    The questions gives away a few hints. The number of balls is a power of 2, and an arbitrary one at that. Can we generalise this for a given power of 2?

  5. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Or better yet, can it be done for any \(n\)?

  6. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    1 ball: does not apply. 2 balls: one time. 3 balls: two times. 4 balls: three times. (Right?)

  7. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    OK, so suppose that we have a collection of \(n\) balls. Is it true that with \(n+1\) balls, we would need only one more weight?

  8. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Or better yet, if we have a collection of \(n\) balls whose second-highest weight is known, and we add another ball to it, would it be possible to determine if the newly added weight is the second-highest weight in only one weighing?

  9. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    hey guys so heres the answer 1st - we divide the balls into pair of 2s and therefore we get 16 pairs. We weigh the balls of each pair and take the heavier ball from all the pairs. TOTAL WEIGHINGS = 16 2nd-we divide the 16 balls that we got frm above step into pairs of 2s and we get 8 pairs, we weigh each the balls of each pair and take the heavier balls.TOTAL WEIGHINGS = 8 3rd - we divide the 8 balls into pair of 2s and get 4 pairs and weigh them and get the 4 heavier balls.TOTAL WEIGHINGS = 4 4th-we divide the 4 balls into pair of 2s and weigh them and get 2 heaviest balls.TOTAL WEIGHINGS = 2 5TH- we weigh the 2 balls so obtained and get the heaviest ball. TOTAL WEIGHINGS=1 now you might be wondering that we got the heaviest ball and not the second heaviest one. So now heres the way to find it Lets 1st think that how can that second heaviest ball can be eliminated- the only way to eliminate the 2nd heaviest ball is to compete it with the heaviest ball which we got in the 5th step. But there can be a case that the second heaviest ball did not get the chance to compete with the heaviest ball and then it came to the final and got out, so this means that the ball who weighed less in the final was the second heaviest ball. So now to make sure that the ball which weighed less in the final was the second heaviest ball we weigh it with the ball who got eliminated by the heaviest ball in the 1st,2nd,3rd and 4th rounds. If the loser of 5th round weighs less than the balls who got eliminated by heaviest ball, then we'll take that winner ball and we'll compete it with the other balls who got eliminated by the heaviest ball so TOTAL WEIGHINGS= 4 OVERALL TOTAL WEIGHINGS = 16+8+4+2+1+4 = 35

  10. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Oh, so it did have to do something with being a power of 2.

  11. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    yes @ParthKohli

  12. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    This is actually a dynamic programming problem, the answer for general case that parth has started is \[n+\log_2 n-2\]

  13. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    It seems more like a logic problem, like a mind bender type question.

  14. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Oh my, I don't think I'd ever have been able to do that. Haha.

  15. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the scale must be a comparison scale

  16. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    yes the scale was a comparison scale @Miracrown

  17. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thought so

  18. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    So this problem can't be solved for an \(n\) that is not a power of 2 because it can have many cases. Hmm.

  19. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Here is a slightly easier way to think about this problem in context to dynamic programming : It takes \(n-1\) comparisons to find out the first heaviest ball. And the first heaviest ball is compared against exactly \(\log_2 n\) times : |dw:1433838513485:dw| The second heaviest ball must be one of the \(\log_2 n\) balls that got compared against the first heaviest ball. So it neds \(\log_2n-1\) more comparisons.

  20. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    this problem can be solved for any \(n\), just replace \(\log_2n\) by \(\lceil \log_2 n\rceil \)

  21. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Great.

  22. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    well done @rational

  23. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I was reading this - something similar but the question is different ... http://classic-puzzles.blogspot.com.au/2006/12/13-balls-problem-one-of-hardest.html

  24. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    All your balls are different weights - so you need new logic. I would try putting all the balls into pairs, and doing a weighing of EACH one. and maybe placing them down in a way you remember their partner

  25. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    yes @Miracrown the link has similar questions but i mixed the question with slight twist.

  26. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    @Miracrown yes this is the actual approach

  27. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Another solution is here... to the same question... but a better answer https://weteachscience.org/mentoring/resources/lesson-plans/eight-balls-weighing-problem-logic

  28. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    @Miracrown how is the question same :)

  29. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, the goal is to find "the odd weighted ball" but your question is different. If you combine them all on the scale, there is no guarantee you will have the heaviest of lightest ball in any given set...

  30. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    The question isn't the same, but the problem is. :)

  31. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Actually not really.

  32. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That is where the popping of a brain vessel comes in

  33. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    i didn't combined all the ball nd weighed. what i did was that i weighed 2 balls at a time @Miracrown

  34. Miracrown
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Whatever you did, it was SMART

  35. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    :)

  36. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.