Santa's Dirty Socks - an optimisation challenge

[Paul Shaddick]

There is a great opportunity here to see if students can come up with an even better solution than the elf does.

A better solution is to keep dividing the remaining boxes into three piles and placing two of the piles in the balance. If they balance exactly, the socks must be in the unweighed pile. Always take the pile with the socks in and repeat the division into three piles etc.
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. For example with 20 boxes weigh two piles of six leaving a pile of eight.

[george boukeas]

On Thu, Oct 2, 2014 at 9:27 PM, Paul Shaddick <pa...@shaddick.net> wrote:
> 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. For example with 20
> boxes weigh two piles of six leaving a pile of eight.

Paul, it's not very important, but with the 20-box example, why not
have two piles of seven, leaving a pile of six? This is a slightly
more even distribution. In general, it seems to me that when n modulo
3 equals 2, this remainder should be evenly split among the two piles
on the scale.

[Paul Shaddick]

You may be right Boukeas. Unless someone can handle the conditional probabilities mathematically, perhaps we should try a Monte Carlo simulation to check whether it is better to bring the modulus into the balance or not.

[shyamlal karra]

Hi my name is shyam and i am a student of theoretical computer science. I am trained in automata theory and model checking, i would like to know its application in real world and industry scenarios.can you help me out

[Tim Bell]

For our "Computer Science Field Guide" we always try to give real-world
applications. There's some material relating to automata here:
http://csfieldguide.org.nz/FormalLanguages.html (assuming you mean
real-world applications of automata, and not dirty socks - for dirty
socks, the main application is indeed errors in gift wrapping, although I
think divide and conquer is used in other areas of computing :-).

If you come up with other applications that would be compelling to high
school students, let me know!

cheers,
tim

>--
>You received this message because you are subscribed to the Google Groups
>"cs-unplugged-sharing" group.
>To unsubscribe from this group and stop receiving emails from it, send an
>email to cs-unplugged-sha...@googlegroups.com.
>To post to this group, send email to
>cs-unplugg...@googlegroups.com.
>Visit this group at http://groups.google.com/group/cs-unplugged-sharing.
>For more options, visit https://groups.google.com/d/optout.

[Aleksandra Faust]

Probably the easiest example for automata is any workflow process. For example bug processing. User reports a bug, analyst reviews it and assigns it to a developer. The developer fixes it and sends it to testing. From testing it can either go to a release or back to development, etc...

Another example are motion planning problems in robotics where you have a connectivity map as a directed graph and you move the agent through it. Edges can be distances, sights, etc...

Sandra

On Sat, Dec 20, 2014 at 1:56 AM, shyamlal karra <shyamla...@gmail.com> wrote:

Hi my name is shyam and i am a student of theoretical computer science. I am trained in automata theory and model checking, i would like to know its application in real world and industry scenarios.can you help me out