After building your mental muscles on Perplexus logic problems, you feel ready to embark on the south sea logic treasure hunt. You travel to remote Uwalahooloo and are initially delighted to discover that you are the first treasure hunter to arrive. Or so you think. It turns out that the other hunters gave up long ago and departed with the natives, having despaired of ever working out which of the two paths through the jungle leads to the treasure and which leads to the deadly sphinx.

Not being someone to give up easily, you search the island and come upon the journal of a previous treasure hunter. You read:

"I've been here for months, but I’ve still reached no clear conclusion as to which path to take. I’ve recorded my findings in the hopes that someone may yet succeed where I have failed.

I have interviewed four natives and know each to be either a knight or a liar. However, as the island is part of an archipelago occupied by two different tribes, I am at a loss to say which language each native speaks (although I have determined that each native is monolingual). I have been able to learn a few interrogatives in both languages, but the confounded thing is that each question has a distinct, valid meaning in each language.

There is also one further complication: one of the natives has a hearing impairment and can't detect a “w” sound at the start of a word.

I list for you the questions and their variant translations in languages A and B:

Wuf?

A: Do more natives speak language A than language B?

B: Are all knights language B speakers?

Hacha?

A:Are there more liars than language A speakers?

B:Would any of the other natives tell me the truth?

Uf?

A:Can I reach the treasure by taking the left path?

B:Is the native with the hearing problem a knight?

The natives' responses (in uppercase letters) to each question were:

Native 1: Wuf? NO Hacha? YES Uf? YES

Native 2: Wuf? YES Hacha? NO Uf? YES

Native 3: Wuf? YES Hacha? YES Uf? NO

Native 4: Wuf? NO Hacha? YES Uf? YES"

(Note that the native with the hearing disability will have misinterpreted the question "Wuf?" as "Uf?")

Can you reason how to choose the correct path?

(In reply to Eh? by FrankM)

um... tell you about it--

represent the types of speakers as
ak: lang. A speaker and knight
al: lang. A speaker and liar
bk: lang. B speaker and knight
bl: lang. B speaker and liar

these are in an array of 4 elements. Speaker 1 is cycled through all four possible types, and depending on his veracity, his answers or the opposite thereof go into array q$(n,1) where the first subscript refers to the question (1 thru 6), second subscript to the speaker (native 1-4). (Yes from a knight becomes true, from a liar false; the opposite for No)

A loop inner to this treats native 2 in the same way, etc., until the full 6x4 array is filled with whatever could be gleaned based on these statements.

Then the array is checked for consistency: if the deduced truth value of a given hypothesis (1-6) conflicts, that can't be a possibilty for the set of native types. But if no conflict exists, then it's ok and is printed. The one-dimensional cons$ array gives the consensus truth value of the 6 questions, based on the veracities of all the speakers.

There are of course null values as, for a given native being assumed to be a given language speaker, only half the questions are addressed. At the end of any given assumption about a given speaker, all that set of questions is re-nulled-out in preparation for the next possibility of the assumptions.

There being 4 possible types of natives there are 4^4 = 256 sets of assumptions to check out.

A fancier program would have avoided some checking, by making sure that the first and last natives for example were either the same type or completely opposite, before going into the truth-value checks. But with only 256 sets to check the program is fast enough anyway.  The only assumption made was that the second native's first answer didn't match as he was the one with the hearing problem, as his was the only set where the first and last questions were answered the same way.

 

 

Edited on February 21, 2008, 10:44 pm

Posted by Charlie on 2008-02-21 22:42:19