2025年加拿大數學競賽（CMO）模擬試卷（組合數學與數論進階）——競賽題型剖析一、組合數學要求：考察學生對組合數學基礎知識的掌握，包括排列組合、組合恒等式、二項式定理等。1.計算以下排列數：（1）從5個不同的球中取出3個球的排列數。（2）從7個不同的球中取出4個球的排列數。2.計算以下組合數：（1）從5個不同的球中取出3個球的組合數。（2）從7個不同的球中取出4個球的組合數。3.應用二項式定理展開以下表達式：（1）(x+y)^4（2）(x+y)^54.求證以下組合恒等式：（1）C(n,k)=C(n,n-k)（2）C(n,k)+C(n,k-1)=C(n+1,k)二、數論要求：考察學生對數論基礎知識的掌握，包括質數、合數、同余、模運算等。1.判斷以下數是質數還是合數：（1）17（2）21（3）29（4）352.求以下數的最大公約數和最小公倍數：（1）12和18（2）15和203.判斷以下同余式是否成立：（1）3^2≡1(mod8)（2）2^3≡5(mod7)4.求解以下模運算：（1）若a≡5(mod7)，求a^2≡?(mod7)（2）若a≡3(mod5)，求a^3≡?(mod5)5.求證以下定理：（1）若a和b互質，則a^2+b^2也互質。（2）若a和b互質，則a和b+1也互質。三、綜合題要求：考察學生對組合數學與數論的綜合應用能力。1.已知集合A={1,2,3,4,5}，B={2,4,6,8,10}，求集合A與B的笛卡爾積的元素個數。2.已知正整數n，求證：若n是質數，則n^2-1是合數。3.已知兩個正整數a和b，求證：若a和b互質，則a^2+b^2也是合數。4.已知兩個正整數a和b，求證：若a和b互質，則a^2-b^2也是合數。5.已知一個正整數n，求證：若n是質數，則n^2-1可以表示為兩個質數的乘積。6.已知兩個正整數a和b，求證：若a和b互質，則a^2-b^2可以表示為兩個質數的乘積。四、數論應用題要求：考察學生對數論知識在實際問題中的應用能力。1.證明：若p是質數，且p>2，則p^2-1是4的倍數。2.已知正整數n，求最小的正整數m，使得n^2-1能被m整除。3.設p是奇質數，證明：p^2-1可以被(p-1)^2整除。五、組合計數問題要求：考察學生對組合計數方法的運用，包括遞推關系、容斥原理等。1.某班有30名學生，其中有10名男生和20名女生。現在要從這個班級中選出4名學生參加比賽，要求至少有1名女生。求選出的4名學生中女生人數的分布情況。2.有5個不同的球，需要將它們放入3個不同的盒子中，每個盒子至少放一個球。求不同的放法有多少種。3.已知集合A有10個元素，集合B有8個元素，且A與B的交集有3個元素。求集合A與B的并集有多少個元素。六、數論中的最大公約數問題要求：考察學生對最大公約數和最小公倍數的計算方法，以及其在數論中的應用。1.求以下數的最大公約數和最小公倍數：（1）180和270（2）56和982.設a和b是兩個正整數，且a是b的倍數。證明：a和b的最大公約數是b。3.已知a和b是兩個正整數，且a和b的最大公約數是c。證明：a和b的最小公倍數是ab/c。本次試卷答案如下：一、組合數學1.計算以下排列數：（1）從5個不同的球中取出3個球的排列數：P(5,3)=5×4×3=60（2）從7個不同的球中取出4個球的排列數：P(7,4)=7×6×5×4=8402.計算以下組合數：（1）從5個不同的球中取出3個球的組合數：C(5,3)=5!/(3!×(5-3)!)=10（2）從7個不同的球中取出4個球的組合數：C(7,4)=7!/(4!×(7-4)!)=353.應用二項式定理展開以下表達式：（1）(x+y)^4=1x^4y^0+4x^3y^1+6x^2y^2+4x^1y^3+1x^0y^4=x^4+4x^3y+6x^2y^2+4xy^3+y^4（2）(x+y)^5=1x^5y^0+5x^4y^1+10x^3y^2+10x^2y^3+5x^1y^4+1x^0y^5=x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^54.求證以下組合恒等式：（1）C(n,k)=C(n,n-k)：根據組合數的定義，C(n,k)=n!/(k!×(n-k)!),C(n,n-k)=n!/((n-k)!×(n-n+k)!)=n!/(k!×(n-k)!)，因此C(n,k)=C(n,n-k)。（2）C(n,k)+C(n,k-1)=C(n+1,k)：根據組合數的定義，C(n,k)=n!/(k!×(n-k)!),C(n,k-1)=n!/((k-1)!×(n-k+1)!),C(n+1,k)=(n+1)!/(k!×(n+1-k)!),將C(n,k)和C(n,k-1)相加，得到C(n,k)+C(n,k-1)=n!/(k!×(n-k)!)+n!/((k-1)!×(n-k+1)!)=(n+1)!/(k!×(n+1-k)!),因此C(n,k)+C(n,k-1)=C(n+1,k)。二、數論1.判斷以下數是質數還是合數：（1）17：質數（2）21：合數，因為21=3×7（3）29：質數（4）35：合數，因為35=5×72.求以下數的最大公約數和最小公倍數：（1）12和18：最大公約數是6，最小公倍數是36（2）15和20：最大公約數是5，最小公倍數是603.判斷以下同余式是否成立：（1）3^2≡1(mod8)：成立，因為3^2=9，9除以8余1（2）2^3≡5(mod7)：成立，因為2^3=8，8除以7余14.求解以下模運算：（1）若a≡5(mod7)，求a^2≡?(mod7)：由于5^2=25，25除以7余4，所以a^2≡4(mod7)（2）若a≡3(mod5)，求a^3≡?(mod5)：由于3^3=27，27除以5余2，所以a^3≡2(mod5)5.求證以下定理：（1）若a和b互質，則a^2+b^2也互質：假設a和b互質，即gcd(a,b)=1，那么gcd(a^2,b^2)=gcd(a,b)^2=1，因此a^2+b^2也互質。（2）若a和b互質，則a和b+1也互質：假設a和b互質，即gcd(a,b)=1，那么gcd(a,b+1)=gcd(a,1)=1，因此a和b+1也互質。三、綜合題1.已知集合A={1,2,3,4,5}，B={2,4,6,8,10}，求集合A與B的笛卡爾積的元素個數：A與B的笛卡爾積有5×5=25個元素。2.已知正整數n，求證：若n是質數，則n^2-1是合數：假設n是質數，那么n^2-1=(n+1)(n-1)，由于n是質數，n+1和n-1不等于1，因此n^2-1是合數。3.已知兩個正整數a和b，求證：若a和b互質，則a^2+b^2也是合數：假設a和b互質，即gcd(a,b)=1，那么a^2+b^2不等于a和b的平方和，因此a^2+b^2也是合數。4.已知兩個正整數a和b，求證：若a和b互質，則a^2-b^2也是合數：假設a和b互質，即gcd(a,b)=1，那么a^2-b^2不等于a和b的平方差，因此a^2-b^2也是合數。5.已知一個正整數n，求證：若n是質數，則n^2-1可以表示為兩個質數的乘積：假設n是質數，那么n^2-1=(n+1)(n-1)，由于n是質數，n+1和n-1不等于1，因此n^2-1可以表示為兩個質數的乘積。6.已知兩個正整數a和b，求證：若a和b互質，則a^2-b^2可以表示為兩個質數的乘積：假設a和b互質，即gcd(a,b)=1，那么a^2-b^2不等于a和b的平方差，因此a^2-b^2可以表示為兩個質數的乘積。四、數論應用題1.證明：若p是質數，且p>2，則p^2-1是4的倍數：由于p是質數，p>2，那么p可以表示為4k+1或4k+3的形式，其中k是正整數。當p=4k+1時，p^2-1=(4k+1)^2-1=16k^2+8k=4(4k^2+2k)，是4的倍數；當p=4k+3時，p^2-1=(4k+3)^2-1=16k^2+24k+8=4(4k^2+6k+2)，也是4的倍數。因此，p^2-1是4的倍數。2.已知正整數n，求最小的正整數m，使得n^2-1能被m整除：由于n^2-1=(n+1)(n-1)，所以n^2-1能被n+1和n-1整除。最小的正整數m是n+1和n-1的最小公倍數。3.設p是奇質數，證明：p^2-1可以被(p-1)^2整除：由于p是奇質數，p-1是偶數，所以(p-1)^2是4的倍數。又因為p^2-1=(p+1)(p-1)，所以p^2-1可以被(p-1)^2整除。五、組合計數問題1.某班有30名學生，其中有10名男生和20名女生。現在要從這個班級中選出4名學生參加比賽，要求至少有1名女生。求選出的4名學生中女生人數的分布情況：女生人數可以是1、2、3或4，分別計算每種情況的組合數，然后相加得到總情況數。2.有5個不同的球，需要將它們放入3個不同的盒子中，每個盒子至少放一個球。求不同的放法有多少種：先考慮每個盒子至少放一個球的情況，即5個球分成3組，然后計算分組的不同情況數。3.已知集合A有10個元素，集合B有8個元素，且A與B的交集有3個元素。求集合A與B的并集有多少個元素：A與B的并集元素個數為A的元素個數加上B的元素個數減去A與B的交集元素個數。六、數論中的最大公約數問題1.求以下數的最大公約數和最小公倍數：（1）180和270：最大公約數是90，最小公倍數是540（2）56和98：最大公約數是14，最小公倍數是2722.設a和b是兩個正整數，且a是b的倍數。證明：a和b的最大公約數是b：由于a是b的倍數，所以gcd(