Question

【題目】某校有微機(jī)臺，分別放在個(gè)房間，各房間開門鑰匙互不相同.某期培訓(xùn)班有學(xué)員人（），每晚恰有人進(jìn)機(jī)房實(shí)習(xí)操作，為保證每人一臺機(jī)，至少應(yīng)準(zhǔn)備多少把鑰匙分給這個(gè)學(xué)員，使得每晚不論哪個(gè)人進(jìn)機(jī)房，都能用自己分到的鑰匙打開一間機(jī)房的門進(jìn)去練習(xí)，并按分得鑰匙少的人先開門的原則，能保證每人恰可得到一個(gè)房間.

Answer 1

【答案】至少應(yīng)準(zhǔn)備把鑰匙分給學(xué)員才能滿足題目要求

【解析】

注：本題可先設(shè)計(jì)一個(gè)鑰匙分配方案，再證明該方案最佳（鑰匙總數(shù)最少且滿足要求）.

先將個(gè)房間的把不同鑰匙分給某名學(xué)員，每人一把（個(gè)人都可用自己分得的鑰匙打開一個(gè)房間的門），其余個(gè)人，可每人分把（所有房間的鑰匙）.這批人得的鑰匙多，只要那個(gè)房間無人，都可開門進(jìn)去.此方案共需鑰匙：把.

下面證明方案最佳.假設(shè)鑰匙總數(shù)，則由抽屜原理，必有一房里鑰匙數(shù).這房間的鑰匙最多只能分給個(gè)學(xué)員，因每天只有個(gè)學(xué)員上機(jī)房.也恰有個(gè)人不上機(jī)房.如果分得這房間鑰匙的學(xué)員全部不上機(jī)房，則這房間的門無法打開，題目條件不能滿足.故該方案最佳.即至少應(yīng)準(zhǔn)備把鑰匙分給學(xué)員才能滿足題目要求.