11
$\begingroup$

A group of 10 students in a summer learning camp (fun times!) is asked to complete a brief survey to help them determine which of their new classmates they're most compatible with. The survey lists 10 subjects (math, science, English, art, history, band, gym, biology, shop, and home ec) and asks respondents to mark each subject as "like" or "dislike".

Once all 10 students have completed the survey, the teacher calculates an "affinity" score for each pair of students. The affinity between two students is the total number of subjects both students marked "like". Hence if Bill liked only "science", "art", "gym"; Jane liked only "science", "gym", and "history"; and Tara liked only "science", "history", "band", and "English", the affinity between Bill and Jane would be 2, the affinity between Bill and Tara would be 1, and the affinity between Jane and Tara would be 2.

The teacher writes the affinity scores for all 45 pairs of students on the board, then addresses the class.

I'm pleased to see that every student likes at least one subject, and I've noticed that no two students like exactly the same set of subjects. What I find bizarre, though, is that all of your affinity scores are even numbers. I've never seen that happen before. I'm wondering if it might be because the total number of 'likes' over all your surveys is 50 out of 100 possible; exactly half.

Hearing this, a particularly math-savvy student, Keenan Byonde, puts up his hand and explains,

Actually, it's because 50 is part of the arithmetic sequence $10 + 8n ; 0 \le n \le 10$. It's a simple matter to come up with 11 sets of ten responses to this survey such that each set has the properties:

  • each respondent likes at least one subject;
  • no two respondents like exactly the same subjects;
  • all 45 affinity scores are even; and
  • the total number of 'liked' subjects is a number in the arithmetic sequence.

Intrigued, the teacher asks Byonde to come up to the board, give an example set of ten survey responses with 50 total 'likes' and the stated properties, and explain how to (easily) contrive a set of survey responses with $10 + 8n$ total 'likes' and the stated properties for $0 \leq n \leq 10$.

What example and what simple procedure should Byonde write on the board to prove he's correct?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Absolutely love the wordplay in the title. You, sir, deserve more upvotes! $\endgroup$
    – CodeNewbie
    Jul 22, 2015 at 3:36
  • $\begingroup$ I'm not sure I agree. In order to construct this data for the survey, prior knowledge of the students' favourite subjects must exist. If you know nothing about the favourite subjects of your students, you will not be able to compile a survey. For instance, suppose there are 20 subjects, 10 of which are not liked by any of your students. If you chose to create your survey from these 10, you would get only negative responses. $\endgroup$
    – Ian MacDonald
    Jul 22, 2015 at 15:15
  • $\begingroup$ @IanMacDonald: The puzzle lies in contriving a set of responses that has the given property, not in contriving a survey whose responses are guaranteed to have the property. In other words, if you could fill out all ten surveys yourself any way you wanted to, how would you fill them out such that all the listed conditions are met. $\endgroup$
    – COTO
    Jul 22, 2015 at 16:27
  • $\begingroup$ I see. So this math-savvy student's outburst is only tangentially related to the statements the teacher makes. To directly address the teacher's wonder, it is because the total number was 50 out of 100, but because 50 is part of the arithmetic series, not because it's exactly half. $\endgroup$
    – Ian MacDonald
    Jul 22, 2015 at 16:54
  • $\begingroup$ @IanMacDonald: The teacher was succumbing to the "correlation = causation" fallacy. He'd never before seen a set of all-even affinities and he'd never before had exactly half of all subjects marked 'like'. He wondered out loud whether the latter was the cause of the former. But it turns out that the two conditions (all-even affinities, 50 total likes) aren't related in this way. The most we can say is that if the total number of likes is one of 10, 18, ..., 90, we can contrive a set of surveys with all-even affinities (and the other two properties) that has this total number of likes. $\endgroup$
    – COTO
    Jul 22, 2015 at 18:54

2 Answers 2

Reset to default
7
$\begingroup$

Divide the 10 students into 5 pairs. Assign each student a different favorite subject.

If each student only likes their favorite subject, then there are a total of 10 "likes" and no affinities. To add 8 "likes", choose two pairs to meet each other. When two pairs meet, each student "like"s the favorite subjects of the other pair (four students each adding two likes). There are ten pairs of pairs. When they have all met, there are 90 "likes": every student likes every subject except their partner's favorite, and all affinity scores are 8.

Diagram: black squares are initial likes, more likes can be added in groups of 8 squares with the same number.

Diagram

Each student always likes their own favorite subject and never likes their partner's favorite subject. Any other student who likes the first student's favorite subject must also like the partner's favorite subject, so no two students ever like exactly the same subjects.

The affinity between two students in the same pair gains 2 for every pair they meet.. The affinity between two students in different pairs gains 2 for every pair they have both met, plus 2 if they have met each other (from them liking each other's favorite subjects). Because all affinities only go up in increments of 2, they are all even.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ All correct. What's intriguing is that I came up with the exact same strategy in a totally different way, using totally different logic. Well done. $\endgroup$
    – COTO
    Jul 22, 2015 at 12:45
  • $\begingroup$ @COTO mind sharing your logic? $\endgroup$
    – f''
    Jul 22, 2015 at 12:51
  • 1
    $\begingroup$ I built the problem up around the solution, which was to find an orthogonal matrix in $\mathcal{M}\left( \mathbb{Z}_2\right)$. The obvious starting point is the identity matrix. Playing around with inverting blocks of various sizes quickly yielded that the inversions had to be symmetric about the diagonal, have even width and height, and that two or more inversions could only overlap by an even number of rows/columns. This led me to the conclusion that the ten blocks you have color-coded were the smallest irreducible blocks that could be inverted, each of which adds 8 1's. $\endgroup$
    – COTO
    Jul 22, 2015 at 13:13
2
$\begingroup$

Posting this as I don't have time to finish. Either I'll come back to finish it later or someone else will take it and run with it.

Label students $s_1...s_{10}$, and classes $c_1...c_{10}$.

For $n=10$, assign $s_i$ to $c_i$. Each student likes one class, each affinity is zero, no students like the same set of classes.

To extend to $n=18$, assign as before except $s_1...s_4$ are each assigned one of the four combinations of three elements from $c_1...c_4$. These students will all have a mutual affinity of 2.

This suggests the general method: to add more likes, take a set of $m$ students and classes such that $m$ is even and have each student like one of the $m-1$ distinct combinations of $m-1$ classes. If $m=4,6$ we may add a second group of 4.

N       Combination
10      None
18      4
26      4,4
34      6
42      6,4
58      8
90      10

At this point we throw our chalk at the blackboard in disgust.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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