6
$\begingroup$

You are the math teacher at a high school and you are in charge of organizing Student Council for the whole school next year. Your boss, the Principal, read a research paper on Student Councils and made some crazy demands:

MORE OPPORTUNITY : There will no longer be one Student Council but instead we will have many of them over the course of the year

FAIR REPRESENTATION : No more elections. All students are assigned to Student Council by you. Each student must have equal time serving at the end of the year

GOOD PROPORTIONS : The only acceptable ratio of Total Students to the size of any Student Council is 17 to 1

EVEN MIXING : Each student council, when compared to any other student council, must have exactly 3 students in common. Pick any two Councils randomly from the year and they must share exactly 3 members

You think the Principal is taking the research too literally, but as luck would have it, all his demands are possible to satisfy

Question: How many students attend your school?

Edit...

Bonus Question: Is that the only possible answer? You will need to do a good job explaining why

$\endgroup$
1
  • $\begingroup$ I may have screwed up in thinking the answer had to be unique. This shouldn't effect who receives the check mark for answering correctly, but I'd like to hold off until I feel a little better about it. $\endgroup$
    – Skosh
    May 22, 2019 at 14:27

5 Answers 5

6
$\begingroup$

I think (if I have not miscalculated again) the total number of students is

$17 * 99 = 1683$

This is just one of the solutions. There might be others. I have not proved that each student has to participate in exactly 2 Councils - I just assumed it for simplicity.

Reasoning (updated for clarity)

Lets set $X$ be the size of the Student Council and assume each student participates in 2 Councils. Then the total number of students is $17X$.

Lets call a freshman a student who have not served on a Council yet and lets form Councils by the following method:

1st: $X$ freshmen
2nd: $(X - 3)$ freshmen $+ 3$ students from the 1st Council
3rd: $(X - 6)$ freshmen $+ 3$ students from the 1st $+ 3$ students from the 2nd Council
...
$K$th: $(X - 3(K-1))$ freshmen $+ 3$ students from each previous $(K-1)$ Council who have not served twice yet.

At some point we should reach the state when there are no more freshmen left, so that $K$th Council (the last one) is only formed from the students who have already served once. That means that the number of freshmen in the $K$th Council is equal to zero.

$X - 3(K-1) = 0$, hence $X = 3K - 3$

Now let's count the total number of students using our process of forming Councils. This number is equal to the sum of all freshmen used in each Council formation:

$X + (X - 3) + ... + (X - 3(K - 1)) = $

$KX - (0 + 3 + 6 + ... 3(K - 1)) = $

$KX - 3K(K-1)/2$

So here is the equation for the total number of students.

$KX - 3K(K-1)/2 = 17X$ or

$3K^2 - (2X + 3)K + 34X = 0$

Substituting $X = 3K - 3$, we get a quadratic equation for $K$.

$K^2 - 35K + 34 = 0$

Solving it for $K$, and noting that and $K > 1$, we get

$K = 34$, $X = 99$

Here is an answer to the bonus question. I used @Thomas Blue excellent formula connecting number of students per Council with the number of Council stints each student has to serve. @Thomas Blue deserves a full credit for the solution. I wrote a simple minded program to find an assignment of students to Councils based on the number of stints each student has to serve. Here are the results.

The solution to the puzzle is not unique! There is at least one more possible answer in addition to the one I found earlier.

To simplify the calculation I split the total number of students into non intersecting groups of $3$ and assumed that each group always serves on a Council together. This is just an assumption - no proof. It worked for me in the case when the number of stints per student was $2$, so I decided to try it again.

With this assumption we need to find an assignment of groups to Councils so that any 2 Councils have exactly one group in common.

According to @Thomas Blue formula the possible number of stints are

$2, 3, 4, 5, 7, 9, 13, 17, 25, 49$

I was able to find an additional solution for $5$ stints with $63$ students per Council and total number of students being $1071$. That makes $357$ groups. Here is a link to the assignment matrix https://drive.google.com/file/d/19yrdLUI7enEFlQQY32cSh1Wnd2XM3OJX/view?usp=sharing

I was not able to find solutions for stint values other than $2$ and $5$. Though I cannot prove they do not exist.

$\endgroup$
4
  • $\begingroup$ Your construction for building each council works, and seeing as you arrived at the right answer, I must assume you didn't make up everything in the middle. KX-3K(K-1)/2=17X and X=3K-3 don't seem obvious to me and I was hoping you could explain how/why you made them. $\endgroup$
    – Skosh
    May 22, 2019 at 17:11
  • 1
    $\begingroup$ @DarkThunder, I tried to clarify my reasoning. I'll be happy to provide more details if necessary. Please let me know. Thanks for the great puzzle! Do not know the answer for the bonus question yet. $\endgroup$
    – ppgdev
    May 22, 2019 at 18:13
  • $\begingroup$ I added an answer to the bonus question. Full credit goes to @Thomas Blue for his great formula. $\endgroup$
    – ppgdev
    May 22, 2019 at 22:23
  • $\begingroup$ Amazing! I can't really back-check that too thoroughly but I'm convinced. I'm not done thinking about this by a long shot, but I would like to note that we both group the students into 3's. I can imagine not doing that, but I never got it to work. Assuming that's an important aspect of any solution, it would mean the total students must be divisible by three, and this would eliminate half of the list from the running. $\endgroup$
    – Skosh
    May 23, 2019 at 14:23
4
$\begingroup$

Partial:

Let D be size of a single council (17D be amount of students), n be amount of times a single student serves his due. Then amount of councils will equal (17D*n)/D = 17n. (I calculated amount of all student servings and divided by the size of a council).
Let's count amount of pairs of the kind "the student serves in this council - the same student serves in different council".
First, it will be 17D*n(n-1)/2, since every student produces n(n-1)/2 such pairs. Secondly, it will be 3*(17n)*(17n-1)/2, since each pair of councils produces exactly three such pairs.
Now, we have an equality 17Dn(n-1)/2 = 3*17n(17n-1)/2 which we convert to D = 3(17n-1)/(n-1) = 51 + 48/(n-1).

I expected to get more information out of it. Anyway, now we now that n-1 is a divisor of 48, so there is, at least, finite amount of answers :)

$\endgroup$
3
  • $\begingroup$ Great observation, +1! $\endgroup$
    – ppgdev
    May 22, 2019 at 18:43
  • $\begingroup$ @DarkThunder, I used Thomas Blue formula to answer the bonus question. His answer deserves a full credit for it. $\endgroup$
    – ppgdev
    May 23, 2019 at 1:33
  • $\begingroup$ This insight defines the # of total students and council size for a given number of times each student serves. That's incredibly informative. I'm suspecting other factors further reduce the list, but I've found nothing concrete. $\endgroup$
    – Skosh
    May 23, 2019 at 14:27
0
$\begingroup$

I believe you have

102 students in the school.

Since

the ratio must be 17:1, the options for total numbers of students must be multiples of 17. Since 3 students must be in common in each council, the minimum number is 17x4 = 68 (because if it were 17x3 = 51, all three must be on the council each time and no new students could rotate in) If there are 68, the first council will have 4 members, and there will be 64 students left over. One new student will join the council each time, and this process will run through all the remaining students. But students must have equal time, and at the end two students will have served on one council, and all the rest will have served on three. The way to fix this issue is take 17x6= 102 students. The council will then have six members, half of which will be rotated out for each service term. Each student will serve on two councils, with the first three to rotate off the first council joining the last council with the last three to join the penultimate council. This will require 33 student councils throughout the year, and based on an 183 day school year, each council will be appointed for roughly 5 and a half days.

edited to fix a spoiler tag

$\endgroup$
3
  • 1
    $\begingroup$ I believe you have solved for the case where all adjacent councils share 3 members, but it's EVERY council that shares 3. Maybe I can edit the question to make that a little more clear. $\endgroup$
    – Skosh
    May 21, 2019 at 22:14
  • $\begingroup$ Ah, I misunderstood the condition. For clarification, every council shares three students with every other council then? $\endgroup$
    – JProblems
    May 21, 2019 at 22:18
  • $\begingroup$ Correct. Good luck! $\endgroup$
    – Skosh
    May 21, 2019 at 22:29
0
$\begingroup$

Answer:

There are 323 students, each serving 3 times on a 19 member student council.

Reasoning:

There are 17 times as many students (N) as there are places on the council (X).
i.e. N = 17X

For any given student council there are C = X(X-1)(X-2)/6 ways to permute three members from it, satisfying the three in common requirement for all other councils.

Given the requirement that each student serves on the same number of councils we know that dividing C by N must be an integer.

Since 17 is prime, the lowest integer solution for X is 19, because that gives 19-2 in the above calculation.

Hence:
X=19
N=17 x 19 = 323
C=(19 x 18 x 17)/ 6 = 969

$\endgroup$
2
  • $\begingroup$ I guess the thing is you need to convince me that each council must contain 3 members in common with each other. $\endgroup$
    – Skosh
    May 22, 2019 at 15:16
  • $\begingroup$ Isn't that just the even mixing rule? At least if there are any two councils that don't have 3 members in common, it would appear to be broken. $\endgroup$ May 22, 2019 at 22:48
0
$\begingroup$

This is aimed at the bonus question:

When I construct a set of student councils, they always look the same initially. I'm ignoring the ratio requirement for the moment, and I have also reduced the number of required students in common from 3 to just 1. We can later treat each "council member" as a grouping of 3 students to achieve our requirement.

So for example

enter image description here

Each student in the initial council must be separate from the others exactly n-1 times. The blank spots in the chart would be filled with other letters. We can't combine any of them or add more, so this has to be the total number. Beyond that I'm just making the simple observation that the cells in this chart needs to be divisible by n, because for each new letter we add it will fill 5 spots.

I said all this because I confused some numbers earlier... got it. Sorry

$\endgroup$

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.