Combinatorial nail varnish
I begin with a confession. Although the problem that follows can be represented as a combinatorial optimisation problem, I have not studied the literature about that problem. However, I know that it is in the same class of difficulty as the Travelling Salesperson Problem (TSP), about which there is a vast literature.
The story begins when I went for a haircut. My hairdresser subscribes to a service which delivers six to ten monthly magazines that will appeal to men - and, no, there are none of that kind, thank you very much! His science magazine had a page of mathematics, and the theme was based on using nail varnish to represent binary digits on a hand. Using your right hand, the smallest finger represents 0/1, then working to the left, the next is 0/2, then 0/4, 0/8 and 0/16. So every number from 0 to 31 can be represented by the presence or absence of nail varnish (or having plain varnish and glitter) on the appropriate fingers in the binary expansion. In particular, this means that any date in the month can be coded on you fingers.
So, the maths writer Katie Steckles posted a video on YouTube about this process. (look for Nail Varnish Tutorial - Binary numbers). Then she posed the question:
Suppose I want to paint my nails on one hand differently every day for a month – so I need to use all 31 combinations involving glitter. Assuming that a nail painted with plain varnish can have glitter added, but a nail with glitter needs to be nail-varnish-removed before it can become a plain nail again, what order do I apply the different combinations so that you minimise the amount of nail varnish remover I’ll need to use?
(Obviously, the answer does not need to code the dates in order.)
Would you like to think about solving this before looking at the published answer.
In the hairdresser's, my initial thought was that this could be formulated as a combinatorial optimisation problem as follows:
Let each of the 31 patterns be a node in a network. Define the edge distance between two patterns as 1 if the only change needed is to paint the nails, and 10N when you need to remove the varnish from N nails. Now the problem is to find a route through each of the 31 nodes to minimise the total distance.
This is not quite a TSP. You don't need to return to the start. So you might think that the way to solve Katie's problem is to find a solution to the TSP on these 31 nodes, and then delete the longest edge. Yes, but ... there might be a longer TS tour with a longest edge so long that it gave a smaller solution to Katie's problem. And that is why I know that the problem is in the same complexity class as the TSP.
Now you can look at the solution, which is that she needs to remove varnish 13 times. There is a very neat proof that this is the lower bound, and the web page shows how to achieve this theoretical minimum.
So here is the answer.
Now for a related, more general, problem: I wish to create a walking tour of M places. I can choose to start at any one of them, and finish at any one of them. The journey from home to the start and from the end to home does not count. How can I find the shortest walking tour? Dear reader, do you know what literature there is on this problem?
My thanks to aperiodical.com for drawing this amusing problem to my attention.
The story begins when I went for a haircut. My hairdresser subscribes to a service which delivers six to ten monthly magazines that will appeal to men - and, no, there are none of that kind, thank you very much! His science magazine had a page of mathematics, and the theme was based on using nail varnish to represent binary digits on a hand. Using your right hand, the smallest finger represents 0/1, then working to the left, the next is 0/2, then 0/4, 0/8 and 0/16. So every number from 0 to 31 can be represented by the presence or absence of nail varnish (or having plain varnish and glitter) on the appropriate fingers in the binary expansion. In particular, this means that any date in the month can be coded on you fingers.
So, the maths writer Katie Steckles posted a video on YouTube about this process. (look for Nail Varnish Tutorial - Binary numbers). Then she posed the question:
Suppose I want to paint my nails on one hand differently every day for a month – so I need to use all 31 combinations involving glitter. Assuming that a nail painted with plain varnish can have glitter added, but a nail with glitter needs to be nail-varnish-removed before it can become a plain nail again, what order do I apply the different combinations so that you minimise the amount of nail varnish remover I’ll need to use?
(Obviously, the answer does not need to code the dates in order.)
Would you like to think about solving this before looking at the published answer.
In the hairdresser's, my initial thought was that this could be formulated as a combinatorial optimisation problem as follows:
Let each of the 31 patterns be a node in a network. Define the edge distance between two patterns as 1 if the only change needed is to paint the nails, and 10N when you need to remove the varnish from N nails. Now the problem is to find a route through each of the 31 nodes to minimise the total distance.
This is not quite a TSP. You don't need to return to the start. So you might think that the way to solve Katie's problem is to find a solution to the TSP on these 31 nodes, and then delete the longest edge. Yes, but ... there might be a longer TS tour with a longest edge so long that it gave a smaller solution to Katie's problem. And that is why I know that the problem is in the same complexity class as the TSP.
Now you can look at the solution, which is that she needs to remove varnish 13 times. There is a very neat proof that this is the lower bound, and the web page shows how to achieve this theoretical minimum.
So here is the answer.
Now for a related, more general, problem: I wish to create a walking tour of M places. I can choose to start at any one of them, and finish at any one of them. The journey from home to the start and from the end to home does not count. How can I find the shortest walking tour? Dear reader, do you know what literature there is on this problem?
My thanks to aperiodical.com for drawing this amusing problem to my attention.
Comments
Post a Comment