[bushindo]

Suppose that there are 16 people standing in a straight line in a room. Each person is either a truth teller (always tell the truth) or a naysayer (always answer NO). You are in a different room, and your task is to determine the positions of all the truth teller in this line. You can not see the 16 people, as they are in the other room.

You are allowed to take 'turn' to determine their persona. During each turn, you can address 1 single YES/NO question to ALL 16 people. The question will be relayed to the 16 people, and the total number of YES will be relayed back to you. Assume that number of YES relayed back to you at the end of each turn is reliable. As usual, you are not allowed to ask questions that are impossible for the truth tellers to answer accurately with YES/NO (asking paradoxes, etc.) .

Show that it is possible to correctly identify all the truth tellers and the naysayers within 6 questions.

Edited November 30, 2010 by bushindo

[Guest]

Suppose that there are 16 people standing in a straight line in a room. Each person is either a truth teller (always tell the truth) or a naysayer (always answer NO). You are in a different room, and your task is to determine the positions of all the truth teller in this line. You can not see the 16 people, as they are in the other room.

You are allowed to take 'turn' to determine their persona. During each turn, you can address 1 single YES/NO question to ALL 16 people. The question will be relayed to the 16 people, and the total number of YES will be relayed back to you. Assume that number of YES relayed back to you at the end of each turn is reliable. As usual, you are not allowed to ask questions that are impossible for the truth tellers to answer accurately with YES/NO (asking paradoxes, etc.) .

Show that it is possible to correctly identify all the truth tellers and the naysayers within 6 questions.

This can be accomplished through a binary tree sort in 5 questions:

Are you a truth teller?

Are you in the position 1 through 8?

Are you in position 1, 2, 3, 4, 9, 10, 11, or 12?

Are you in position 1, 2, 5, 6, 9, 10, 13, or 14?

Are you in position 1, 3, 5, 7, 8, 11, 13, or 15?

This will give you 5 numbers, the first number will be 0 to 16, the other 4 will be from 0 to 8. This 5 digit combination is unique for all possible combos.

I tried to upload a spreadsheet to Google Docs to share here for the proof, but it's too large.

[bushindo]

This can be accomplished through a binary tree sort in 5 questions:

Are you a truth teller?

Are you in the position 1 through 8?

Are you in position 1, 2, 3, 4, 9, 10, 11, or 12?

Are you in position 1, 2, 5, 6, 9, 10, 13, or 14?

Are you in position 1, 3, 5, 7, 8, 11, 13, or 15?

This will give you 5 numbers, the first number will be 0 to 16, the other 4 will be from 0 to 8. This 5 digit combination is unique for all possible combos.

I tried to upload a spreadsheet to Google Docs to share here for the proof, but it's too large.

Some comment

There might be an error with the excel sheet somewhere, because this 5 digit combination is not unique for all possible combos.. Let's say that the answers to the 5 questions above in the same order are (2, 1, 1, 1, 1). We can see that the following positions could have produced that response

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  0  0  0  T  0  0  0  0  0  0  T  0  0  0  0

0  0  0  0  0  0  T  0  0  T  0  0  0  0  0  0

0  0  0  T  0  0  0  0  0  0  0  0  T  0  0  0

where the index in the top row indicates the position, 0 indicates a naysayer, and T indicates a truth teller, and rows 2-4 each indicate a possible combination. In fact, if there are only 2 truth tellers in the 16, and the 2 truth tellers are located at positions i and 17-i, then their response to those 5 questions will be (2, 1, 1, 1, 1). More questions probably are needed to clarify those ambiguous cases.

Edited November 30, 2010 by bushindo

[Guest]

I have a posible solution to this. Have tried quite a few times to cross-check it and it worked each time! Let me know if you find a case where it does not work.

The six questions to ask would be the following:

1) Are you a truthteller?

2) Are you in positions 1 to 8?

3) Are you in an even position (2,4,6,8,10,12,14,16)

4) Are you in a position which is a multiple of 3 (3,6,9,12,15)

5) Are you in a position which is a multiple of 4 (4,8,12,16)

6) Are you ina a position which is a prime number (2,3,5,7,11,13)

The answers are unique for each set of positions (as far as I can tell).

[bushindo]

I have a posible solution to this. Have tried quite a few times to cross-check it and it worked each time! Let me know if you find a case where it does not work.

The six questions to ask would be the following:

1) Are you a truthteller?

2) Are you in positions 1 to 8?

3) Are you in an even position (2,4,6,8,10,12,14,16)

4) Are you in a position which is a multiple of 3 (3,6,9,12,15)

5) Are you in a position which is a multiple of 4 (4,8,12,16)

6) Are you ina a position which is a prime number (2,3,5,7,11,13)

The answers are unique for each set of positions (as far as I can tell).

Some comment

It appears that the following possible 2 combinations have the same response: (1, 1, 1, 0, 1, 0 )

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  0  0  T  0  0  0  0  0  0  0  0  0  0  0  0

0  0  0  0  0  0  0  T  0  0  0  0  0  0  0  0

where T indicates the truth tellers, 0 indicates a naysayer, and the index on top indicates their position.

Edited December 1, 2010 by bushindo

[phaze]

If I were to ask you if you were a truth teller you would reply with what answer?

This will tell you how many truth tellers there are and if there are 16 or 0 yes then your job is already done.

From here the binary search method may have potential (still need to verify this) however will need to keep asking questions of the form "If I were to ask you if.... what would your reply be"

[phaze]

Figured the binary search method would only work if there was one truth teller so the second question if there is between 1 - 4 truth tellers is

What would your answer be if I were to ask if there is a truth teller somewhere to your right?

for 12-16 truth tellers

What would your answer be if I were to ask if there is a liar somewhere to your right?

still need to work on the question for between 5-11 truth tellers

[bushindo]

Figured the binary search method would only work if there was one truth teller so the second question if there is between 1 - 4 truth tellers is

What would your answer be if I were to ask if there is a truth teller somewhere to your right?

for 12-16 truth tellers

What would your answer be if I were to ask if there is a liar somewhere to your right?

still need to work on the question for between 5-11 truth tellers

You're on track for the first question, but i have some question about the second

If there is between 1 - 4 truth tellers:

What would your answer be if I were to ask if there is a truth teller somewhere to your right?

Can you elaborate on an example of how this second question can help narrow down the position of the truth tellers? Let's say that the response to the first question is that there are 4 truth tellers in the 16. It seems to me that the second question (Is there a truth teller to your right) is redundant because we already know that there will be 3 YES.

Edited December 2, 2010 by bushindo

[phaze]

You're on track for the first question, but i have some question about the second

Can you elaborate on an example of how this second question can help narrow down the position of the truth tellers? Let's say that the response to the first question is that there are 4 truth tellers in the 16. It seems to me that the second question (Is there a truth teller to your right) is redundant because we already know that there will be 3 YES.

Sorry I meant anywhere to you right not immediately to your right

As you are asking to the group

if a truth teller is in position 1 you get 0 Yeses

If the first truth teller is in position 2 you get 1 yes

If the first truth teller is in position 16 you get 15 yeses

[phaze]

if the questions can be of any length and you can ask

"If I were to ask you if you are in the first 8 people in the row and the first person is a truth teller or if you are in position 9th to 12th and the second person is a truth teller or if you are in position 13 or 14 and the third person is a truth teller or you are the 15th person in the row and the forth person is a truth teller what would your answer be?"

The number of Yes you get back would vary between 0 -15

if you can subtract 8 the first person is truth teller

if you can subtract an additional 4 the second person is truth teller

...

you can do it 4 times for the entire row

...

Edit: Grammer

Edited December 3, 2010 by phaze

[bushindo]

if the questions can be of any length and you can ask

"If I were to ask you if you are in the first 8 people in the row and the first person is a truth teller or if you are in position 9th to 12th and the second person is a truth teller or if you are in position 13 or 14 and the third person is a truth teller or you are the 15th person in the row and the forth person is a truth teller what would your answer be?"

The number of Yes you get back would vary between 0 -15

if you can subtract 8 the first person is truth teller

if you can subtract an additional 4 the second person is truth teller

...

you can do it 4 times for the entire row

...

Edit: Grammer

Yes, the questions can be of any length, so there is no objection to cramming as much information into a question as possible. I have some comment on this solution

Suppose that there is only 1 truth teller in the 16, and he is arranged at position 2. Below is a diagram of the position so it's easier to follow the methodology

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  T  0  0  0  0  0  0  0  0  0  0  0  0  0  0

If we ask each of the 16 people your question:

"If I were to ask you if you are in the first 8 people in the row and the first person is a truth teller or if you are in position 9th to 12th and the second person is a truth teller or if you are in position 13 or 14 and the third person is a truth teller or you are the 15th person in the row and the forth person is a truth teller what would your answer be?"

Then the total number of YES relayed back to you would be 0. Since we can't really subtract 4 from 0 without going into the negative, then we won't be able to identify the second person as the truth teller.

Edited December 3, 2010 by bushindo

[phaze]

How do you get 0, If no2 is a truth teller and I was to ask just the question "if I were to ask you if you are in position 9th to 12th and the second person is a truth teller what would your answer be?" would I not get 4 yes?

NNNNNNNNYYYYNNNN

[bushindo]

How do you get 0, If no2 is a truth teller and I was to ask just the question "if I were to ask you if you are in position 9th to 12th and the second person is a truth teller what would your answer be?" would I not get 4 yes?

NNNNNNNNYYYYNNNN

Comment

So, suppose that we have the following configuration

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  T  0  0  0  0  0  0  0  0  0  0  0  0  0  0

where we only have 1 truth teller, and 15 naysayers. The naysayers will always say NO, regardless of what you ask. If you ask "if I were to ask you if you are in position 9th to 12th and the second person is a truth teller what would your answer be?", the naysayers in position 9th - 12th would say NO. The truth tellers in position 2 would also answer NO. Hope that clears it up.

[Guest]

Question 1: Are you a truth-teller?

Questions 2-6: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Explanations:

Observation 1: The first question is giving the number of truth-tellers. If there are no truth-teller, the problem is readily solved.

Observation 2: Number 'abcd'_B represents a number in base B such that 'abcd'_B = a*B^3 + b*B^2 + c*B^1 + d*B^0. Base 10 is implicit if the base not mentioned.

Observation 3: A k-combination of a set is a subset of k distinct elements of the set. If the set has n elements, the number of k-combinations is equal to the binomial coefficient

(n,k) = n! / ( k! * (n-k)! ).

Observation 4: Hereunder is a table with the following significance:

- first column represents the number k of truth-tellers (information received in the first question)

- second column represents the number of combinations (16,k)

- third column represents the number of combinations (16,k) in base B = k+1 indicated

As we can see, all numbers in the third column have no more than 5 base-B-digits

[1] [16] '10000'_2

[2] [120] '11110'_3

[3] [560] '20300'_4

[4] [1820] '24240'_5

[5] [4368] '32120'_6

[6] [8008] '32230'_7

[7] [11440] '26260'_8

[8] [12870] '18580'_9

[9] [11440] '11440'_10

[10] [8008] '6020'_11

[11] [4368] '2640'_12

[12] [1820] 'AA0'_13

[13] [560] '2C0'_14

[14] [120] '80'_15

[15] [16] '10'_16

[16] [1] '1'_17

Observation 5: A table of correspondences associates to each possible combination an order number . For instance, the table for (16,2) can be written as follows:

[ 1 2] #000 == '00000'_3

[ 1 3] #001 == '00001'_3

[ 1 4] #002 == '00002'_3

[ 1 5] #003 == '00010'_3

....

[14 15] #117 == '11100'_3

[14 16] #118 == '11101'_3

[15 16] #119 == '11102'_3

The table contains #000-#119, a total of 120 combinations.

The relevant such table of correspondences is given to the persons questioned with the phrase "Given the formalism, notations and lines of logic explained below". Therefore they are all aware of all notations.

Observation 6 (line of logic): The 16 persons are to be ordered (physically or only mentally) such that each truth-teller knows his position relative to all other persons and to all other truth-tellers. This position does not change during the questioning. The relevant information (referred to in the questions 2-5) is:

- for Question2: the last digit of the base B number representing the combination of positions of all truth-tellers

- for Question3: the fore-last digit of the base B number representing the combination of positions of all truth-tellers

and so on

Observation 7: Considering that the digit b is the relevant information, the phrase "would your answer have to be yes in order to convey me relevant information" should be understood as "are you among the first b truth-tellers from left to right?". Please notice that the persons themselves know digit b from the table, even if I don't.

EXAMPLE:

Suppose there are 3 truth-tellers in positions [14 15 16]

In the table of correspondences, it is given: [14 15 16] #560 == '20233'_4

Q1: Are you a truth-teller?

Result: 3 yes answers

Q2: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q2 translated for them: Are you among the first 3 truth-tellers from left to right?

Result: 3 yes answers

Q3: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q3 translated for them: Are you among the first 3 truth-tellers from left to right?

Result: 3 yes answers

Q4: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q4 translated for them: Are you among the first 2 truth-tellers from left to right?

Result: 2 yes answers

Q5: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q5 translated for them: Are you among the first 0 truth-tellers from left to right?

Result: 0 yes answers

Q6: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q6 translated for them: Are you among the first 2 truth-tellers from left to right?

Result: 2 yes answers

Other observations:

If there is 1 truth-teller, Q2-5 translate to "Is the last/fore-last/etc. bit of your position equal to 1?"

If there are 9 or more truth-tellers, there can also be a logic of conveying to the questioner a 16-bit number in which the positions of the truth-tellers is marked with bit 1.

Edited December 7, 2010 by Kornrade

[bushindo]

Question 1: Are you a truth-teller?

Questions 2-6: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Explanations:

Observation 1: The first question is giving the number of truth-tellers. If there are no truth-teller, the problem is readily solved.

Observation 2: Number 'abcd'_B represents a number in base B such that 'abcd'_B = a*B^3 + b*B^2 + c*B^1 + d*B^0. Base 10 is implicit if the base not mentioned.

Observation 3: A k-combination of a set is a subset of k distinct elements of the set. If the set has n elements, the number of k-combinations is equal to the binomial coefficient

(n,k) = n! / ( k! * (n-k)! ).

Observation 4: Hereunder is a table with the following significance:

- first column represents the number k of truth-tellers (information received in the first question)

- second column represents the number of combinations (16,k)

- third column represents the number of combinations (16,k) in base B = k+1 indicated

As we can see, all numbers in the third column have no more than 5 base-B-digits

[1] [16] '10000'_2

[2] [120] '11110'_3

[3] [560] '20300'_4

[4] [1820] '24240'_5

[5] [4368] '32120'_6

[6] [8008] '32230'_7

[7] [11440] '26260'_8

[8] [12870] '18580'_9

[9] [11440] '11440'_10

[10] [8008] '6020'_11

[11] [4368] '2640'_12

[12] [1820] 'AA0'_13

[13] [560] '2C0'_14

[14] [120] '80'_15

[15] [16] '10'_16

[16] [1] '1'_17

Observation 5: A table of correspondences associates to each possible combination an order number . For instance, the table for (16,2) can be written as follows:

[ 1 2] #000 == '00000'_3

[ 1 3] #001 == '00001'_3

[ 1 4] #002 == '00002'_3

[ 1 5] #003 == '00010'_3

....

[14 15] #117 == '11100'_3

[14 16] #118 == '11101'_3

[15 16] #119 == '11102'_3

The table contains #000-#119, a total of 120 combinations.

The relevant such table of correspondences is given to the persons questioned with the phrase "Given the formalism, notations and lines of logic explained below". Therefore they are all aware of all notations.

Observation 6 (line of logic): The 16 persons are to be ordered (physically or only mentally) such that each truth-teller knows his position relative to all other persons and to all other truth-tellers. This position does not change during the questioning. The relevant information (referred to in the questions 2-5) is:

- for Question2: the last digit of the base B number representing the combination of positions of all truth-tellers

- for Question3: the fore-last digit of the base B number representing the combination of positions of all truth-tellers

and so on

Observation 7: Considering that the digit b is the relevant information, the phrase "would your answer have to be yes in order to convey me relevant information" should be understood as "are you among the first b truth-tellers from left to right?". Please notice that the persons themselves know digit b from the table, even if I don't.

EXAMPLE:

Suppose there are 3 truth-tellers in positions [14 15 16]

In the table of correspondences, it is given: [14 15 16] #560 == '20233'_4

Q1: Are you a truth-teller?

Result: 3 yes answers

Q2: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q2 translated for them: Are you among the first 3 truth-tellers from left to right?

Result: 3 yes answers

Q3: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q3 translated for them: Are you among the first 3 truth-tellers from left to right?

Result: 3 yes answers

Q4: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q4 translated for them: Are you among the first 2 truth-tellers from left to right?

Result: 2 yes answers

Q5: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q5 translated for them: Are you among the first 0 truth-tellers from left to right?

Result: 0 yes answers

Q6: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q6 translated for them: Are you among the first 2 truth-tellers from left to right?

Result: 2 yes answers

Other observations:

If there is 1 truth-teller, Q2-5 translate to "Is the last/fore-last/etc. bit of your position equal to 1?"

If there are 9 or more truth-tellers, there can also be a logic of conveying to the questioner a 16-bit number in which the positions of the truth-tellers is marked with bit 1.

Good work, Kornrade. I was considering posting some hints since this question may go unanswered. Seems like that fear was unfounded. You solved the problem perfectly. Way to go, and welcome to the den!

Edited December 7, 2010 by bushindo

[k-man]

Wow! Good job, Kornrade, but that's one crazy solution! My head is still spinning. Bushindo, is this the solution you had in mind?

I never thought of a solution involving communicating tons of information to the answerers before asking the questions, but if this is allowed then can the problem be solved in 5 questions?

Kornrade's solution involves preparing tables of possible combinations of truth-tellers and assigning the numbers to each combination. The number is then communicated back digit-by-digit. The total number of combinations is 65536 - a 5-digit number. If we prepare a table of all possible combinations of truth-tellers and assign a number to each combination in a way to only use the digits that are less than or equal to the number of truth-tellers in that combination then we can prepare one table with all combinations. The combination number will embed the number of truth-tellers in it, so we don't need to ask the first question. We just give the answerers the table and they communicate back to us the number corresponding to the combination they are standing in.

The only question that I don't have the answer for yet is whether it's possible to represent all combinations using only the digits that are less than or equal to the number of the truth-tellers. For example, combinations with one truth-teller would have numbers 1, 10, 11, 100, 101, etc. assigned to them. These are decimal numbers, not binary. Based on the number of combinations for each number of the truth-tellers it seems that it can be done, but I haven't proven that yet. The complexity here is that once a number is used it cannot be used again. However, the combination number doesn't have to be in the range of 0-65535. It can be in the range of 0-99999.

EDIT: added some more thoughts

Edited December 7, 2010 by k-man

[k-man]

The table below contains the number of combinations (column 2) for each number of truth-tellers (column 1) and the running total of combinations (column 3).

1	16	16

2	120	136

3	560	696

4	1820	2516

5	4368	6884

6	8008	14892

7	11440	26332

8	12870	39202

9	11440	50642

10	8008	58650

11	4368	63018

12	1820	64838

13	560	65398

14	120	65518

15	16	65534

16	1	65535

The running total is what needs to be encoded using only the digits less than or equal to the number of truth tellers. So below table is the running totals converted to the corresponding base to verify that we are still within our 5 digit limit. For combinations with the number of truth-tellers >9 we can just use decimal representation.

1	10000

2	12001

3	22320

4	40031

5	51512

6	61263

7	63334

8	58687

9	50642

10	58650

11	63018

12	64838

13	65398

14	65518

15	65534

16	65535

So, this proves that every possible combination of truth-tellers can be assigned a unique 5-digit decimal number using only the digits equal to or less than the number of truth-tellers in the combination. The combination number can be communicated digit-by-digit in 5 steps.

[bushindo]

Wow! Good job, Kornrade, but that's one crazy solution! My head is still spinning. Bushindo, is this the solution you had in mind?

I never thought of a solution involving communicating tons of information to the answerers before asking the questions, but if this is allowed then can the problem be solved in 5 questions?

Kornrade's solution involves preparing tables of possible combinations of truth-tellers and assigning the numbers to each combination. The number is then communicated back digit-by-digit. The total number of combinations is 65536 - a 5-digit number. If we prepare a table of all possible combinations of truth-tellers and assign a number to each combination in a way to only use the digits that are less than or equal to the number of truth-tellers in that combination then we can prepare one table with all combinations. The combination number will embed the number of truth-tellers in it, so we don't need to ask the first question. We just give the answerers the table and they communicate back to us the number corresponding to the combination they are standing in.

The only question that I don't have the answer for yet is whether it's possible to represent all combinations using only the digits that are less than or equal to the number of the truth-tellers. For example, combinations with one truth-teller would have numbers 1, 10, 11, 100, 101, etc. assigned to them. These are decimal numbers, not binary. Based on the number of combinations for each number of the truth-tellers it seems that it can be done, but I haven't proven that yet. The complexity here is that once a number is used it cannot be used again. However, the combination number doesn't have to be in the range of 0-65535. It can be in the range of 0-99999.

EDIT: added some more thoughts

Kornrade's answer is what I had in mind when I made the puzzle. Kornrade's truth tellers got it easy; my truth tellers had to do more tons more work by calculating their own combinatorial numbers instead of having the bloody combination sheets handed to them . Nice work on reducing the limit to 5. Excellent job!

Edited December 7, 2010 by bushindo

[araver]

It looks insanely complicated, but does the trick.

Kudos Kornrade .

And welcome to the den! I'm looking forward to reading your contributions.

[Guest]

Thanks everybody (and nice reduction k-man!)

I already posted one of my all-time favourites (I'm curious how fast you can get to the bottom of it):

[Guest]

One little addendum, if I may:

k-man's reduction to 5 questions is based on the assumption that the truth tellers know each other beforehand. If so, the reduction is correct.

Otherwise, we still need Q1 "Are you a truth teller?" to let them identify themselves before communicating their positions.