- Joined
- 26 Apr 03
- Moves
- 26771
06 Sep 11
Originally posted by JS357The final configuration is when all the pairs where at least one of the pair said the other was a liar have been removed.
I'm not sure what the dispute concerns. Is "final configuration" the arrangement of Ls and Ts after a round has been completed and all but the pairs of people reporting "TT" about one another have crossed off the list? If you add back only one LT pair to it, of course that one pair would have been the only one eliminated in that round.
- Joined
- 26 Apr 03
- Moves
- 26771
06 Sep 11
Originally posted by JS357Good post JS357, I agree. The rotation by ceiling(N/2 + 1/2) does not guarantee to finish the game at round 2.
I think there is not a specific number of spaces to rotate the pairings, that ends the game at round 2 for all arrangements of A’s and B’s.
I'm going with 11 A’s and 9 B’s out of laziness.
Look at the following:
ABABABABAB
ABABABABAA
Becomes:
ABABABABA
ABABABABA
Now arranged in a circle, we can see that there are two A's next to one another, ...[text shortened]... ents of A’s and B’s.
Alternating odd and even rotations from round to round might be best.
However I suspect it ensures that at least floor(N/2) pairs are removed on each round, so it has the least bad "worst case".
- Joined
- 29 Dec 08
- Moves
- 6788
06 Sep 11
Originally posted by PalynkaGood. I am wondering about that. After the solo LT is crossed off, leaving each of the Ls paired with another L, and each of the T's paired with another T, the asker applies a simple pairing method that shifts the people in one circle S persons to the right or left, where S is less than the number of pairs. (S could vary from round to round) How does this avoid creating at least two LTs? After all, whenever you create one LT, you break up one pair of Ls and one pair of Ts. That's where they are. And given that there is one more TT pair than LL pair, you WILL shift people out of matched pairs.
Yes, but that I can find one means that it exists so it could be the WCS...
06 Sep 11
Originally posted by JS357You're correct, I meant the two pairs (not the one pair, that's impossible like you correctly point out). I still don't see that shifting one or two or N/2 is different in any relevant way, though. I like the way you put in in another post. By putting the remaining pairs in a circle, we see that there's nothing fundamental about their position, since we don't know which pairs are L or T. If you take configuration C1 and shift them one position we get CF. But I can also find a configuration C2 that when I shift them two positions also get CF, and so on and so forth.
Good. I am wondering about that. After the solo LT is crossed off, leaving each of the Ls paired with another L, and each of the T's paired with another T, the asker applies a simple pairing method that shifts the people in one circle S persons to the right or left, where S is less than the number of pairs. (S could vary from round to round) How does this avoi ...[text shortened]... given that there is one more TT pair than LL pair, you WILL shift people out of matched pairs.
- Joined
- 26 Apr 03
- Moves
- 26771
06 Sep 11
Originally posted by iamatigerProved myself wrong with a simulation:
Good post JS357, I agree. The rotation by ceiling(N/2 + 1/2) does not guarantee to finish the game at round 2.
However I suspect it ensures that at least floor(N/2) pairs are removed on each round, so it has the least bad "worst case".
e.g. for 11 pairs:
BBBAAABBAAA
BBBAAABBAAA
This goes to
ABBAAABBBAA
BBBAAABBAAA
which only gets rid of the minimum 2 pairs
Now I am wondering whether some combination of two consecutive shuffles can be found that has optimum worst case elimination.
- Joined
- 29 Dec 08
- Moves
- 6788
06 Sep 11
Originally posted by iamatigerOh s**t I am getting right back into this. At least the wife's not home.
Proved myself wrong with a simulation:
e.g. for 11 pairs:
BBBAAABBAAA
BBBAAABBAAA
This goes to
ABBAAABBBAA
BBBAAABBAAA
which only gets rid of the minimum 2 pairs
Now I am wondering whether some combination of two consecutive shuffles can be found that has optimum worst case elimination.
Different things that you and Palynka have said make me wonder about suggesting this question. Is every arrangement of As and Bs that we can imagine, reachable using the pairing rule under examination on some initial arrangement? Palynka talked about reverse engineering, but I think he was not suggesting that the location of already-removed LT pairs can be imputed by examination of the arrangement and the pairing rule. (That would be the "route" of reverse engineering the genetic trail.)
You found an arrangement that does not yield much material to that pairing rule, but is it reachable?
The arrangement you discuss here looks unreachable from the putative WCS starting arrangement which is, IIRC, a string of LL pairs, a string of TT pairs, and an LT pair tucked in somewhere. The process we are examining looks something like snipping teleomeres, and the fewer of them, the better. It may be that the arrangement you are discussing in this post is reached quickly from some woefully suboptimal starting position, and so, is excusable. It may also be that it is woefully suboptimal a few iterations later.
Its also making me think about cellular automata, which is another great way to burn up time. 🙂
- Joined
- 29 Dec 08
- Moves
- 6788
07 Sep 11
Originally posted by PalynkaI've tried to create an example of a seven-pair CF with two more A's than B's, produced from a C1 shifted once, and also from a C2 shifted twice, remembering that C1 and C2 have had their AB and BA pairs already crossed out. Haven't succeeded yet, but need to stop, suddenly. Wife home.
You're correct, I meant the two pairs (not the one pair, that's impossible like you correctly point out). I still don't see that shifting one or two or N/2 is different in any relevant way, though. I like the way you put in in another post. By putting the remaining pairs in a circle, we see that there's nothing fundamental about their position, since we don' ...[text shortened]... configuration C2 that when I shift them two positions also get CF, and so on and so forth.
- Joined
- 26 Apr 03
- Moves
- 26771
07 Sep 11
Originally posted by JS357I was thinking of a starting position like:
Oh s**t I am getting right back into this. At least the wife's not home.
Different things that you and Palynka have said make me wonder about suggesting this question. Is every arrangement of As and Bs that we can imagine, reachable using the pairing rule under examination on some initial arrangement? Palynka talked about reverse engineering, but I think h ...[text shortened]... also making me think about cellular automata, which is another great way to burn up time. 🙂
BBBAAABBBAAA
BBBAAABBAAAA
(each item above another is paired with it)
Here there are two more As than Bs, which is consistent with our initial 100 puzzle, I am only working with 22 people though, because I can explore all the combinations if I do that.
- Joined
- 26 Apr 03
- Moves
- 26771
07 Sep 11
2 edits
I am also wondering whether we are still throwing away some useful information.
We know that the pairs we retain match: They must either both be liars or both be truth tellers.
Say person A matches with Person B:
On the next round we question pairs AC and BD,
If AC and BD match, we can make the union set ABCD, and we know the people in this set must all match.
The sets tend to increase in size (as a proportion of the total remaining pool) on each round. They increase fastest when we have thrown out fewest pairs in a round.
We can potentially use the information about these sets in two ways:
1) If, later in our search, we make the pair AD, we don't have to ask that pair a question because we know they both match as they are both in the same set.
2)If at some point a set contains more than half of the total pool then we know that set must contain only truth tellers and we can halt.
07 Sep 11
1 edit
Originally posted by iamatigerThis sounds good to me! That's an excellent reason why the sequence of shift sizes matters... Glad to be wrong. Again.
I am also wondering whether we are still throwing away some useful information.
We know that the pairs we retain match: They must either both be liars or both be truth tellers.
Say person A matches with Person B:
On the next round we question pairs AC and BD,
If AC and BD match, we can make the union set ABCD, and we know the people in this set n half of the total pool then we know that set must contain only truth tellers and we can halt.
Also, if we take care not to match ABCD with each other, the group then either doubles size or we manage to eliminate at least one pair out of 4. This seems like it could work relatively fast.
I'm still confused, though! Working on that system. Pair up, eliminate liars and keep only one of each pair. First, 50 questions leaves us with (25,24) TL.
51 49 0
50 48 50
25 24 0
We can pair now, but we need to leave one out. If we leave a T then it's possible they all pair but then we know the left out is T, or we eliminate an even number of pairs, which means we also know that the left out is T*. If we leave a L out, then we get at least one pair. Only one pair means that we know remainder must be a L. So WCS we eliminate one LT pair+one L. Keep representatives, iterate. This is the sequence I get.
24 22 24
12 11 0
Ok, now it's slightly different as the odd number is of L, not T. If we leave T out, we get at least one pair. If we leave a L out then we can get no pairs. This doesn't seem so good, but we can still remove the L left out and take representatives.
12 10 10
6 5 0
Same here.
6 4 5
3 2 0
3 1 2
And now we have a matched pair that must be TT.
So using a variation of your rounding up method I get 91 questions...
*Still need to check that this isn't the WCS, so we could be removing more now at the expense of a potentially less nice ordering. Don't have time now, though... Edit - In that case, if we eliminate an even number of pairs, then we know the left out was a T, right?
- Joined
- 29 Dec 08
- Moves
- 6788
07 Sep 11
Originally posted by iamatiger
I was thinking of a starting position like:
BBBAAABBBAAA
BBBAAABBAAAA
(each item above another is paired with it)
Here there are two more As than Bs, which is consistent with our initial 100 puzzle, I am only working with 22 people though, because I can explore all the combinations if I do that.
I was thinking of a starting position like:
BBBAAABBBAAA
BBBAAABBAAAA
...Here there are two more As than Bs,
I only see one of them.
- Joined
- 29 Dec 08
- Moves
- 6788
07 Sep 11
Originally posted by iamatigerThis is interesting.
I am also wondering whether we are still throwing away some useful information.
We know that the pairs we retain match: They must either both be liars or both be truth tellers.
Say person A matches with Person B:
On the next round we question pairs AC and BD,
If AC and BD match, we can make the union set ABCD, and we know the people in this set ...[text shortened]... n half of the total pool then we know that set must contain only truth tellers and we can halt.
The following might be implicit in the work you and Palynka are already doing.
Another thing you can do if you have two groups of people, each reporting all the other members of their group T, is to take one person from each group and pair them. If one is a truther and one a liar, the truther will report the liar and you can eliminate both groups on the answers to just 1 or 2 questions (this implies sticking to the original overall strategy.) If they both report T you can combine the two groups on just the 1 or 2 questions; in this case they are all either truthers or liars. I think.
- Joined
- 26 Apr 03
- Moves
- 26771
07 Sep 11
9 edits
Here is an algorithm that I think is optimal.
0.1Maintain two sets: Questioned and Free
0.2Initially Questioned is Empty and Free contains all the people.
0.3 Initialise THRESHOLD to N_Liars + 1
0.4 Repeat the following until halt is reached:
{
a) If there are only two people left in Questioned + Free then HALT (they are both truth tellers)
b) If there are THRESHOLD people in Questioned then HALT (all in Questioned are truth tellers).
c) If Questioned is empty, choose a random person from Free and move him to Questioned
d) Define the preferred set as the larger of Questioned and Free
e) Choose one random person from Questioned, and one Random Person from Free
f) Ask the person from the preferred set "Is the other person a liar?".
f.1) If the answer is YES, then remove the two people from their respective sets, discard them and decrement THRESHOLD.
f.2) If the answer is NO then ask the remaining person "IS the other person a liar?"
f.2.1) If the answer to the new question is YES, then remove the two people from their respective sets, discard them and decrement THRESHOLD.
f.2.2) If the answer to the new question is NO, then move the person who is currently in Free to Questioned.
}
I think this has a worst case of 2(N-3) questions
Giving an answer of 194 questions, worst case, for 49 liars + 51 truth tellers.
The above benefits greatly from JS357's method of finding TT FF pairs, many thanks JS!
- Joined
- 26 Apr 03
- Moves
- 26771
07 Sep 11
3 edits
Originally posted by PalynkaFirst, 50 questions leaves us with (25,24) TL.
This sounds good to me! That's an excellent reason why the sequence of shift sizes matters... Glad to be wrong. Again.
Also, if we take care not to match ABCD with each other, the group then either doubles size or we manage to eliminate at least one pair out of 4. This seems like it could work relatively fast.
I'm still confused, though! Working on tha case, if we eliminate an even number of pairs, then we know the left out was a T, right?
There is a max of 100 initial questions rather than 50, if a pair is TT, FF, or FT (F asked first) then that pair takes 2 questions to categorise, 1 per person.
Then you have 48 people, but you don't know what they are, so you need another 48 questions, then 24 then 12, then 6...
If N questions is then 3 & 1 it comes to 194, which is the same as my algorithm above, but I think you may only need two final questions, so you **may** beat me by two, I'm not sure, maybe I'll have to simulate both approaches....