7
$\begingroup$

There is a race which has a truth gene. It consists of 3 alleles, namely T, F and O. A person inherits one allele from each of his parents, hence he/she has always exactly two alleles. For example, if the parents have alleles TF and FO, the child may have TF, TO, FF or FO. Genes are distributed randomly in the initial species. They behave as follows:

  • TT - Always speaks the truth, remains silent if not possible.1
  • TO - Same as TT.
  • FF - Always lies, remains silent if not possible.1
  • FO - Same as FF.
  • TF - One of T and F is the dominant allele.2 The individual behaves as per the dominant gene.
  • OO - Children die at birth.

Clarifications:

  1. There exists certain questions where it is not possible to give a truthful answer.

  2. This is a concept in genetics. For example, if T is the dominant allele, the person always speaks the truth. If F is dominant, he always lies. The dominant allele is the same for an entire species. So, if your father has F dominant in TF, and you are also a TF by birth, you will also have F dominant.

  3. There are no gene defects.

  4. Assume that every individual has children with exactly one opposite sex partner.

Question

You have just found all $8$ great-grandparents of a person named Mr.X. Each of them knows correctly the nature (lying or truth-telling) of each of their own direct descendants (but not each other's or Mr.X's) and themselves. They do not know anybody's genetic makeup. They do not know which allele is dominant, and neither do you. Nobody (including the great grand parents) knows the nature of Mr. X.

You must ask them a series of yes/no questions to determine the sex and nature (truth-telling/lying) of Mr.X, or else conclude that such a task is unaccomplishable for the given scenario. The maximum questions you require (worst case scenario) is $n$. Minimize $n$.

$\endgroup$
  • $\begingroup$ Do we know who had children with whom? Do they know? $\endgroup$ – Somo145 Oct 4 '15 at 10:51
  • $\begingroup$ Do the great-grandparents have more than one child per couple? Do the grandparents and parents also have more than one child per couple? $\endgroup$ – Gordon K Oct 4 '15 at 10:53
  • 1
    $\begingroup$ What about the Q gene? Someone's gotta ask the questions to the others, right? $\endgroup$ – Ian MacDonald Oct 4 '15 at 12:50
  • 1
    $\begingroup$ Interestingly the O alleles doesn't last over enough generations, they eventually decrease to zero and we fall back to the well known (TT, TF, FF) pattern. $\endgroup$ – Rohcana Oct 4 '15 at 14:32
  • 1
    $\begingroup$ To Mr. X's parents and grandparents know the knight/knave phenotypes of their ancestors? I.E., could you ask "What would your son say if I asked him whether you tell the truth"? $\endgroup$ – user1618143 Oct 9 '15 at 19:55
2
+50
$\begingroup$

It is not necessarily possible to get an answer as to the nature of Mr. X.

It is certainly possible that all of Mr. X's ancestors are genotype TF. In that scenario, it is then possible that Mr. X is either TT or FF.

In this scenario, no matter what the dominance rules are for the two alleles, we cannot know anything about what genes Mr. X received, so we cannot determine his nature.

Are there scenarios where it is possible to determine Mr. X's nature? Yes

If two parents are both liars and they have a child that is a truth-teller, then the F-gene must be dominant, and both parents were heterozygous TF$^1$, and the child is homozygous TT. The logic is the same with T and F reversed and reversed dominance.

Thus, if X's father's parents were both liars, but X's parents were both truth-tellers, then F would be the dominant gene, and since X's parents were both truth-tellers, they could not have had the F gene to pass to X, so X would be a truth-teller. Likewise for X's mothers parents, or for authenticity-switching. This leaves 4 scenarios. There are also eight scenarios where one pair of great-grandparents are the dominant type, their child is the recessive type, and X's parents are both the recessive type.

Update: Finding $n$. To summarize, it is only possible to determine X's nature if X's parents are both of the recessive trait and someone who is of the recessive trait has parents that are both the dominant trait. The latter condition identifies which trait is recessive, which allows us to know that both of X's parents must be homozygous recessive, so X must also.

So, assume X's parents are both the recessive trait and ask questions to see if you can prove it. If they are not both the recessive trait, or you cannot prove they are, then it is impossible to tell X's nature.

Annoyingly, you do not know which great-grandparents are paired with which others. However, I think it is safe to assume that each person knows the answer to the questions "Do you have a (grand)child in common with (point to a person) him/her?". I am also assuming it is possible to determine the genders of the 8 people, without asking any questions.

We'll use the standard trick of asking what someone would say if you asked them a question: "What would you say if I asked you 'Q'?" will always elicit the true answer to question 'Q'.

Pick a woman, label her "A" and use Q = "You have a grandchild that is a parent of X. Is that child a liar?" Given the double-asking, this comes out as "You have a grandchild that is a parent of X, if I asked you if that person is a liar, what would you say?" Assume that the answer we get for that parent is of the recessive trait.

Pick another woman, label her "C", and ask her: "If I asked you if you and (point to A) her have a grandchild in common, what would you say?" If the answer is no, then ask her the same first question. If the answer is yes, then ask one of the other two women the same first question.

You have now identified the traits of X's parents. If the answers do not match, then it is not possible to determine X's traits. You have asked 3 questions so far. If they match, continue.

If C does not share a grandchild with A, then ask one of the other two women that question. At this point, relabel the women so that A & C share a grandchild, as do E & G. At this point, you have asked at 3 or 4 questions.

Ask A "You have a child that is a grandparent of X. Is I asked you if that child is a liar, what would you say?" If the answer indicates that child has the dominant trait, ask C the same question. If this answer is also the dominant trait, then you have your solution. The best case scenario is 5 questions.

If either of those answers was the submissive trait, then ask the same question of the other two women.

The worst case scenario is that all four of the grandparents have the submissive trait, as well as both parents. You can determine this in at most 8 questions.

In this case, ask each of the eight people "If I asked you if you were a liar, what would you say?" 8 more questions.

If more than half are of the dominant trait, then there must be at least one pair where both are dominant. You don't need to determine which; you have succeeded.

The worst case scenario is that two of each gender are the dominant trait and two are of the recessive trait. In this case, ask each of the woman with the dominant trait "If I asked you if he (points to one male with dominant trait) or he (points to other male with dominant trait) were your husband, what would you say?" If either says yes, you have succeeded. If both say no, then it is not possible to determine X's trait.

Thus, all tolled, this adds up to 18 questions for the worst case scenario. In the case that all of X's parents and grandparents are the recessive trait, as are half his great-grandmothers and great-grandfathers, then finding the answer or finding the problem is unsolvable comes down to determining if any of the pairs of great-grandparents were of the dominant trait.

$^1$Note: the presence of the O allele does not affect the math. If two people are truth-tellers and have a child that is a liar, then the T gene must be dominant, and the child must be either FF or FO. If T is dominant and two people are both liars, then their children must also be liars (or stillbirths, which we know Mr. X and his ancestors are not).

As to Mr X.'s gender. We can assume that the title "Mister" means X is male. If that assumption is not valid, then we have to add yet another question to determine X's gender, for a total of 19 questions.

Complication: If two people have had a stillbirth, then they must both have had an O gene. Thus, if X's parents are both the same phenotype (liar or truth-teller), but they have also had a stillbirth, then we know X must be the same type, regardless of gene dominance.

Second Update Dealing with stillbirths.

There is also the possibility that we can use stillbirths to rule out the possibility that someone inherited a trait. If a person's parents are both one trait, and the person had a sibling that was stillborn, then that person must have that same trait, and cannot have any genes for the opposite trait.

It would take 16 questions to determine that all of X's parents, grandparents, and great-grandparents are of the same trait (see above). The worst case scenario is that X had no stillborn siblings, nor did his parents, but all four of his grandparents did.

Assuming that the only stillbirths anyone knows about are those among their descendants (including their own children, of course). Thus, it would take 7 questions to determine that X had no siblings that were stillbirths, that neither of his parents did, and that all 4 of his grandparents did.

Thus, the new worst-case (yest still solvable) scenario is $n = 23$ questions. (Plus 1 to determine X's gender, if necessary).

Third Update Adding another, different worst-case scenario, but same limit.

If someone is the same trait as both his/her parents, but has siblings of the opposite trait, then we know that the person and parents are the dominant trait, and the sibling is the recessive trait.

Thus, if both of X's parents are the recessive trait, each of them has a parent of each type, and one of the grandparents with the dominant trait has parents with the dominant trait and a sibling with a recessive trait, we can determine for sure which trait is recessive, and that X's parents both have it, so X must, as well.

This adds up to 16 questions to determine all the ancestor's traits, as above, plus 4 questions to sort which great-grandparents are which, and 2 questions to determine if a grandparent with the dominant trait has a sibling with the recessive trait.

This takes $n = 22$ questions. However, if after all questions, we still don't know, there is the possibility that X had a stillborn sibling, so we could determine for sure that X had that trait with 1 more question. Thus brings us up to $n = 23$, which is the same as for the second update.

$\endgroup$
  • $\begingroup$ Are you assuming that 100% of stillborn infants have OO genotypes? That seems unlikely. $\endgroup$ – user1618143 Oct 9 '15 at 19:58
4
$\begingroup$

Note: The latest edit invalidates this answer.

You can just ask one great-grandparent

1. Does exactly one of you and Mr. X tell the truth?
2. Is exactly one of the statements 'Mr. X is male' and 'You tell the truth' true?

This gives the truth table

Truth table
(where G = Great-grandparent tells the truth, M = Mr. X is male, T = Mr. X tells the truth, 1 and 2 = answer to that question)
which has each combination of answers mapped onto one unique combination of attributes for Mr. X regardless of whether the great-grandparent tells the truth. So $n = 2$.

$\endgroup$
  • $\begingroup$ Didn't notice this flaw. I meant to say that nobody knows the nature of Mr X. That is why it is possible that you never find the answer in certain circumstances. $\endgroup$ – ghosts_in_the_code Oct 4 '15 at 10:37
1
$\begingroup$

Almost certainly non- optimal.

Initial step: Query for determining truth teller vs falsehoodian:

Would you remain silent if I gave you an inanswerable question.
You do this for the number of great grandparents you need to get

One note on an unsolvable case:

If they are All TF, then it is impossible to derive as they will all display the dominant trait, with no indication they are heterozygotes. This tells us in general, we cannot guarantee a solution that doesn't have to find out all of the ancestors genotypes. However this can be optimized by asking, do any of your descendants display a different phenotype than you, after having surmised the original great grandparent's phenotype.

A pretty key question:

Do any of your descendants have a phenotype neither of their parents have? (or something to that effect) If true, this immediately determines if there is a recessive, Additionally depending on the phrasing what is the recessive gene.

Sorry for just a partial answer, I have some stuff to do hope to come back, and maybe someone can be inspired to greater creativity after me.

$\endgroup$
  • $\begingroup$ I realize now we were not necessarily solving for genotype... woops. $\endgroup$ – Going hamateur Oct 4 '15 at 2:44
1
$\begingroup$

Following on from @goinghamateur, isn't is simply a case of asking a single great-grandparent

Would you remain silent if I gave you an inanswerable question?

Then ask them if Mr. X is male (which is probably true anyway) and whether Mr. X is a truthteller.

Based on their answer to the first question, you know whether they are telling the truth for the other two. All the stuff about alleles is irrelevant. $n = 3$.

$\endgroup$
  • $\begingroup$ Please see the edit clarification. Nobody knows Mr X's nature. $\endgroup$ – ghosts_in_the_code Oct 4 '15 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.