[問題]這個題目怎麼寫啊??鴿籠原理...

[問題]這個題目怎麼寫啊??鴿籠原理...

訪客 於 星期一 一月 21, 2008 7:52 pm


1.  If processors are interconnected, show that at least two processors are directly connected to the same number of processors .

2.  Show that if we select 151 distinct computer science courses numbered between 1 and 300 inclusive, at least two are consecutively  
     numbered.

這兩題怎寫啊??雖然題目是英文的....但請用中文回答我包刮解答!!謝謝~~

訪客

 

Re: [問題]這個題目怎麼寫啊??鴿籠原理...

G@ry 於 星期二 一月 22, 2008 1:35 pm


Anonymous 寫到:1.  If processors are interconnected, show that at least two processors are directly connected to the same number of processors .

2.  Show that if we select 151 distinct computer science courses numbered between 1 and 300 inclusive, at least two are consecutively  
     numbered.

這兩題怎寫啊??雖然題目是英文的....但請用中文回答我包刮解答!!謝謝~~

1. let there be n processors, the number of connected processors for a particular processor i is ci , i=1,2,...,n
As all processors are interconnected => ci > 0 => ci ≥ 1
The max number of processors for a processor to connect = n-1 => n-1 ≥ ci ≥ 1
There are n ci with only 1...n-1 = n-1 values to choose from.
Thus by Pigeonhole principle, there are at least 2 ci with the same value.
i.e. There are at least two processors directly connected to the same number of processors.

2. similar logic, try yourself~~
☆子 是也

G@ry
版 主
版 主
 
文章: 597
註冊時間: 2007-03-01
來自: 香港




大學以上數學問題