Site icon R-bloggers

Dyson’s Algorithm for the Twelve Coins Problem

[This article was first published on R – Win Vector LLC, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Nina continues with the 12 coins problem by transcribing Dyson’s algorithm into R. It is kind of a fun article.

Most of us see the 12 coins problem as a one-off puzzle that we spend a little time with and give up on.

In her earlier “The Twelve Coins Puzzle” Nina used an algebraic notation to allow her to search long enough to solve the 12 coins problem. There wasn’t really any deep algebra to the solution, the “algebraic notation” is just a mathematician’s favorite method to write sparse vectors. And the sparse notation makes things a bit easier.

However, Dyson’s solution solves the problem for many different counts of coins and discusses the optimality of the solution. However, the solution procedure is a variation of a previously written up method that was shown to be wrong. So we have to read very carefully and even after that are living a Knuth quotes:

Beware of bugs in the above code; I have only proved it correct, not tried it.

In the modern world- procedures are algorithms, and algorithms can be run or tried. Nina does just that in “Dyson’s Algorithm for the Twelve Coins Problem”. Funnily enough- in translating the procedure to a modern algorithm she runs back into the signed trinary notation underlying her solution to “Bachet’s Four Weights Problem”.

This has always been the deep hope of mathematics students: that problems can be organized systematically in a manner similar to mathematics. Or knowning a moderate amount of mathematics solves a large number of problems. It turns out the 12 coins problem has real algebraic structure and Nina explores and explains it here. Please check it out.

To leave a comment for the author, please follow the link and comment on their blog: R – Win Vector LLC.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Exit mobile version