# Choosing a leader from 3 groups of students

At a class, the students are going to choose a leader. The class has 3 groups of students, and each group contains 4 students, so the total number of students is 12. After discussion, they determine the following rule:

each student has to vote 1 from each group (so each student has to vote for 3 persons).

For example, if the groups are [a,b,c,d] [e,f,g,h] [i,j,k,l], then each student has to choose 1 from [a,b,c,d], 1 from [e,f,g,h], and 1 from [i,j,k,l].

If someone breaks the rules, their vote is disqualified.

(To simplify the problem, let's write just the initials of the students, since no 2 students have the same initials.)

 1. [c,d,f]     2. [a,g,c]     3. [d,h,l]    4. [b,e,d]
5. [f,j,g]     6. [g,j,i]     7. [j,i,a]    8. [j,a,f]
9. [b,h,k]     10.[l,c,d]     11.[a,h,l]    12.[g,e,b]


There is 1 vote which is disqualified.

The questions:

• Determine each group's members.
• Determine which vote is disqualified.

The groups are

Group 1: A, D, G, K
Group 2: C, E, H, J
Group 3: B, F, I, L

and the disqualified vote is

vote 2 (A,G,C).

My method:

Start by putting D, H, and L in groups 1, 2, and 3 respectively, because of vote 3.
Vote 11 (A,H,L) implies A must also go in group 1.
Vote 10 (L,C,D) implies C has to go in group 2.
Vote 1 (C,D,F) implies F has to go in group 3.
Vote 8 (J,A,F) implies J has to go in group 2.
Vote 7 (J,I,A) implies I has to go in group 3.
Vote 5 (F,J,G) implies G has to go in group 1.
Vote 4 (B,E,D) forbids B from being placed in group 1, and vote 9 (B,H,K) forbids B from being placed in group 2, so B must go in group 3.
Vote 4 (B,E,D) implies E has to go in group 2.
Vote 9 (B,H,K) implies K has to go in group 1.
Vote 2 (A,G,C) is disqualified because it contains two people from the same group (A and G in group 1).

At the suggestion of @Matsmath, if we started with the disqualified vote:

D, H, and L must go in groups 1, 2, and 3 respectively, due to vote 2.
Votes 3 (D,H,L) and 11 (A,H,L) imply that D has to go in group 1.
Vote 10 (L,C,D) implies that L has to go in group 2.
Vote 11 (A,H,L) implies that H has to go in group 3.
Vote 1 (C,D,F) implies that F has to go in group 2, but this contradicts vote 5 (F,J,G), which forbids F from going in group 2 due to G already being there.

• You should address the case when you start with an incorrect vote. – Matsmath Sep 10 '16 at 23:12
• @Matsmath Added! – DooplissForce Sep 10 '16 at 23:19
• No, I am afraid you misunderstood me. You consider the case that vote X (I am not spoiling what is X in your answer) is not disqualified, and you start forcing cases and teams and then reach a conclusion. My suggestion was to consider what would have happened, if vote X would have been the disqualified vote. Noone told you that there is a single solution to the puzzle. – Matsmath Sep 10 '16 at 23:42
• In a similar vein, your deduction looks like "Vote 11 (A,H,L) implies A must also go in group 1.". But vote 11 could be disqualified, so you can't deduce anything from it alone. – ffao Sep 11 '16 at 0:48
• "Determine which vote is disqualified." We are told that one vote only is not counted, in the question. – Nij Sep 11 '16 at 20:49

An alternative route to the answer:

Any two students who are both mentioned in two or more votes are in different groups: at least one of those votes is valid. This applies to $b, e (4, 12); c, d (1, 10); d, l (3, 10); h, l (3, 11); a, j (7, 8); f, j (5, 8); g, j (5, 6)$; and $i, j (6, 7)$.

So in particular, none of $a, f, g, i$ is in the same group as $j$. So $a, f, g, i$ are collectively in only two groups (those groups that do not contain $j$). In particular, at least two of $a, f, g$ are in the same group. Now $2$ implies that $a, g$ are in different groups; $5$, $f, g$; $8$, $a, f$. Therefore $2, 5$ or $8$ is the invalid vote. Therefore $6, 7$ are valid, so $i$ is in a different group from $a, g$. Thus one group contains $j$, another contains $i$ and another contains $a$ and $g$, so vote $2$ is invalid. Following DooplissForce, label the groups

Group 1: a, g
Group 2: j
Group 3: i

By $5, f$ is in 3.

Group 1: a, g
Group 2: j
Group 3: f, i

Vote $1, [c, d, f]$ implies that group 3, containing $f$, excludes $c, d$. Similarly, votes $1, 11, 12$ imply:

Group 1: a, g but not b, e, h, l
Group 2: j
Group 3: f, i but not c, d

So group 1 contains two of $c, d, k$. By $1$ it does not contain both $c, d$, so it contains one of those, and $k$. Group 2 contains the other of $c, d$. So, by $10, l$ is in 3.

Group 1: a, g, k, c/d
Group 2: j, d/c
Group 3: f, i, l

So there are two places in group 2 and one in group 3 for $b, e, h$. By $4, 9$, $b$ is neither with $e$ nor with $h$. Thus $b$ is in 3 and $e, h$ are in 2:

Group 1: a, g, k, c/d
Group 2: e, h, j, d/c
Group 3: b, f, i, l

Finally, by $3$, $d$ is not with $h$ in $2$ and is thus in $1$, and $c$ is in $2$:

Group 1: a, d, g, k
Group 2: c, e, h, j
Group 3: b, f, i, l

• This is better as it is more rigorous, addressing the concerns of Matsmath and ffao in the DooplissForce's answer. – justhalf Sep 13 '16 at 2:28

My way of thinking:

even if one of votes 5, 6, 7 or 8 is the invalid vote, we can deduce from the other three that group 1 has J, group 2 has A and G, and group 3 has F and I.
From this we immediately know, that it is vote 2, which is invalid, and all the rest can be used for deduction.
From votes 3 and 11 we know that D is in the same group as A, that is group 2.
Vote 1 makes C belong to group 1.
Vote 10 makes L belong to group 3.
Vote 11 makes H belong to group 1.
At this point we have B, E and K left, and one room in each group.
Vote 12 makes K belong to the same group where G is - group 2.
Vote 9 makes B belong to group 3.
And E has to be in group 4.

Groups:

{A, D, G, K}
{B, F, I, L}
{C, E, J, H}

Invalid Ballot

Number 2

Work:

Make a list of all pairs which appear on two ballots. AJ, BE, CD, DL, FJ, GJ, HL, IJ must be in different groups.
Those pairs mean ballots 3,5,6,7,8, & 10 are fully valid.
Ergo Groups are: {J}, {FI}, {AG}
Because of {AG}, ballot #2 is corrupt and all other information is valid.
At this point groups are: {J}, {FI}, {AG}
Because of Ballots 10+1: {J}, {FIL}, {AG}
Because of Ballots 11: {JH}, {FIL}, {AG}
Because of Ballots 3: {JH}, {FIL}, {AGD}
Because of Ballots 1: {JHC}, {FIL}, {AGD}
Because of Ballots 9+12: {JHC}, {FILB}, {AGD} ...(B is diff from G & H)
Because of Ballots 4: {JHCE}, {FILB}, {AGD}
Because of Ballots 9: {JHCE}, {FILB}, {AGDK}