1
$\begingroup$

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.)

Here are the votes:

 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.
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You should address the case when you start with an incorrect vote. $\endgroup$ – Matsmath Sep 10 '16 at 23:12
  • $\begingroup$ @Matsmath Added! $\endgroup$ – DooplissForce Sep 10 '16 at 23:19
  • $\begingroup$ 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. $\endgroup$ – Matsmath Sep 10 '16 at 23:42
  • 1
    $\begingroup$ 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. $\endgroup$ – ffao Sep 11 '16 at 0:48
  • $\begingroup$ "Determine which vote is disqualified." We are told that one vote only is not counted, in the question. $\endgroup$ – Nij Sep 11 '16 at 20:49
7
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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}

$\endgroup$

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.