Google Analytics

Saturday 26 January 2019

Twelve Balls

Things that amused us when we should have been working

Solution to the Twelve Balls Problem and other matters

I came across a note I made in 1970 (on the right of the notepad, above):

                                        SHINE BALD TOP
                                        BALD SPOT
                                        SLAB DINE
                                        HEAP LIST

It took me a while to remember what it was. Eventually it came back: it was the solution to the twelve balls problem (sometimes known as the twelve coins problem). One of the management staff posed it in November, 1969, when we were auditing Spencer and Halstead, an engineering manufacturer at Ossett. We couldn’t solve it. Insufferably, he wouldn’t tell us the answer until our next visit four months later.

The Problem: You have twelve identical-looking balls (or they could be coins or anything similar). One of them is a forgery and is therefore different in weight to others: it could be heavier or it could be lighter but you do not know which. You have a simple balance to weigh the balls against each other, but you can use it only three times – no more. How do you identify the fake ball and whether it weighs more or less than the others?

Note that you do not know whether the fake is heavier or lighter. If you knew for certain that it was, say, definitely lighter than the others, the problem is slightly different: it becomes a question of how to find a single fake out of nine coins in two weighings, or out of twenty-seven coins in three weighings. This is simpler and is not addressed here.

You may wish to pause to consider it further at this point. Or, if you’ve glazed over already, you may wish to jump to the end to find out about the other notes on the notepad.

                                                                *          *          *

The answer is to label the twelve balls with the letters of the first phrase above, and then weigh them in groups of eight – four against four – as specified in the three pairs of words.

For example, if the three weighings come out as (i) balance (ii) left heavy (iii) right heavy, then you know the faulty ball is not one of those in the first weighing, so it must be H, I, N or E. The second weighing eliminates H which is not there, and because I, N and E are on the light side, one of these must be lighter than all the others. Of these only E is on the light side in the third weighing, so E is the fake, and it is lighter than the others.

I wondered how this could work for all possible answers. Well, first of all, because each weighing can have three possible outcomes – left heavier, right heavier or balance – there are 3 x 3 x 3 i.e. 27 possible outcomes across the three weighings. Secondly, as there are twelve balls, and as we know that only one of them is either heavier or lighter, there are 24 possible answers. So the number of possible outcomes exceeds the number of possible answers, suggesting that each outcome could identify a different answer, with three outcomes unused.

One of the unused outcomes has to be where all three weighings are in balance, because that would mean all balls had identical weight. 

Not being one to let this kind of thing pass by without further thought, I could not resist creating the following table (L means left heavy, R means right heavy and B means balance). Hey, some people enjoy crosswords, I enjoy doing this. Get over it!

      S heavy = RLR       S light = LRL
      H heavy = BBL       H light = BBR
      I heavy = BRR       I light = BLL
      N heavy = BRB       N light = BLB
      E heavy = BRL       E light = BLR
      B heavy = LLB       B light = RRB
      A heavy = LLL       A light = RRR
      L heavy = LLR       L light = RRL
      D heavy = LRB       D light = RLB
      T heavy = RBR       T light = LBL
      O heavy = RBB       O light = LBB
      P heavy = RBL       P light = LBR
      Not used: BBB, RLL, LRR

You can see that the outcomes for heavy balls are mirror images of the outcomes for light balls. Also, the ‘unused outcomes’ are ones which do not occur.

In fact, the table also tells you where to place each ball in the three weighings. Looking just at the left hand column: Ball A should be placed on the left of the balance in all three weighings; Ball O should be placed on the right in the first weighing and omitted from the second and third weighings.

With this insight, we could now create our own mnemonic for the solution. How about:

                                        READ THIS BLOG
                                        READ BITS
                                        BEAR GOLD
                                        THOR SLED

I think it works. It’s just a case of finding a phrase consisting of twelve different letters, and then jiggling the letters and weighing patterns around until you get words.

I wondered why a pair of outcomes is left over: RLL / LRR as well as BBB. It is because the solution only needs 24 rather than the full 26 of the 3 x 3 x 3, i.e. 27 possible outcomes. So could it be used for a thirteenth ball? Unfortunately not, because if you placed a thirteenth ball on the balance you would be weighing six balls against seven each time, which would tell you nothing. However, I think you could use this outcome instead of one of the others provided you switched round other balls to preserve the equality of the three four-against-four weighings.

Could you do four balls in two weighings? Theoretically, this has 8 possible answers with 3 x 3 i.e. 9 outcomes from two weighings. But, you get only a partial solution. You have to weigh one against one each time (with two two-against-two weighings, neither would balance, and five of the nine possible outcomes would be non-occurring). For example, labelling the balls A, B, C and D, and weighing A against B and then A against C:

      A heavy = LL       A light = RR
      B heavy = RB       B light = LB
      C heavy = BR       C light = BL
      D heavy =BB       D light = BB (also)
      Not used: RL, LR            

It identifies all outcomes except when ball D is the fake, which is identified correctly but not whether heavy or light. However, it would work if you had only three balls and two weighings. I suspect this was the starting point for the person who originally formulated the problem.

What if you were allowed four weighings? What, then, would be the maximum number of balls from which you could identify a lighter or heavier fake? There would then be 3 x 3 x 3 x 3, i.e. 81 possible outcomes. Forty balls would have eighty possible answers, but I suspect you would have insufficient non-occurring / unused outcomes to be able to do it.

Well, I’ve worked it out (I told you I’m a loony). Four weighings would allow you to find the fake amongst thirty-nine balls. If you want to know how I did it, look here. It actually gives quite an insight into how the whole things works. It appears there is always a variety of ways to formulate the groups used in the weighings.

What if, rather than just one, there were two fake balls? How would you weigh them then? O.K., this is beginning to go beyond even my limits of pointless curiosity. Proper mathematicians have come up with formulae to show how many balls can be done in N weighings (in the main case considered here it’s ½(3n-1)-1 if you want to know, but it can get a lot more complicated).

It’s clever stuff. Out of the millions of ways in which twelve balls can be weighed against each other, it is genius to realise that you can arrange things so that each combination of outcomes identifies a different solution. And just as brilliant is the realisation that the balls can be labelled with the letters of a phrase so that the three weighings can be selected using pairs of words made from the letters of that phrase. But cleverest of all is whoever it was that came up with the problem in the first place.

                                                     *                 *                *

The other notes on the paper, by the way, are also things which amused us during our working hours.

The first is supposedly a telegram sent by a sailor to his wife on returning from a long voyage. It was intended to read “In today, home tonight, lots of love, Rodney” but got garbled during transmission and came out probably as what he was really thinking.

The second refers to a philanderer who took out policies with different insurers to provide for his loved ones. The policy for his baby was with General Accident, and so on.

So, we did not spend our entire time thinking about combinations and permutations. Welcome to the wonderful misogynistic world of business and commerce, 1970.

Sunday 20 January 2019

Some Memorable Posts

Posts from other blogs that have stuck in the memory

Although it’s over four years since I started this blog, I don’t have many readers or followers. Would I do better by being more like other bloggers?

Sadly, in my case, the answer is almost certainly “No”. No one would be interested in the beauty products I use, or pictures showing my repertoire of appealing facial expressions. I’m not sure anyone would want to know how comfortable my ten-year old M&S underpants are, or that I have had three Shredded Wheat for breakfast almost every day for the last forty years. I’m not qualified to give tips on how to get thousands of followers in just one week, or how to find commercial partnerships and get paid to promote products. As for hints on parenting and lifestyle, my kids would go ballistic if I posted those childhood photographs of them nude in the bath. 

I have explored linkies, retweet accounts and facebook boosts, but it seems to me that the main beneficiaries of these things are the people who host them. They get them going and within a few weeks are pestering you to say they have “teamed up” with this or that product to bring you the latest feminine lingerie, slimming aids or facial filler creams.

There are, however, some wonderful blogs I do admire, and would like to mention posts from the past few years that left a memorable impression.

I have a soft spot for blogs by middle aged men from the North of England retrospectively trying to construct meaning in their lives. Jonathan Humble’s poetry blog has some pretty powerful stuff, and some amusing stuff too, but it was a short story, Rainbow Friday, that first caught my attention. It could be straight from my own childhood. It is so good, I sometimes wonder why I bother trying to write a blog myself.

I followed Andrew Petcher from fairly early on. He has a well-read travel blog written in his guise as “international man of leisure”, but it was his childhood blog, from when children roamed free without a care, that attracted me first. His memories of a rugby-mad games teacher are spot-on, and his experiences of working in a privatised utility (part 1, part 2) have you gunning for re-nationalisation.

David Hodgson Personal Blog (not the snappiest of titles) is always fascinating. Two pieces I especially remember are one which begins by wondering what became of a large map of East Yorkshire bus routes that used to be on the side of a building overlooking the bus station in Bridlington, and a piece about the bizarre demise of the British electronics company Ferranti which supported him through university.

Moving on from elderly memoir, Estelle Hargraves’ The Skittish Library, a reflection on out-of-print oddities, was another early following. I found it when researching one of my own favourite old books, The Universal Book of Hobbies and Handicrafts. Her posts about the chapters on pet keeping and self defence give questionable advice about the disposal of unwanted kittens and how to pierce an assailant’s throat with the tip of your umbrella.

Brian’s Blog, a philosophical take on anything and everything contradictory in the world, always makes me think. The writer strives for a green and thoughtful life by cycling and recycling, and minimising present-day irrationalities. The diversity of the blog makes it difficult to pick specific pieces, but two recent ones that come to mind are on micro-beads and the idiocy of  GDPR cookies.

Sarada Gray also blogs about anything and everything. I look at all her posts, and especially enjoyed one about her new pair of reading glasses. She also, quite rightly, roused my indignation at how Mo Mowlem has been airbrushed out of history.

Finally, for now, Gary Strachan is possibly the most prolific blogger I follow. At sometimes two or three lengthy posts a day I could never keep up with everything he writes, but I regularly find myself returning for his wit and humour which is up there with Tim Dowling in the Guardian or Eddie Mair in the Radio Times. To be honest, I envy how easily he seems to turn it out. Over the last few days he has even produced a series of posts joking about his recent heart attack.  

I feel that’s enough for now and apologise for not mentioning more of the blogs I follow. I’ve made a mental note to attend to it in due course.

Friday 11 January 2019

Research Before The Internet

A. S. Byatt: Possession
as evoked by
A.S. Byatt - Possession: a Romance (5***)

The novel, Possession, evokes for me exactly what it was like to carry out research before the age of the internet, when we had to go to libraries to look things up in books and journals, and even use primary sources. More on this below.

It may also be the cleverest novel I have ever read: in fact I read it twice, partly because I enjoyed it so much and partly because a lot of it went over my head the first time through.

To describe the book first, the plot concerns two nineteen-eighties scholars who discover correspondence between two fictional Victorian poets revealing a previously unknown love affair. It is a discovery of immense historical significance, akin, say, to finding revelatory private correspondence by major literary figures such as Alfred Lord Tennyson or Christina Rossetti. As the two present-day scholars investigate the lives of the poets, they themselves are drawn into a relationship echoing that of the two Victorians. The two stories are revealed in parallel through five hundred pages of narrative, fictional poetry, letters, journals and diaries. So as well as the two love stories, and a cracking mystery story, A. S. Byatt has created substantial bodies of work attributed to the fictional poets and numerous pieces of writing attributed to other characters.

I struggled the first time through because: (i) the Victorian setting is rich in classical, biblical, literary and contemporary references of the kind with which educated Victorians of the time would have been very familiar but most of us today are not; and (ii) the nineteen-eighties setting alludes to numerous arcane and specialist approaches to textual analysis and criticism; e.g. we learn one of the scholars is trained in post-structuralist deconstruction. It found my own education sorely lacking.

Some might say the author is simply showing off, but essentially she is poking fun, and is abundantly able to do so because of her sweeping knowledge of Victorian and modern scholarship, poetry and literature. Some might say this is self-indulgent, but surely that is what all writers are. Her descriptions of beautiful things are dazzling, be they Victorian bathrooms, snowfall, the North York Moors or libraries. The 1990 Booker judges were clearly impressed.

That she put this sumptuous book together before 1990, before the internet, makes the achievement all the more impressive. She has not simply googled a tapestry of ideas and stitched them in, it stems from a lifetime’s study and expertise.

And that is what Possession strongly evokes for me: the pleasure and excitement of academic work before the age of abundant electronic resources and the internet. Anyone whose university days predated the turn of the century, perhaps researching a thesis or dissertation, or a final-year project, will find Possession brings it all back. You feel as if you are researching the Victorian poets yourself.

For me it was the light and quiet in a corner of the top floor of the Brynmor Jones Library at Hull, looking through the raked windows across the city to the distant Humber where bogies high above the river crossed slowly back and forth spinning the Humber Bridge suspension cables. Later it was the darkness and claustrophobia of the open stacks deep in the bowels of the John Rylands Library at Manchester.

The silence; the decades of collected journals; the Dewey Decimal index; the chance discovery of a promising book next to the one you were looking for; deliberately mis-shelving books so that no one else can deny you them the next day (I plead guilty, but I never stole anything, unlike one of the scholars in Possession); pages of handwritten notes from volumes piled six or seven high on your desk; coloured pens and paper clips, sore fingers; treasure-trails through the impenetrable Science and Social Sciences Citation Indexes (the SCI and SSCI); flip-lidded index card boxes; inter-library loans; journal offprint requests; scratchy, smelly, chemical photocopies; microfilm readers; hours following leads and loose ends which led to nowhere; puzzling new words and terminology in need of clarification; flashes of insight on encountering new ideas and making what you hoped, but rarely were, entirely original associations. More than anything else, the Csikszentmihalyian sense of flow: the buzz of your own thoughts, total immersion in the task at hand, suspended in time so that nothing else seemed to matter.

Through the nineteen-nineties things gradually changed. It became possible to research whole topics instantly and with plausible thoroughness through just a screen in an austere book-free room. Things were never the same again. I was still recommending books for my courses into the new century, but in rapidly changing subject areas such as computing, and even the social sciences, some of the university lecturers I knew stopped using print sources completely.

I hung on to my collection of academic books until retirement when they had to go. I kept a few that no one wanted, and ones that had once been especially useful and dear to me.

Key to star ratings: 5*** wonderful and hope to read again, 5* wonderful, 4* enjoyed it a lot and would recommend, 3* enjoyable/interesting, 2* didn't enjoy, 1* gave up.