A new college, The University of Discrete Structures, is opening in Boulder! Ioana and Rachel are its founders and are holding a meeting to determine how many different courses to offer. The following rules are being insisted on: Each course must meet in a different building on the UDS campus, and no two students enrolled at the college may take the exact same set of courses. This means that for any two students, their list of courses that they are taking must differ by at least one course. It is required that all students enroll in at least one course. You must fully justify the following questions: (a) If there are 500 students enrolled in the new university, what is the smallest number of buildings that will be needed to host classes? (b) In general, with n different buildings, what is the maximum number of students that can enroll in the university so that rules are still met?

Question

Sanaa Norman

Mathematics

14 March, 21:23

A new college, The University of Discrete Structures, is opening in Boulder! Ioana and Rachel are its founders and are holding a meeting to determine how many different courses to offer. The following rules are being insisted on: Each course must meet in a different building on the UDS campus, and no two students enrolled at the college may take the exact same set of courses. This means that for any two students, their list of courses that they are taking must differ by at least one course. It is required that all students enroll in at least one course. You must fully justify the following questions: (a) If there are 500 students enrolled in the new university, what is the smallest number of buildings that will be needed to host classes? (b) In general, with n different buildings, what is the maximum number of students that can enroll in the university so that rules are still met?

+4

Answers (1)

Know the Answer?

Remington Marshall · Answer 1

(a) 9 buildings

(b) 2^n - 1

Step-by-step explanation:

The number of distinct non-empty subsets of b objects is 2^b - 1. Since the subsets are distinct, each could represent a list of the buildings, from the set of b buildings, in which a student is taking courses.

(a) For 8 buildings, 2^8 - 1 = 255 students could enroll. for 9 buildings, 2^9-1 = 511 students could enroll.

For 500 students, 9 buildings are required.

__

(b) The maximum number of students for n buildings is ...

2^n - 1