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 c
i , i=1,2,...,n
As all processors are interconnected => c
i > 0 => c
i ≥ 1
The max number of processors for a processor to connect = n-1 => n-1 ≥ c
i ≥ 1
There are n c
i with only 1...n-1 = n-1 values to choose from.
Thus by Pigeonhole principle, there are at least 2 c
i 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~~