返回题库

HMMT 二月 2017 · 团队赛 · 第 7 题

HMMT February 2017 — Team Round — Problem 7

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 45 ] Let p be a prime. A complete residue class modulo p is a set containing at least one elementequivalent to k (mod p ) for all k .
    (a) ( 20 ) Show that there exists an n such that the n th row of Pascal’s triangle forms a completeresidue class modulo p .
    (b) ( 25 ) Show that there exists an n ≤ p such that the n th row of Pascal’s triangle forms a complete 2
    residue class modulo p .
解析

英文解析

  1. [ 45 ] Let p be a prime. A complete residue class modulo p is a set containing at least one elementequivalent to k (mod p ) for all k .
    (a) ( 20 ) Show that there exists an n such that the n th row of Pascal’s triangle forms a completeresidue class modulo p .
    (b) ( 25 ) Show that there exists an n ≤ p such that the n th row of Pascal’s triangle forms a complete 2
    residue class modulo p .
    Proposed by: Alexander Katz
    We use the following theorem of Lucas:
    Theorem. Given a prime p and nonnegative integers a, b written in base p as a = a a . . . a andn n − 1 0
    b = b b . . . b respectively, where 0 ≤ a , b ≤ p − 1 for 0 ≤ i ≤ n , we havepn n − 1 0 i i
    ( ) ( )pn
    ∏
    a ai = (mod p ) .
    b bii =0
    Now, let n = ( p − 1) × p + ( p − 2) = p − 2. For k = pq + r with 0 ≤ q, r ≤ p − 1, applying Lucas’s 2
    theorem gives
    ( ) ( )( )
    n p − 1 p − 2
    ≡ (mod p ) .
    k q r
    Note that
    ( )
    ∏qp − 1 p − i = ≡ ( − 1) (mod p ) ,qq ii =1
    ( )andr
    ∏
    p − 2 p − 1 − i ( r + 1)!
    r r = ≡ ( − 1) = ( − 1) ( r + 1) (mod p ) .
    r i r !
    i =1
    ( )
    So for 2 ≤ i ≤ p we can take k = ( p + 1)( i − 1) and obtain ≡ i (mod p ), while for i = 1 we cannktake k = 0. Thus this row satisfies the desired property.