Kỳ thi chọn HSGQG môn Toán 2015 - Đề thi - Page 5

**chemthan** · 09-01-2015, 05:41 PM

Trích:

Nguyên văn bởi huynhcongbang

Bài 7a.

Ứng với mỗi chương trình văn nghệ, ta mô phỏng việc ghép cặp của các cặp nam nữ song ca thành một bảng gồm $m$ hàng và $n$ cột như sau:

Bảng sẽ được đánh số 1 hoặc 0, trong đó: số 1 chỉ trong chương trình này, học sinh nữ ở hàng và học sinh nam ở cột tương ứng có song ca với nhau, số 0 chỉ hai học sinh đó không song ca.

Một bảng gọi là “tốt” nếu trên mỗi hàng và mỗi cột đều phải có ít nhất một số 1.
Xét một học sinh $X$ nào đó, giả sử đó là nữ; trường hợp học sinh nam chứng minh tương tự.

Chương trình tương ứng lệ thuộc học sinh $X$ nếu như tồn tại ít nhất 1 cột có đúng 1 số 1 nằm trên hàng của $X$, ta gọi bảng này là lệ thuộc X và cột như thế là cột lệ thuộc $X$.
Ta cần chứng minh rằng trong các bảng lệ thuộc $X$ thì số bảng có số các số 1 chẵn bằng số bảng có số các số 1 lẻ.

Thật vậy,
Xét trường hợp trong bảng có $k$ cột lệ thuộc $X$. Rõ ràng $k<m$ vì nếu không $k=m$ thì toàn bộ các ô trên hàng $X$ đều là 1, còn tất cả các ô còn lại của bảng đều là 0. Do $n\ge 2$ nên tồn tại 1 dòng toàn là số 0, mâu thuẫn.
Với $k<m$, ta bỏ $k$ cột đó ra khỏi bảng thì trên bảng sẽ mất đi đúng $k$ số 1. Mỗi ô trong $m-k$ ô còn lại của hàng $X$ sẽ được điền số 0 hoặc 1 tùy ý vì các cột còn lại đều còn ít nhất một số 1 nữa không thuộc hàng $X$. Do đó, nếu ta bỏ luôn hàng $X$ đi thì bảng còn lại vẫn là tốt.

Suy ra số bảng lệ thuộc $X$ trong trường hợp này sẽ là ${{2}^{m-k}}$ nhân với số lượng bảng tốt có kích thước $(m-k)\times (n-1)$ còn lại. Trong mỗi bảng sau khi đã bỏ các cột lệ thuộc $X$ đi, ta chọn một ô bất kỳ của hàng $X$ và thay đổi số từ $0\to 1,1\to 0$ thì sẽ dẫn đến thay đổi tính chẵn lẻ của số các số 1 trên bảng nên có số bảng có số các số 1 lẻ và chẵn là bằng nhau.

Ứng với mỗi $k=\overline{1,m-1}$ thì số lượng bảng có số 1 lẻ và chẵn đều bằng nhau nên tổng số bảng phụ thuộc $X$ có số các số 1 lẻ bằng với bảng có số các số 1 chẵn.

Ta có đpcm.

Phần b) sử dụng kết quả phần a) thì phải.@
Gọi $f(m, n)$ là tập hợp các bảng tốt $m * n$ có số chẵn các số 1, và $g(m, n)$ là tập hợp các bảng tốt $m * n$ có lẻ các số 1.
Nếu tồn tại một cột là $(1, 0, ...., 0)$ thì sử dụng phần a) ta suy ra số các bảng tốt thuộc $f(m, n)$ và số các bảng tốt thuộc $g(m, n)$ trong trường hợp này là bằng nhau.
Ngược lại thì sau khi bỏ hàng đầu tiên đi ta thu được một bảng tốt $(m -1) * n$.
Vì hàng đầu tiên của bảng $m * n$ gốc không thể chứa toàn số 0 nên:
$|f(m, n)| - |g(m, n)| = |g(m - 1, n)| - |f(n - 1, n)| = ... = (-1)^{m - 1}(|f(1, n)| - g(1, n)|) = (-1)^{m + n - 1}$.

lupanh7 · 09-01-2015, 06:14 PM

Phần b) bài 7
Gọi a là một học sinh nam
Gọi C(n,m) là số lượng chương trình có chẵn bài hát có thể có của một Liên hoan song ca với n học sinh nam và m học sinh nữ.
L(n,m) là số lượng chương trình có lẻ bài hát có thể có của một Liên hoan song ca với n học sinh nam và m học sinh nữ.
Gọi $A_1, A_2, A_3, A_4$ lần lượt là tập hợp các chương trình có thể có với n học sinh nam và m thuộc loại 1,2,3,4 với:
Loại 1: Chương trinh lệ thuộc vào a và có chẵn bài hát
Loại 2: Chương trinh lệ vào a và có lẻ bài hát
Loại 3: Chương trinh không lệ thuộc vào a và có chẵn bài hát
Loại 4: Chương trinh không lệ thuộc vào a và có lẻ bài hát
Một chương trình thuộc loại 3 hoặc 4 khi bỏ đi các tiết mục của a sẽ thu được một chương trình với n-1 học sinh nam và m học sinh nữ nên sẽ chứng minh được:
$C(n,m)=|A_1|+C(n-1,m).(C_m^2+C_m^4+...+C_m^{2[m/2]})+L(n-1,m).(C_m^1+C_m^3+...+C_m^{2[(m-1)/2]+1})$
$L(n,m)=|A_2|+L(n-1,m).(C_m^2+C_m^4+...+C_m^{2[m/2]})+C(n-1,m).(C_m^1+C_m^3+...+C_m^{2[(m-1)/2]+1})$
Từ đây suy ra C(n,m)-L(n,m)=L(n-1,m)-C(n-1,m)

ThangToan · 09-01-2015, 06:23 PM

Trích:

Nguyên văn bởi Fool's theorem

Bài 6b:
$x.a^2+y(6a)+36z=n$ tương đương $x.a^2+(y+6m)6a+36(z-ma)=n$, nên ta có thể giả sử $z<a$ (nếu không thay $z$ bằng $z-ma<a$)
Viết lại phương trình thành $x.a^2+y.6a=n-36z$. Từ đây ta có $a|n-36z$, chuyển lại phương trình thành $ax+6y=\frac{n-36z}{a}$
Áp dụng tính chất: Phương trình nghiệm nguyên $ax+by =c$, $gcd(a,b)=1$, ta có số $c$ lớn nhất thỏa mãn phương trình không có nghiệm là $ab-a-ab$
Áp dụng vào ta có $n$ lớn nhất thỏa mãn đề bài sẽ thỏa mãn: $\frac{n-36z}{a} \leq 6a-a-6$ tức $n \leq 5a^2-6a+36z \leq 5a^2-6a+36(a-1) =5a^2+30a-36$
Tính chất được sử dụng trong bài khá nổi tiếng, mọi người có thể tìm hiểu thêm dưới cái tên Frobenius Coin Problem. Tuy nhiên bài 6 của VMO mà áp dụng phát ra luôn thì cũng không hay lắm

Số n lớn nhất phải là $5a^2+30a-35$

Hennmarsk · 09-01-2015, 06:56 PM

Mình loại được mỗi a=7, a=5 định làm như thế hóa ra sai

n.t.tuan · 09-01-2015, 07:51 PM

Lữ gõ nốt ngày 2 rồi cho bọn anh xin cả CODE nhé!

P.S. Bài 7 anh em mình giống nhau ở chỗ phát biểu lại qua ma trận nhị phân.

sophia2009 · 10-01-2015, 07:45 AM

Trích:

Nguyên văn bởi huynhcongbang

Bài 6 chính là một dạng tương tự của bài 3 IMO 1983:

[Only registered and activated users can see links. ]

Cho $a,b,c$ là các số nguyên dương có $(a,b,c)=1$. Chứng minh rằng $2abc-ab-bc-ca$ là số nguyên lớn nhất không biểu diễn được dưới dạng $xab+ybc+zca$.

Chú ý rằng phương trình đã cho viết lại là: $x.a^2+y.(6a)+z.(6^2)=n$.

Điều kiệnlà a,b,c đôi một nguyên tố cùng nhau chứ không phải (a,b,c)=1 anh Bảng ạ. Bạn đọc có thể xem bài viết tổng quan về vấn đề Frobenius của TS Lưu Bá Thắng trên Tạp chí thông tin Toán học (Trang 20-28) của Hội Toán học Việt Nam.
[Only registered and activated users can see links. ]

**huynhcongbang** · 10-01-2015, 09:43 AM

Trích:

Nguyên văn bởi n.t.tuan

Lữ gõ nốt ngày 2 rồi cho bọn anh xin cả CODE nhé!

P.S. Bài 7 anh em mình giống nhau ở chỗ phát biểu lại qua ma trận nhị phân.

Dạ vâng ạ.

Thầy Nam Dũng đã lên kế hoạch thực hiện ngay sau khi kết thúc ngày 1 rồi anh ạ, mong là sẽ xong bản word vào cuối tuần này và bản Latex vào đầu tuần sau ạ.

------------------------------

Trích:

Nguyên văn bởi slivergun

Em nghĩ phàn b chỉ Cần xét 1 người nam rồi xét t là min các đỉnh nối vs ng đó( e giải ngôn ngữ đồ thị)

Bài này em giải bằng đồ thị lưỡng phân à, ý tưởng mô hình này cũng khá tự nhiên nhưng hôm qua anh làm mãi mà không được. Em có thể nói rõ thêm cách xử lý được không?

------------------------------

Trích:

Nguyên văn bởi dat150611

Anh Lữ nghĩ mấy điểm thì mới có giải III ạ ?

Anh đoán (và cũng hy vọng) là 17đ, keke.

Nhưng nói chung chưa biết phân bố điểm của các câu thế nào (tỉ lệ 50-50 như 2013 hay là theo độ khó), nên cũng mơ hồ lắm.

**quocbaoct10** · 10-01-2015, 11:15 AM

Bài 7:
a) xét đồ thị lưỡng phân $G(M,N,E)$ trong đó $M$ là tập đỉnh biểu diễn học sinh nam và $N$ là tập đỉnh biểu diễn học sinh nư. ta có $|M|=m$ và $|N|=n$.
Theo điều kiện của đề, ta thấy mỗi đỉnh tử $M$ được nối với ít nhất một đỉnh ở $N$ và ngược lại. Một buổi diễn phụ thuộc vào học sinh nam $i$ (nữ tương tự) nghĩa là trong đồ thị lưỡng phân $G(M,N,E)$ thì trong tập các đỉnh nối với đỉnh $i$ phải có ít nhất một đỉnh $n_{i_k}$ có $deg (n_{i_k}) = 1$, giả sử có $k$ đỉnh như vậy. Bỏ đi các đỉnh $n_{i_k}$ có $deg=1$ và đỉnh $i$, ta sẽ được đồ thị $G(M',N',E')$ mà trong đó $|M'|=m-1$ và $|N'|=n-k$.Sau khi xóa đi $k$ cạnh, số cạnh còn lại có thể chẵn hoặc lẻ. Với trường hợp chẵn, nếu trong tập $M'$ không có đỉnh $m_t$ nào có $deg(m_t)=n-k$ thì ta có thể chọn một số lẻ đỉnh và nối đỉnh đó đến một đỉnh khác trong tập $N'$, khi đó sẽ được một số đỉnh lẻ. như vậy có $O=\binom{n-1}{1}+\binom{n-1}{3}+\binom{n-1}{5}+ ...$. Tương tự đó với việc chọn số chẵn đỉnh để được số cạnh chẵn, ta có $E=\binom{n-1}{0}+\binom{n-1}{2}+...$. Dễ thấy $O=E$ nên suy ra số tập cạnh chẵn sẽ bằng số tập cạnh lẻ. Tương tự với trường hợp phần còn lại là tập cạnh lẻ. Nếu có ít nhất 1 đỉnh trong $M'$ có $deg=n-k$, ta bỏ đi qua các đỉnh này và chọn tương tự cho phần các đỉnh còn lại. Như vậy, từ đấy ta luôn có điều phải chứng minh.
b). Gọi $O(m,n)$ là số đồ thị $G(M,N,E)$ có số cạnh lẻ, $E(m,n)$ là số đồ thị có số cạnh chẵn, khi đó xét một điểm $i \in M$, nếu đồ thị G bị phụ thuộc $i$ thì dựa vào câu a) sẽ có số đồ thị có số cạnh chẵn và số đồ thị có số cạnh lẻ là bằng nhau (*). Với những đồ thị không phụ thuộc vào $i$, khi bỏ i, ta sẽ được số đồ thị có chẵn cạnh là $E(m-1,n)$ và số đồ thị có lẻ cạnh là $O(m-1,n)$. Nếu $i$ có số $deg(i)=2k+1$ thì từ số đồ thị có số chẵn cạnh $E(m,n)$ ta sẽ có được số đồ thị có số lẻ cạnh $k.O(m-1,n)$, tương tự với $O(m,n)$ (1). Khi với $deg(i)=2k+2 > 0$ thì từ số đồ thị có cạnh chẵn $E(m,n)$ ta nhận được số đồ thị có cạnh chẵn là $(k-1)E(m-1,n)$ và tương tự với số đồ thị có cạnh lẻ (2) (sở dĩ được $k-1$ vì ta không xét đến trường hợp $deg(i)=0$ cũng là một số chẵn).
Từ (1) và (2) và (*) ta được: $E(m,n)-O(m,n)=O(m-1,n)-E(m-1,n)=...=(-1)^m(E(1,n)-O(1,n))=(-1)^m$.
Vì vậy số đồ thị có số cạnh chẵn không chênh lệch với số đồ thị có số lẻ cạnh quá 1 đơn vị, nên có thể sắp xếp xen kẽ các đô thị có số cạnh chẵn và các đồ thị có số cạnh lẻ với nhau.
.

ThangToan · 10-01-2015, 11:27 AM

Bài 6. Ta xét phương trình $6a^2x+6ay^2+36z=m$ (1) với nghiệm nguyên dương.
Bổ đề. Ta chứng minh số $m=6a^2+36a$ là số nguyên dương lớn nhất để phương trình trên vô nghiệm.
Thật vậy,
a) với $m=6a^2+36a$ ta chứng minh phương trình sau không có nghiệm nguyên dương:
$6a^2x+6ay^2+36z=6a^2+36a$ (2).
Từ (2) ta có $z \vdots a \Rightarrow \exists k \in {N^*}:z = ka$
Chia hai vế của (1) cho $a$ ta được:
$ax+6y+36k=6a+36$
$ \Leftrightarrow a\left( {6 - x} \right) = 6\left( {y + 6k - 6} \right) \vdots a \Rightarrow y + 6k - 6 \vdots a \Rightarrow y + 6k - 6 \ge a$
$ \Rightarrow 6\left( {y + 6k - 6} \right) \ge 6a > \left( {6 - x} \right)a$ vô lý.
b) Tiếp theo ta chứng minh rằng với mọi $m \ge 6{a^2} + 36a + 1$ thì phương trình (1) luôn có nghiệm nguyên dương.
Do $(a,6)=1$ nên hệ $\left\{ {36.1,36.2,...,36.a} \right\}$ là hệ đầy đủ theo $moda$ suy ra tồn tại $ z \in \left\{ {1,2,...,a} \right\}:36z \equiv n\left( {\bmod a} \right) \Rightarrow \frac{{n - 36z}}{a} \in Z $
Kết hợp với $n - 36z \ge 6{a^2} + 36a - 36a > 0 \Rightarrow \frac{{n - 36z}}{a} \in {N^*}$
Mặt khác $\left\{ {6.1,...,6.a} \right\}$ là hệ thặng dư đầy đủ theo $moda$ suy ra tồn tại $y \in \left\{ {1,2,...,a} \right\}$ sao cho $6y \equiv \frac{{n - 36z}}{a}\left( {\bmod a} \right)$. Từ đó suy ra tồn tại số nguyên $x$ sao cho :
$\frac{{n - 36z}}{a} - 6y = ax \Leftrightarrow {a^2}x + 6ay + 36z = n$.
Tiếp theo ta chứng minh $x$ nguyên dương như sau:
Ta có $ax = \frac{{n - 36z}}{a} - 6y = \frac{{n - 36z - 6ay}}{a} \ge \frac{{6{a^2} + 36a + 1 - 36a - 6{a^2}}}{a} > 0 \Rightarrow x > 0$.
Vậy luôn tồn tại các số nguyên dương $x,y,z$ thỏa mãn:
$6a^2x+6ay+36z=n$.
Vậy số lớn nhất thỏa mãn là $m=6a^2+36a$. Vậy bổ đề được chứng minh.
Ta quay trở lại bài toán 6 VMO 2015 như sau:
Phương trình $6{a^2}x + 6ay + 36z = n \Leftrightarrow 6{a^2}\left( {x + 1} \right) + 6a\left( {y + 1} \right) + 36\left( {z + 1} \right) = n + {a^2} + 6a + 36$
Như vậy bài toán 6 VMO 2015 trở thành phương trình ứng với nghiệm nguyên dương: $6{a^2}\left( {x + 1} \right) + 6a\left( {y + 1} \right) + 36\left( {z + 1} \right) = n + {a^2} + 6a + 36$
b) Áp dụng bổ đề với $m=n+6a^2+6a+36$ ta được
$n + {a^2} + 6a + 36 \le 6{a^2} + 36a \Leftrightarrow n \le 5{a^2} + 30a - 36$. Vậy số lớn nhất cần tìm là $n=5a^2+30a-36$.
a)
TH1. $(a,6)=1$
Theo phần b ta có: $5{a^2} + 30a - 36 < 250 \Leftrightarrow 5{a^2} + 30a < 286 \Leftrightarrow a \in \left\{ {1,2,3,4,5} \right\}$
Dễ thấy với $a=2,3,4$ không thỏa mãn.
+) $a=1$ thì chọn nghiệm là $(n,0,0)$.
+) $a=5$ ta chứng minh với mọi $n \ge 250$ thì phương trình sau luôn có nghiệm tự nhiên: $25x+30y+36z=n$
Ta có $\left\{ {25.0,25.1,...,25.5} \right\}$ là hệ thặng dư đầy đủ theo $mod6$ nên tồn tại $x \in \left\{ {0,1,...,5} \right\}:n - 25x = 6t$.
Do $x\le 5$ nên $n - 25x \ge 250 - 25.5 \Rightarrow t > 20$.
Bổ đề. Với mỗi số nguyên dương $t>20$ luôn tồn tại các số tự nhiên $y,z$ sao cho $t=5y+6z$.
Thật vậy, ta chứng minh bằng quy nạp theo $t$: Dễ thấy
$21=3.5+6,22=2.6+2.5,23=3.6+5,24=4.6+0.5,25=0.6+5. 5$ Do đó với $t>25$ ta có:
$t=5+t-5=5+5u+6v=5(u+1)+6v$ do đó theo pp quy nạp bổ đề được chứng minh.
Sử dụng bổ đề ta được $n-25=6t=6(5y+6z)$ suy ra $n=25x+30y+36z$.
Vậy $a=1, a=5$.

son235 · 11-01-2015, 01:08 AM

Câu 6b. Trước hết chứng minh bổ đề về số Frobenius đối với hai số $a$, $b$ nguyên tố cùng nhau là $ab-a-b$. Sau đó dùng ý tưởng như bạn Fool’s theorem, ta có đáp số là ${{n}_{\max }}=5{{a}^{2}}+30a-36$.
Quay trở lại 6a. Nếu $\gcd (a,6)=d>1$ thì bài toán không thỏa (vì nếu phương trình có nghiệm thì $d|n$, điều này không thể xảy ra với mọi $n\ge 250$).
Nếu $\gcd (a,6)=1$ và $a>1$,theo câu b, để thỏa yêu cầu bài toán thì $5{{a}^{2}}+30a-36<250$, dễ dàng giải được $a\le 5$, do đó $a=5$.
Nếu $a=1$ thì bài toán thỏa.
Vậy đáp số là $a=1$ và $a=5$.

khanghaxuan · 11-01-2015, 02:38 PM

Bạn nào trình bày rõ ràng bài tổ ngày 1 ra giúp mình với ( bằng truy hồi , kể cả cái hệ thức cũng giải ra giúp mình nhé ! ) . ( Ức chế mấy ngày nay rồi , phải giải stress mới được )

duythanbg · 11-01-2015, 07:14 PM

Trích:

Nguyên văn bởi khanghaxuan

Bạn nào trình bày rõ ràng bài tổ ngày 1 ra giúp mình với ( bằng truy hồi , kể cả cái hệ thức cũng giải ra giúp mình nhé ! ) . ( Ức chế mấy ngày nay rồi , phải giải stress mới được )

ko biết đúng không .

Gọi A(n) là số các số có n chữ số được tạo bởi {2,0,1,5} và chia hết cho 3 .
Gọi B(n),C(n) là số các số có n chữ số được tạo bởi {2,0,1,5} và chia 3 dư 1 và 2 .
Ta có các hệ thức sau :
A(n+1) = A(n) + 2 B(n) + C(n)
B(n+1) = A(n) + B(n) + 2C(n)
C(n+1) = 2 A(n) + B(n) +C(n)

A(n) + B(n) + C(n) là số các số có n chữ số được tạo bởi {2,0,1,5} nên : A(n) + B(n) +C(n) = 3.4^(n-1)
------------------------------

Trích:

Nguyên văn bởi huynhcongbang

Cụ thể là thế này đây bạn:

Bài 4a.

Gọi $K,L$ lần lượt là giao điểm của $(I)$ với $BC$.
Ta có $AK\cdot AF=AL\cdot AE \Rightarrow \frac{AK}{AL}=\frac{AE}{AF}=\frac{AB}{AC} \Rightarrow KL\parallel BC$.

Do $(I)$ tiếp xúc với $BC$ tại $D$ nên
\[\frac{B{{D}^{2}}}{C{{D}^{2}}}=\frac{BF\cdot BK}{CE\cdot CL}=\frac{BF}{CE}\cdot \frac{BK}{CL}=\frac{BF}{CE}\cdot \frac{AB}{AC}=\frac{BF}{CE}\cdot \frac{BE}{CF}=\frac{\cot B}{\cot C}. \]
Vậy $\dfrac{BD}{CD}=\sqrt{\dfrac{\cot B}{\cot C}}$.

a)
Gọi giao điểm của (I) với AB,AC là M,N .
Dễ thấy :
$\Delta BME \sim \Delta CNF\Rightarrow \frac{BE}{CF}=\frac{BM}{CN}\Leftrightarrow \frac{BF}{CF}:\frac{CE}{BE}=\frac{BM.BF}{CN.CE}= \frac{DB^{2}}{DC^{2}} \Leftrightarrow \sqrt{ \frac{cotB}{cotC} }=\frac{DB}{DC}$

294753618 · 11-01-2015, 07:44 PM

Trích:

Nguyên văn bởi khanghaxuan

Bạn nào trình bày rõ ràng bài tổ ngày 1 ra giúp mình với ( bằng truy hồi , kể cả cái hệ thức cũng giải ra giúp mình nhé ! ) . ( Ức chế mấy ngày nay rồi , phải giải stress mới được )

Bài 3 cách truy hồi:
Gọi $A(n)$, $B(n)$, $C(n)$ lần lượt là số các số có không quá n chữ số được tạo bởi {2,0,1,5} và chia hết cho 3, chia 3 dư 1, chia 3 dư 2 .Suy ra $A(n)+B(n)+C(n)=4^n$
Ta có :
$A(n+1) = A(n) + 2 B(n) + C(n)$
$B(n+1) = A(n) + B(n) + 2C(n)$
$C(n+1) = 2 A(n) + B(n) +C(n)$
$\Rightarrow A(n)=4^{n-1}+4^{n-2}+4^{n-3}+A(n-3)$
$\Rightarrow A(n)-\frac{4^{n}}{3}=A(n-3)-\frac{4^{n-3}}{3}=...=A(r)-\frac{4^{r}}{3}$
với $1\leq r\leq 3$ và $r\equiv n$ (mod 3)
Ta có: $A(1) = 1$,$ A(2) = 5$,$ A(3) = 22$
Vậy:
Nếu $n\equiv 1 $ (mod 3) thì $A(n)=1+\frac{4^{n}-4^{1}}{3}=\frac{4^{n}-1}{3}$
Nếu $n\equiv 2 $ (mod 3) thì $A(n)=5+\frac{4^{n}-4^{2}}{3}=\frac{4^{n}-1}{3}$
Nếu $n\equiv 0 $ (mod 3) thì $A(n)=22+\frac{4^{n}-4^{3}}{3}=\frac{4^{n}+2}{3}$

Nam Chung QB · 14-01-2015, 05:15 PM

Câu hình ý a : Theo mình nghĩ chỉ cần bình phương là xong

vuxuandh · 16-01-2015, 10:56 PM

Bài 7/b
Gọi T(A1, A2, ..., Am-1) là tập hợp các chương trình mà:
Tập các nam hát với nữ thứ nhất là A1
...
Tập các nam hát với nữ thứ m -1 là Am -1.
Trong mỗi chương trình thuộc T: A1, A2, ..., Am -1 cố định, tính chẵn lẻ số bài hát phụ thuộc vào tập Am các nam hát với nữ m. Tập Am phải chứa các nam chưa được hát tính tới m -1 nữ đầu, và với k nam được hát rồi thì chứa hay không: tùy. Do đó có thể coi Am là tập con của k phần tử, mà ta biết số tập con có chẵn phần tử của một tập hợp bằng số tập con có lẻ phần tử.
Vậy trong T(A1, A2, ..., Am-1) số chương trình có chẵn bài hát bằng số chương trình có lẻ bài hát. bài toán được chứng minh.
Mọi người cho ý kiến giúp, nếu đúng mình post ý a.

09-01-2015, 07:51 PM	#65
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Lữ gõ nốt ngày 2 rồi cho bọn anh xin cả CODE nhé! P.S. Bài 7 anh em mình giống nhau ở chỗ phát biểu lại qua ma trận nhị phân. __________________ T.

10-01-2015, 11:15 AM	#68
quocbaoct10 +Thành Viên Danh Dự+ Tham gia ngày: Oct 2012 Đến từ: THPT chuyên Lê Quý Đôn-Nha Trang-Khánh Hòa Bài gởi: 539 Thanks: 292 Thanked 365 Times in 217 Posts	Bài 7: a) xét đồ thị lưỡng phân $G(M,N,E)$ trong đó $M$ là tập đỉnh biểu diễn học sinh nam và $N$ là tập đỉnh biểu diễn học sinh nư. ta có $\|M\|=m$ và $\|N\|=n$. Theo điều kiện của đề, ta thấy mỗi đỉnh tử $M$ được nối với ít nhất một đỉnh ở $N$ và ngược lại. Một buổi diễn phụ thuộc vào học sinh nam $i$ (nữ tương tự) nghĩa là trong đồ thị lưỡng phân $G(M,N,E)$ thì trong tập các đỉnh nối với đỉnh $i$ phải có ít nhất một đỉnh $n_{i_k}$ có $deg (n_{i_k}) = 1$, giả sử có $k$ đỉnh như vậy. Bỏ đi các đỉnh $n_{i_k}$ có $deg=1$ và đỉnh $i$, ta sẽ được đồ thị $G(M',N',E')$ mà trong đó $\|M'\|=m-1$ và $\|N'\|=n-k$.Sau khi xóa đi $k$ cạnh, số cạnh còn lại có thể chẵn hoặc lẻ. Với trường hợp chẵn, nếu trong tập $M'$ không có đỉnh $m_t$ nào có $deg(m_t)=n-k$ thì ta có thể chọn một số lẻ đỉnh và nối đỉnh đó đến một đỉnh khác trong tập $N'$, khi đó sẽ được một số đỉnh lẻ. như vậy có $O=\binom{n-1}{1}+\binom{n-1}{3}+\binom{n-1}{5}+ ...$. Tương tự đó với việc chọn số chẵn đỉnh để được số cạnh chẵn, ta có $E=\binom{n-1}{0}+\binom{n-1}{2}+...$. Dễ thấy $O=E$ nên suy ra số tập cạnh chẵn sẽ bằng số tập cạnh lẻ. Tương tự với trường hợp phần còn lại là tập cạnh lẻ. Nếu có ít nhất 1 đỉnh trong $M'$ có $deg=n-k$, ta bỏ đi qua các đỉnh này và chọn tương tự cho phần các đỉnh còn lại. Như vậy, từ đấy ta luôn có điều phải chứng minh. b). Gọi $O(m,n)$ là số đồ thị $G(M,N,E)$ có số cạnh lẻ, $E(m,n)$ là số đồ thị có số cạnh chẵn, khi đó xét một điểm $i \in M$, nếu đồ thị G bị phụ thuộc $i$ thì dựa vào câu a) sẽ có số đồ thị có số cạnh chẵn và số đồ thị có số cạnh lẻ là bằng nhau (). Với những đồ thị không phụ thuộc vào $i$, khi bỏ i, ta sẽ được số đồ thị có chẵn cạnh là $E(m-1,n)$ và số đồ thị có lẻ cạnh là $O(m-1,n)$. Nếu $i$ có số $deg(i)=2k+1$ thì từ số đồ thị có số chẵn cạnh $E(m,n)$ ta sẽ có được số đồ thị có số lẻ cạnh $k.O(m-1,n)$, tương tự với $O(m,n)$ (1). Khi với $deg(i)=2k+2 > 0$ thì từ số đồ thị có cạnh chẵn $E(m,n)$ ta nhận được số đồ thị có cạnh chẵn là $(k-1)E(m-1,n)$ và tương tự với số đồ thị có cạnh lẻ (2) (sở dĩ được $k-1$ vì ta không xét đến trường hợp $deg(i)=0$ cũng là một số chẵn). Từ (1) và (2) và () ta được: $E(m,n)-O(m,n)=O(m-1,n)-E(m-1,n)=...=(-1)^m(E(1,n)-O(1,n))=(-1)^m$. Vì vậy số đồ thị có số cạnh chẵn không chênh lệch với số đồ thị có số lẻ cạnh quá 1 đơn vị, nên có thể sắp xếp xen kẽ các đô thị có số cạnh chẵn và các đồ thị có số cạnh lẻ với nhau. Bài này bỏ câu a thì vui hơn nhiều nhỉ . __________________ i'll try my best. thay đổi nội dung bởi: quocbaoct10, 10-01-2015 lúc 11:54 AM

16-01-2015, 10:56 PM	#75
vuxuandh +Thành Viên+ Tham gia ngày: Sep 2012 Bài gởi: 4 Thanks: 0 Thanked 3 Times in 3 Posts	Bài 7/b Gọi T(A1, A2, ..., Am-1) là tập hợp các chương trình mà: Tập các nam hát với nữ thứ nhất là A1 ... Tập các nam hát với nữ thứ m -1 là Am -1. Trong mỗi chương trình thuộc T: A1, A2, ..., Am -1 cố định, tính chẵn lẻ số bài hát phụ thuộc vào tập Am các nam hát với nữ m. Tập Am phải chứa các nam chưa được hát tính tới m -1 nữ đầu, và với k nam được hát rồi thì chứa hay không: tùy. Do đó có thể coi Am là tập con của k phần tử, mà ta biết số tập con có chẵn phần tử của một tập hợp bằng số tập con có lẻ phần tử. Vậy trong T(A1, A2, ..., Am-1) số chương trình có chẵn bài hát bằng số chương trình có lẻ bài hát. bài toán được chứng minh. Mọi người cho ý kiến giúp, nếu đúng mình post ý a. thay đổi nội dung bởi: vuxuandh, 16-01-2015 lúc 11:01 PM

Ðiều Chỉnh
Tạo trang in Email trang này
Xếp Bài
Chế độ bình thường Chuyển sang chế độ Pha trộn Chuyển sang chế độ dạng cây

09-01-2015, 06:14 PM	#62
lupanh7 +Thành Viên+ Tham gia ngày: Jul 2011 Bài gởi: 10 Thanks: 7 Thanked 6 Times in 3 Posts	Phần b) bài 7 Gọi a là một học sinh nam Gọi C(n,m) là số lượng chương trình có chẵn bài hát có thể có của một Liên hoan song ca với n học sinh nam và m học sinh nữ. L(n,m) là số lượng chương trình có lẻ bài hát có thể có của một Liên hoan song ca với n học sinh nam và m học sinh nữ. Gọi $A_1, A_2, A_3, A_4$ lần lượt là tập hợp các chương trình có thể có với n học sinh nam và m thuộc loại 1,2,3,4 với: Loại 1: Chương trinh lệ thuộc vào a và có chẵn bài hát Loại 2: Chương trinh lệ vào a và có lẻ bài hát Loại 3: Chương trinh không lệ thuộc vào a và có chẵn bài hát Loại 4: Chương trinh không lệ thuộc vào a và có lẻ bài hát Một chương trình thuộc loại 3 hoặc 4 khi bỏ đi các tiết mục của a sẽ thu được một chương trình với n-1 học sinh nam và m học sinh nữ nên sẽ chứng minh được: $C(n,m)=\|A_1\|+C(n-1,m).(C_m^2+C_m^4+...+C_m^{2[m/2]})+L(n-1,m).(C_m^1+C_m^3+...+C_m^{2[(m-1)/2]+1})$ $L(n,m)=\|A_2\|+L(n-1,m).(C_m^2+C_m^4+...+C_m^{2[m/2]})+C(n-1,m).(C_m^1+C_m^3+...+C_m^{2[(m-1)/2]+1})$ Từ đây suy ra C(n,m)-L(n,m)=L(n-1,m)-C(n-1,m)

09-01-2015, 06:56 PM	#64
Hennmarsk +Thành Viên+ Tham gia ngày: Dec 2014 Bài gởi: 6 Thanks: 4 Thanked 3 Times in 3 Posts	Mình loại được mỗi a=7, a=5 định làm như thế hóa ra sai

10-01-2015, 11:27 AM	#69
ThangToan +Thành Viên+ Tham gia ngày: Nov 2010 Đến từ: THPT chuyên Vĩnh Phúc Bài gởi: 570 Thanks: 24 Thanked 537 Times in 263 Posts	Bài 6. Ta xét phương trình $6a^2x+6ay^2+36z=m$ (1) với nghiệm nguyên dương. Bổ đề. Ta chứng minh số $m=6a^2+36a$ là số nguyên dương lớn nhất để phương trình trên vô nghiệm. Thật vậy, a) với $m=6a^2+36a$ ta chứng minh phương trình sau không có nghiệm nguyên dương: $6a^2x+6ay^2+36z=6a^2+36a$ (2). Từ (2) ta có $z \vdots a \Rightarrow \exists k \in {N^}:z = ka$ Chia hai vế của (1) cho $a$ ta được: $ax+6y+36k=6a+36$ $ \Leftrightarrow a\left( {6 - x} \right) = 6\left( {y + 6k - 6} \right) \vdots a \Rightarrow y + 6k - 6 \vdots a \Rightarrow y + 6k - 6 \ge a$ $ \Rightarrow 6\left( {y + 6k - 6} \right) \ge 6a > \left( {6 - x} \right)a$ vô lý. b) Tiếp theo ta chứng minh rằng với mọi $m \ge 6{a^2} + 36a + 1$ thì phương trình (1) luôn có nghiệm nguyên dương. Do $(a,6)=1$ nên hệ $\left\{ {36.1,36.2,...,36.a} \right\}$ là hệ đầy đủ theo $moda$ suy ra tồn tại $ z \in \left\{ {1,2,...,a} \right\}:36z \equiv n\left( {\bmod a} \right) \Rightarrow \frac{{n - 36z}}{a} \in Z $ Kết hợp với $n - 36z \ge 6{a^2} + 36a - 36a > 0 \Rightarrow \frac{{n - 36z}}{a} \in {N^}$ Mặt khác $\left\{ {6.1,...,6.a} \right\}$ là hệ thặng dư đầy đủ theo $moda$ suy ra tồn tại $y \in \left\{ {1,2,...,a} \right\}$ sao cho $6y \equiv \frac{{n - 36z}}{a}\left( {\bmod a} \right)$. Từ đó suy ra tồn tại số nguyên $x$ sao cho : $\frac{{n - 36z}}{a} - 6y = ax \Leftrightarrow {a^2}x + 6ay + 36z = n$. Tiếp theo ta chứng minh $x$ nguyên dương như sau: Ta có $ax = \frac{{n - 36z}}{a} - 6y = \frac{{n - 36z - 6ay}}{a} \ge \frac{{6{a^2} + 36a + 1 - 36a - 6{a^2}}}{a} > 0 \Rightarrow x > 0$. Vậy luôn tồn tại các số nguyên dương $x,y,z$ thỏa mãn: $6a^2x+6ay+36z=n$. Vậy số lớn nhất thỏa mãn là $m=6a^2+36a$. Vậy bổ đề được chứng minh. Ta quay trở lại bài toán 6 VMO 2015 như sau: Phương trình $6{a^2}x + 6ay + 36z = n \Leftrightarrow 6{a^2}\left( {x + 1} \right) + 6a\left( {y + 1} \right) + 36\left( {z + 1} \right) = n + {a^2} + 6a + 36$ Như vậy bài toán 6 VMO 2015 trở thành phương trình ứng với nghiệm nguyên dương: $6{a^2}\left( {x + 1} \right) + 6a\left( {y + 1} \right) + 36\left( {z + 1} \right) = n + {a^2} + 6a + 36$ b) Áp dụng bổ đề với $m=n+6a^2+6a+36$ ta được $n + {a^2} + 6a + 36 \le 6{a^2} + 36a \Leftrightarrow n \le 5{a^2} + 30a - 36$. Vậy số lớn nhất cần tìm là $n=5a^2+30a-36$. a) TH1. $(a,6)=1$ Theo phần b ta có: $5{a^2} + 30a - 36 < 250 \Leftrightarrow 5{a^2} + 30a < 286 \Leftrightarrow a \in \left\{ {1,2,3,4,5} \right\}$ Dễ thấy với $a=2,3,4$ không thỏa mãn. +) $a=1$ thì chọn nghiệm là $(n,0,0)$. +) $a=5$ ta chứng minh với mọi $n \ge 250$ thì phương trình sau luôn có nghiệm tự nhiên: $25x+30y+36z=n$ Ta có $\left\{ {25.0,25.1,...,25.5} \right\}$ là hệ thặng dư đầy đủ theo $mod6$ nên tồn tại $x \in \left\{ {0,1,...,5} \right\}:n - 25x = 6t$. Do $x\le 5$ nên $n - 25x \ge 250 - 25.5 \Rightarrow t > 20$. Bổ đề. Với mỗi số nguyên dương $t>20$ luôn tồn tại các số tự nhiên $y,z$ sao cho $t=5y+6z$. Thật vậy, ta chứng minh bằng quy nạp theo $t$: Dễ thấy $21=3.5+6,22=2.6+2.5,23=3.6+5,24=4.6+0.5,25=0.6+5. 5$ Do đó với $t>25$ ta có: $t=5+t-5=5+5u+6v=5(u+1)+6v$ do đó theo pp quy nạp bổ đề được chứng minh. Sử dụng bổ đề ta được $n-25=6t=6(5y+6z)$ suy ra $n=25x+30y+36z$. Vậy $a=1, a=5$.

11-01-2015, 01:08 AM	#70
son235 +Thành Viên+ Tham gia ngày: Jan 2010 Bài gởi: 5 Thanks: 31 Thanked 6 Times in 3 Posts	Câu 6b. Trước hết chứng minh bổ đề về số Frobenius đối với hai số $a$, $b$ nguyên tố cùng nhau là $ab-a-b$. Sau đó dùng ý tưởng như bạn Fool’s theorem, ta có đáp số là ${{n}_{\max }}=5{{a}^{2}}+30a-36$. Quay trở lại 6a. Nếu $\gcd (a,6)=d>1$ thì bài toán không thỏa (vì nếu phương trình có nghiệm thì $d\|n$, điều này không thể xảy ra với mọi $n\ge 250$). Nếu $\gcd (a,6)=1$ và $a>1$,theo câu b, để thỏa yêu cầu bài toán thì $5{{a}^{2}}+30a-36<250$, dễ dàng giải được $a\le 5$, do đó $a=5$. Nếu $a=1$ thì bài toán thỏa. Vậy đáp số là $a=1$ và $a=5$.

11-01-2015, 02:38 PM	#71
khanghaxuan +Thành Viên+ Tham gia ngày: Dec 2014 Đến từ: Khánh Hòa Bài gởi: 23 Thanks: 51 Thanked 3 Times in 3 Posts	Bạn nào trình bày rõ ràng bài tổ ngày 1 ra giúp mình với ( bằng truy hồi , kể cả cái hệ thức cũng giải ra giúp mình nhé ! ) . ( Ức chế mấy ngày nay rồi , phải giải stress mới được )

14-01-2015, 05:15 PM	#74
Nam Chung QB +Thành Viên+ Tham gia ngày: Dec 2014 Đến từ: Quảng Bình Bài gởi: 1 Thanks: 0 Thanked 0 Times in 0 Posts	Câu hình ý a : Theo mình nghĩ chỉ cần bình phương là xong