習(xí)題

1.1 求解下列問題。

（a）|{0，1，2，3，4，5，6}|。

（b）。

（c）。

（d）100的因子集合。

（e）100的質(zhì)因子集合。

1.2 設(shè)f（n）是n的最大質(zhì)因子。當(dāng)x<y時(shí)，會有f（x）>f（y）嗎？舉例或說明為什么不可能。

1.3 什么情況下有|x|=|x|-1？

1.4 想象一下：有一個(gè)9×9的鴿籠方陣，每個(gè)鴿籠里有一只鴿子。（因此，81只鴿子在81個(gè)鴿籠中，見圖1.4。）假設(shè)所有鴿子同時(shí)向上、向下、向左或向右移動一個(gè)鴿籠。（邊緣的鴿子不允許移出方陣。）證明某個(gè)鴿籠里會飛進(jìn)兩只鴿子。提示：數(shù)字9有點(diǎn)復(fù)雜。嘗試小一點(diǎn)的數(shù)兒，看看會發(fā)生什么。

1.5 證明在任意一群人中，有兩個(gè)人在群中擁有同樣多的朋友。（這里有個(gè)重要的假設(shè)：沒有人是他或她自己的朋友，并且朋友關(guān)系是對稱的（symmetrical），即如果A是B的朋友，那么B也是A的朋友。）

1.6 已知球體上的任意5個(gè)點(diǎn)，證明其中4個(gè)點(diǎn)必位于一個(gè)閉合的半球體中，其中“閉合”表示半球中包括一個(gè)“圈”，該圈將其與球體的另一半分開。提示：已知球體上的任意兩點(diǎn)，總可以在它們之間畫一個(gè)“大圈”，該圈與球體的赤道有相等的周長。

1.7 證明在任意25個(gè)人的人群中，必有3個(gè)人的生日在同一個(gè)月。

1.8 一堆硬幣中包含6種不同的面值：1分、5分、10分、15分、50分和1元。至少要收集多少枚硬幣才能保證至少有100枚硬幣的面值相同？

1.9 有25個(gè)人每天在同一家健身房上瑜伽課，該健身房每天提供8節(jié)課。每位參加者可以穿藍(lán)色、紅色或綠色襯衫去上課。證明在某一天，至少有一節(jié)課上有兩個(gè)人穿著同一顏色的襯衫。

1.10 在1和60之間（包括1和60）選擇4個(gè)不同的整數(shù)，證明其中兩個(gè)數(shù)的差最多是19。

1.11 找到一個(gè)k，使得前k個(gè)質(zhì)數(shù)的乘積加1不是質(zhì)數(shù)，并且具有比前k個(gè)質(zhì)數(shù)都大的質(zhì)因子。（解決這個(gè)問題沒有訣竅，必須嘗試各種可能。）

1.12 證明任意9個(gè)正整數(shù)構(gòu)成的集合中，存在兩個(gè)數(shù)具有相同的小于或等于5的質(zhì)因子。

1.13 從字符串集到數(shù)字集的哈希函數(shù)（hash function）作用是為文本字符串s計(jì)算出一個(gè)哈希數(shù)值h（s）。例如，將s中所有字符的數(shù)字編碼相加，再除以質(zhì)數(shù)p，保留余數(shù)。哈希函數(shù)的關(guān)鍵點(diǎn)是能產(chǎn)生可再現(xiàn)的結(jié)果（即對同一字符串s計(jì)算兩次h（s）會產(chǎn)生相同的數(shù)值），并且使不同字符串的哈希值在0到p-1之間均勻分布。當(dāng)哈希函數(shù)對不同的兩個(gè)字符串產(chǎn)生相同的哈希值時(shí)，稱這兩個(gè)字符串是哈希值沖突（collide）的。哈希值的沖突數(shù)是指具有相同的哈希值的字符串的數(shù)量減1，因此，如果有2個(gè)字符串具有相同的哈希值，則該哈希值的沖突數(shù)是1。如果有m個(gè)字符串和p個(gè)可能的哈希值，那么對于發(fā)生最多沖突的哈希值，發(fā)生的最小沖突數(shù)是多少？某哈希值發(fā)生的最大沖突數(shù)是多少？