Santa's Dirty Socks - an optimisation challenge
11 views
Skip to first unread message
Paul Shaddick
Oct 2, 2014, 2:18:58 PM10/2/14
to cs-unplugg...@googlegroups.com
If you use this as part of a discussion about optimisation of algorithms, you might want to challenge pupils to see if they can find an even better solution:
A better solution than that suggested by the elf is to keep dividing the remaining boxes into three piles and placing two of the piles in the balance. At each weighing if the piles balance exactly, the socks are in the unweighed pile. Always take the pile with the socks in, and repeat the division into three piles Where the number of boxes remaining (n) is not exactly divisible by three, weigh two piles of int(n/3) boxes i.e. divide by three and take the integral part of the result for each pile to go in the balance. So for example with 20 boxes weigh two piles of six leaving a pile of eight, or for 1024 the initial three piles are 341, 341 and 342.
A better solution than that suggested by the elf is to keep dividing the remaining boxes into three piles and placing two of the piles in the balance. At each weighing if the piles balance exactly, the socks are in the unweighed pile. Always take the pile with the socks in, and repeat the division into three piles Where the number of boxes remaining (n) is not exactly divisible by three, weigh two piles of int(n/3) boxes i.e. divide by three and take the integral part of the result for each pile to go in the balance. So for example with 20 boxes weigh two piles of six leaving a pile of eight, or for 1024 the initial three piles are 341, 341 and 342.
Reply all
Reply to author
Forward
0 new messages