由 G@ry 於 星期二 一月 22, 2008 1:35 pmAnonymous 寫到: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~~