Bữa nay có một số bài toán tổ hợp nên share mọi người
Bài $1$ : Cho $n$ số thực lớn hơn $1$ trên bảng thỏa mãn . Mỗi phép biến đổi được phép xóa đi $2$ số $a,b$ trên bảng và thay vào đó là $(a,b)$ . Chứng minh rằng số còn lại cuối cùng trên bảng không phụ thuộc thứ tự xóa nếu .
$a)$ $(a,b)=ab+a+b$
$b)$ $(a,b)=\frac{ab}{1+a+b}$
$c)$ $(a,b)=\frac{a+b-2ab}{1-ab}$
Chứng minh :
Các bài toán này có thể dùng bất biến để xóa , và bất biến này thông thường là số cuối cùng trên bảng , lời giải này chỉ viết các biến đổi
$a)$ Ta có $(a,b)+1=(a+1)(b+1)$
$b)$ Ta có $\frac{1}{(a,b)+1}=\frac{(a+1)(b+1)}{ab}$
$c)$ Ta có $\frac{1}{(a,b)-1}=\frac{1}{a-1}+\frac{1}{b-1}+1$
Nhưng nếu thay $(a,b)$ bằng các biểu thức phức tạp hơn thì sao ? Không dễ dàng biến đổi, nhưng có một cách , nhìn qua ba phần trên ta dễ dàng suy ra số còn lại không phụ thuộc thứ tự xóa nếu nó thỏa mãn
$$(a,b)=(b,a),((a,b),c)=(a,(b,c))$$
Tức là phép biến đổi đối xứng và kết hợp , tuy không cho ta biết được số cuối cùng như chắc chắn số cuối cùng sẽ không phụ thuộc thứ tự xóa . Vì rõ ràng biến đổi này dễ hơn .
Bài $2$ : Cho cặp số $(a,b) \in N_{*}^{2}$ . Mỗi bước ta chọn một cặp $(x,y)$ trên bảng và viết thêm lên đó một trong ba cặp $(x-y,y),(x+y,y),(y,x)$ ( $(x-y,y)$ được viết nếu $x>y$ ) . Tìm tất cả các cặp số có nhận được trên bảng ?
Chứng minh :
Rõ ràng ta có $gcd(x-y,y)=gcd(x+y,y)=gcd(x,y)$ với mọi $x,y$ . Bằng định lý Bezout và phép quy nạp ta chứng minh tất cả các cặp mà $gcd(x,y)=d$ đều có thể được đi qua .
Một cách ngắn gọn hơn lấy $(x,y)^{-1}=(y,x),(x-y,y)^{-1}=(x+y,y)$ cho ta đpcm . ( hàm ngược ) .
Bài $3$ : Một quân cờ ở điểm $(1,1)$ của lưới ô vuông . Khi quân cờ ở điểm $(x,y)$ nó có thể di chuyển đến các điểm $(x,2y),(2x,y),(x-y,y),(x,y-x)$ ( có $x-y$ nếu $x>y$) . Hỏi quân cờ ban đầu có thể đi đến những điểm nào ?
Chứng minh :
Ta chứng minh tất cả các cặp $(x,y)$ mà $gcd(x,y)=2^{k}$ với $k$ tùy ý đều có thể đi qua .
Rõ ràng ta có
$$gcd(x,y)=(2x,y),(x,2y),(x-y,y),(x,y-x)$$
Xét hàm ngược tương ứng
$$(x,y)=(\frac{x}{2},y),(x,\frac{y}{2}),(x+y,y),(x,x+y)$$
Ta chứng minh $(a,b)$ có thể đi ngược vể $(1,1)$ với $(a,b)=1$ thì $(2^{m}a,2^{m}b)$ cũng đi được về $(1,1)$ . Sử dụng đơn biến , nếu $x>y$ mà có $(x+y,y) \to (\frac{x+y}{2},y)<(x,y)$ . Nói chung tổng của chúng luôn giảm nên một lúc nào đó sẽ phải về $(1,1)$ .
Bài $4$ : Ban đầu trên bảng cho một số nguyên dương $n$ , mỗi bước chọn một số $x$ trên bảng và có thể viết thêm một trong hai số $2x+1$ hoặc $\frac{x}{x+2}$ . Sau một số hữu hạn bước ta nhìn thấy trên bảng xuất hiện số $2016$ . Chứng minh rằng $n=2016$
Chứng minh :
Xét hàm số
$$f : Q \to \left \{ 0,1 \right \}^{2}$$
$$f(\frac{p}{q})=(x_{p},x_{q})$$
Trong đó $x_{p},x_{q}$ là số dư của $p,q$ khi chia cho $2$ và $gcd(p,q)=1$
Rõ ràng ta có $f(2016)=(0,1)$
Nếu có $f(\frac{p}{q})=(1,1)$ thì phép biến đổi luôn cho $(1,1)$
Nếu có $f(\frac{p}{q})=(0,1)$ dùng phép $2x+1$ luôn cho ra $(1,1)$ và trở về TH trước .
Nếu có $f(\frac{p}{q})=(1,0)$ dùng phép $\frac{x}{x+2}$ cũng cho ra trường hợp đầu .
Vậy để từ $n$ đến $2016$ thì nó chỉ được dùng một trong hai phép
$$f=(0,1)$$ ( dùng $\frac{x}{x+2}$)
$$f=(1,0)$$ ( dùng $2x+1$ )
Rõ ràng nếu $f(\frac{p}{q})=(0,1)$ mà dùng $\frac{x}{2}$ thì được $\frac{\frac{p}{2}}{\frac{p}{2}+q}$ , bất biến là tổng của tử và mẫu không đổi , tương tự với $(1,0)$ dùng $2x+1$ .
Vậy tổng của tử và mẫu ban đầu không đổi nghĩa là $n+1=2016+1$ , vậy cho ta $n=2016$ ( đpcm )
Bài $5$ : Ban đầu trên bảng có một số thực $a>1$ , mỗi bước chọn ra số $x$ và có thể viết thêm một trong hai số $2x$ hoặc $\frac{x}{x-1}$ lên bảng . Tìm tất cả các số có thể nhận được sau phép biến đổi .
Chứng minh :
Để ý phép biến đổi sẽ không thay đổi tử , chỉ thêm các số $2$ vào tức là tử số sẽ có dạng $2^{l}.a$ , và các số trên bảng luôn $>1$ , ta sẽ tìm nó ở dạng $\frac{2^{l}.a}{A}>1$ với $A$ nào đó tìm sau . Ở đây ta sẽ chứng minh tất cả các số trên bảng có dạng $A \in \left \{1,2^{l}a-1,ma+1,ma-1 \right \}$ với $(0< m < 2^{l})$ . Chứng minh bằng quy nạp theo $l$ .
Bài $6$ : Cho $90$ viên bi gồm $45$ viên xanh và $45$ viên đỏ xếp thành một hàng . Chứng minh rằng với mọi cách xếp luôn có $30$ viên liên tiếp mà trong đó gồm $15$ viên xanh và $15$ viên đỏ .
Chứng minh :
Xét tập các số liên tiếp từ $S_{i}$ gồm các số từ $i$ đến $i+29$ với $1 \leq i \leq 61$ . Gọi $x_{i}$ là số viên bi xanh trong $S_{i}$ ta có
$$x_{1}+x_{31}+x_{61}=90$$
$$|x_{i}-x_{i+1}|\leq 1$$
Vậy nghĩa là tồn tại $x_{h}=15,x_{s} \leq 14,x_{t} \geq 16,x_{s}+x_{h}+x_{t}=45$ , ta có $x_{h}$ thỏa mãn bài toán .
Bài $7$ : Viết các số nguyên dương lên bảng ô vuông $n^{2}$ . Hiệu hai số ở hai ô có cạnh chung không vượt quá $1$ . Chứng minh rằng có một số xuất hiện ít nhất $n$ lần .
Bài $8$ : Trên bảng ban đầu có cặp số $(a,b)$ với $a<b$ là hai số nguyên dương . Mỗi bước chọn một cặp $(x,y)$ trên bảng và viết thêm một trong hai cặp $(x+1,y+1)$ hoặc $(\frac{x}{2},\frac{y}{2})$ nếu $x \equiv y \equiv 0(mod 2)$ hoặc là chọn hai cặp $(x,y)$ và $(y,z)$ rồi viết thêm cặp $(x,z)$ . Tìm tất cả các cặp số có thể nhận được ?
Hai bài thêm cuối chưa giải , thấy hay quá nên share cho mọi người . Ghé thăm blog của tôi ở đây
Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 31-07-2016 - 01:46
