Đến nội dung

Hình ảnh

Marathon Tổ hợp và rời rạc VMF

- - - - - tổ hợp rời rạc marathon

  • Please log in to reply
Chủ đề này có 65 trả lời

#21
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Lời giải bài 5:

Chọn ra 2 số thuộc $a,b$ thuộc $S$ mà $a,b$ phân biệt mà $2a\leq n< 2b$. Xét 1 cặp $(a;b)$ như thế, ta thấy rằng chỉ có 1 cấp số cộng cực đại duy nhất chứa 2 số $a$ và $b$ đó mà không chứa bất kì số nào nằm giữa 2 số đó. Tương tự, 2 cấp số cộng cực đại công sai khác 0 mà có chứa 2 số (a;b) thoả mãn  $2a< n\leq 2b$ và không chứa bất kì số nào nằm giữa 2 số đó thì sẽ trùng nhau. Vì vậy có thể thiết lập 1 song ánh giữa tập các cặp $(a;b)$ vào tập các csc cực đại công sai khác 0.Mà có thể tạo được $n$ csc cực đại công sai =0 nên số các csc cực đại bằng số cách chọn cặp $(a;b)$ cộng thêm $n$ và sẽ bằng : $(\frac{n}{2})(\frac{n}{2})+n$ nếu $n$ chẵn và bằng $(\frac{n-1}{2}+1)(\frac{n-1}{2})+n$ nếu $n$ lẻ.

 

hình như bạn bị thừa TH ví dụ với $n=10$ thì theo bạn có $1$ cấp số cộng cực đại ứng với $2,8$ nhưng thực ra csc này không cực đại vì ta có thể thêm $5$vào để thành csc $2,5,8$


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 27-05-2016 - 13:30


#22
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

 

Bài 5: Cho số nguyên dương $n>1$ và tập $(1,2,...,n)=S$ . Một tập con của $S$ là cấp số cộng cực đại nếu nó là cấp số cộng và không thể bổ sung thêm số nào để thành cấp số cộng cực đại nữa. Tìm số csc cực đại ? 

mà cho mình hỏi thêm vào ở đây là thêm vào $1$ hay nhiều số vì nếu không chỉ cần thêm tất cả các số vào thì nó sẽ thành csc $1,2,...,n$ và csc của ta không cực đại nữa


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 27-05-2016 - 13:31


#23
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Lời giải bài 7:

 

Xét $n$ chia hết cho 3, khi đó chia bảng $2n\times 2n$ thành các bảng $3\times 3$. Từ mỗi bảng $3\times 3$ đó có thể tạo được 1 bàn cờ vua $3\times 3$ để ghép lại thành 1 bàn cờ vua $2n\times 2n$

Xét $n$ không chia hết cho 3, giả sử bảng $2n\times 2n$ ban đầu có thể biến đổi thành 1 bàn cờ vua. Nếu thế thì khi biến đổi được bảng về 1 bảng cờ vua thì luôn có 2 trong 4 góc bảng màu trắng (Vì $2n$ là số chẵn). Giả sử góc trên cùng bên trái màu trắng sau khi ta lập được 1 bàn cờ vua. Ta sẽ đánh số 1,2,3 vào các ô của bảng thoả mãn điều kiện: 

-Ô bên trái trên cùng đánh số 1

-Ô kề trái những ô đánh số 1,2,3 thì được đánh số lần lượt là 2,3,1. Nếu như ô cuối của hàng được đánh số 1,2,3 thì ô đầu tiên của hàng bên dưới hàng đó được đánh số lần lượt là 2,3,1.

Vì $n$ không chia hết cho 3 nên 3 ô liên tiếp nằm trên cùng 1 hàng hoặc cột được đánh cả 3 số 1,2,3. Vì vậy mỗi lần đổi màu thì số ô đen được đánh dấu số 1 hoặc là tăng lên 1, hoặc là giảm 1. Tương tự với các ô đánh số 2,3. Vì vậy số các ô được đánh số 1,2,3 sau lần đổi màu thứ $n+1$ lần lượt khác tính chẵn lẻ với số các ô được đánh số 1,2,3 sau lần đổi màu thứ $n$.Vì vậy tại mọi thời điểm, số các ô dược đánh số 1,2,3 luôn cùng tính chẵn lẻ với nhau. Nhưng nếu xét bàn cờ vua đã cho,vì ô trên cùng bên trái màu trắng nên số các ô được đánh số 1 là $\frac{2n^2-2}{3}$, số các ô được đánh số 2 và 3 là $\frac{2n^2-2}{3}+1$. 3 số này không cùng tính chẵn lẻ nên suy ra giả sử sai

 

Bài 8: Anne và Alice ở 2 phòng khác nhau. Alice đặt 13 quân bài từ Át đến K vào 14 ô trống nằm trên một đường tròn và có 1 ô không đặt lá bài nào, Anne không thể thấy được Alice sắp xếp thế nào. Mỗi lượt Anne sẽ gọi tên 1 lá bài. Nếu lá bài đó nằm cạnh ô trống thì Alice sẽ dịch chuyển lá bài đó về phía ô trống, còn nếu không thì không làm gì cả.Sau 1 số bước thì Anne sẽ dùng hỏi bài.

a/ Anne có một cách nào đó để chắc chắn sau khi dừng hỏi bài thì tất cả các quân bài không còn nằm ở vị trí ban đầu của nó nữa không?

b/  Anne có một cách nào đó để sau chắc chắn sau khi dừng hỏi bài thì quân Át không nằm cạnh ô trống không?


Bài viết đã được chỉnh sửa nội dung bởi JUV: 28-05-2016 - 21:40


#24
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Lời giải bài 7:

Ta đánh số 1,2,3 cho các ô sao cho ô ở góc trái trên cùng đánh số 1, các ô nằm kề phía trái ô 1 đánh số 2, ô nằm kề trái ô 2 đánh số 3, ô nằm kề trái ô 3 đánh số 1. Nếu mà ô cuối cùng của hàng này đánh 1 trong các số 1,2,3 thì ô đầu tiên ở hàng dưới đánh các số lần lượt là 2,3,1. Nếu $n$ là bội của 3 thì các hàng của bảng đều được đánh cùng 1 số. Xét $n=3$ thấy thoả mãn, trường hợp $n=3k$ thì ta có thể chia bảng ra làm $k^2$ ô vuông $3\times 3$ và thay đổi các bảng đấy sao cho bảng to trở thành 1 bàn cờ vua. Xét $n$ không là bội của 3, lúc đó trong 3 ô liên tiếp bất kì đều chứa cả 3 số 1,2,3. Gọi $a_t;b_t;c_t$ lần lượt là số ô đen được ghi số 1,2,3 sau nước đi thứ $t$. Ta thấy rằng trong 1 nước đi, số các ô đen được đánh số 1,2,3 hoặc giảm 1 hoặc tăng thêm 1, vì vậy $a_{t+1};b_{t+1};c_{t+1}$ luôn lần lượt khác tính chẵn lẻ với $a_t;b_t;c_t$. Vì lúc đầu có 0 ô đen được đánh số 1,2,3 nên $a_t;b_t;c_t$ luôn cùng tính chẵn lẻ với nhau với mọi $t$ tự nhiên. Tuy nhiên khi thu được 1 bàn cờ vua thì số các ô đen đánh số 1,2,3 không đôi một cùng tính chẵn lẻ nên không thể thu được 1 bàn cờ vua

 

bạn xem lại đoạn cuối cái (xét bảng 8*8 thì có 12 số 1 10 số 3 và 10 số 2)



#25
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Anne không biết các quân bài được sắp xếp thế nào bạn ạ ( vì ngồi ở $2$ phòng khác nhau)


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 27-05-2016 - 12:49


#26
Visitor

Visitor

    Hạ sĩ

  • Thành viên
  • 66 Bài viết

Lời giải bài 8.


 

a/ thay các lá bài bằng các số từ $1$ đến $13$ . Anne sẽ gọi lần lượt từ số $1$ tới số $13$, lặp lại một số vòng gọi như vậy. Giả sử ô trống nằm giữa $2$ số $i<j$ thì khi gọi đến $i$,số $i$ sẽ chuyển vào chỗ trống. Khi đó sẽ có 2 số cạnh ô trống là $i$ và một số $k$ nữa. Nếu $k>i$ thì khi gọi đến $k$ $k$ k sẽ di chuyển vào ô trống, và $i$ bh ko cạnh ô trống nữa, còn nếu $k<i$ thì $k$ sẽ dịch chuyển vào ô trống trong vòng gọi thứ 2. Tóm lại $i$ sẽ ko ở cạnh ô trống nữa và sẽ có số khác nhảy vào ô trống. Như vậy sau 1 số bước thì các quân bài ko còn ở vị trí ban đầu nữa.

b/Để quân Át, tức số $1$ ko năm cạnh ô trống thì Anne chỉ việc gọi như phần a/ nhưng sẽ bắt đầu gọi từ $2$ đến $13$. Số $1$ sẽ đứng im còn ô trống sẽ thay đổi nên sẽ có lúc nào đó số $1$ ko nằm cạnh ô trống.


Bài viết đã được chỉnh sửa nội dung bởi Visitor: 27-05-2016 - 12:17

__________

Bruno Mars


#27
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

LƯU Ý : Các bạn post bài đừng trích dẫn lại nhé , mong các bạn bỏ chút time xóa các trích dẫn và trả lời theo form mình ghi ở đầu bài viết là . Lời giải bài n : ABCXYZ rồi Đề xuất bài n + 1 nhé

Một số post mình sẽ nhờ các mod xóa hộ nếu nó không cần thiết , lưu ý không spam nhé 

 


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 27-05-2016 - 12:09

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#28
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Lời giải bài 8.


 

a/ thay các lá bài bằng các số từ $1$ đến $13$ . Anne sẽ gọi lần lượt từ số $1$ tới số $13$, lặp lại một số vòng gọi như vậy. Giả sử ô trống nằm giữa $2$ số $i<j$ thì khi gọi đến $i$,số $i$ sẽ chuyển vào chỗ trống. Khi đó sẽ có 2 số cạnh ô trống là $i$ và một số $k$ nữa. Nếu $k>i$ thì khi gọi đến $k$ $k$ k sẽ di chuyển vào ô trống, và $i$ bh ko cạnh ô trống nữa, còn nếu $k<i$ thì $k$ sẽ dịch chuyển vào ô trống trong vòng gọi thứ 2. Tóm lại $i$ sẽ ko ở cạnh ô trống nữa và sẽ có số khác nhảy vào ô trống. Như vậy sau 1 số bước thì các quân bài ko còn ở vị trí ban đầu nữa.

b/Để quân Át, tức số $1$ ko năm cạnh ô trống thì Anne chỉ việc gọi như phần a/ nhưng sẽ bắt đầu gọi từ $2$ đến $13$. Số $1$ sẽ đứng im còn ô trống sẽ thay đổi nên sẽ có lúc nào đó số $1$ ko nằm cạnh ô trống.

Bạn phải chỉ ra xem Anne sẽ chắc chắn các quân bài không ở vị trí đầu sau bao nhiêu bước bởi nếu có 1 quân bài dịch chuyển hết vòng tròn thì sẽ trở lại VT đầu

Mà đáp án câu b là không thể nhé, thử kiểm tra lại suy luận của mình xem, phải  chỉ ra sau một số bước xác định để quân át không nằm cạnh ô trống chứ không phải là chỉ ra tồn tại


Bài viết đã được chỉnh sửa nội dung bởi JUV: 27-05-2016 - 12:16


#29
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Theo mình khi giải bài nên để tác giả confirm lại đáp án rồi mới post bài tiếp theo tránh trường hợp giải sai $=>$ bỏ qua bài


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 27-05-2016 - 12:51


#30
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Bài 8 hình như lời giải của JUV có vấn đề vì xét trường hợp 2 ô đen 1 ô trắng sẽ chuyển thành 2 ô trắng 1 ô đen thì sẽ không đồng dư với nhau (mod 3) 



#31
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết
Theo bạn Long Phi chúng ta sẽ xem xét bài toán của bạn JUV sau
Đề xuất bài 9 : Một tập hợp các số nguyên dương gọi là tốt nếu mỗi phần tử của nó đều không nhỏ hơn số phần tử của chính tập số .Gọi $a_{n}$ là số tập tốt của tập $n$ số nguyên dương đầu tiên và $b_{n}$ là số tập con của tập đó mà cứ hai phần tử bất kì hơn kém nhau ít nhất $2$ đơn vị . Tính $a_{n}-b_{n}$

Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 28-05-2016 - 01:07

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#32
mrjackass

mrjackass

    Trung sĩ

  • Thành viên
  • 110 Bài viết

Lời giải Bài 9:

Xét $a_n$. Số các tập thuộc $a_n$ có $i$ phần tử là $\binom{n-i+1}{i}$ vì ta chỉ chọn các phần tử $i, i+1, ...,n$

Do đó $a_n=\sum_{i<n-i+1}\binom{n-i+1}{i}$

Xét $b_n$. Ta đếm số các tập thuộc $b_n$ có $i$ phần tử. Gọi các phần tử đó là $x_1 < x_2 < ... <x_i$ thì theo đề bài $1 \leq x_1 < x_2 - 1 < x_3 -2 ... <x_i-(i-1)\leq n -i +1$. Đặt $y_i=x_i-(i-1)$ thì số tập thuộc $b_n$ có $i$ phần tử bằng số các dãy $y_1,y_2,..,y_i$ mà $1\leq y_1 < y_2 <...<y_i \leq n-i+1$ hay bằng $\binom{n-i+1}{i}$. Do đó $b_n=\sum_{i<n-i+1}\binom{n-i+1}{i}$ hay ta có $a_n=b_n$

 

Đề xuất Bài 10: Xét một số tự nhiên được biểu diễn trong hệ nhị phân. Ta gọi một khoảng cách nhị phân là một khoảng gồm các số $0$ liền nhau và ở hai đầu của nó là hai số $1$. Ví dụ số $548=1000100100_{2}$ có hai khoảng cách nhị phân là $000$ và $00$.

Hỏi từ $1$ tới $4095$ có bao nhiêu số mà độ dài các khoảng cách nhị phân của nó nhỏ hơn hoặc bằng $3$?


Bài viết đã được chỉnh sửa nội dung bởi mrjackass: 28-05-2016 - 20:04

420 Blaze It Faggot


#33
bvd

bvd

    Binh nhất

  • Thành viên
  • 31 Bài viết

Ý tưởng ý a bài 10 (thế này chắc chưa là bài giải được)

Gọi $x$ là một số thỏa mãn yêu cầu bài toán, ta có dãy không âm $a$ tăng có $n$ phần tử duy nhất thỏa mãn

$x = \sum_{i=1}^{n} 2^{a_i}$ với $a_i$ là phần tử thứ $i$ của dãy a.

Do các khoảng cách nhị phân của $x$ nhỏ hơn hoặc bằng 3 nên $a_{i+1}-a_{i} \leq 4$ $\forall i<n$.

Lại có $1 \leq x \leq 4095$ nên $a_{n}<12$

Gọi $f(m;n)$ là số dãy số nguyên không âm $a$ tăng có $n$ phần tử, $a_n = m$ thỏa mãn $a_{i+1}-a_{i} \leq 4$ $\forall i<n$, ta có công thức truy hồi:

$f(m;n) = 0$ nếu $m<0$;

$f(m;n) = 1$ nếu $m \geq 0$ $n=1$;

$f(m;n) = f(m-1;n-1) + f(m-2;n-1) + f(m-3;n-1) + f(m-4;n-1)$ nếu $m \geq 0$ và $n > 1$

Do số lượng số $x$ thỏa mãn yêu cầu bài toán bằng số lượng dãy không âm $a$ tăng có $n$ phần tử thỏa mãn $a_{n}<12$ và $a_{i+1}-a_{i} \leq 4$ $\forall i<n$ nên kết quả bài toán là $\sum_{i=0}^{11} \sum_{j=1}^{12} f(i;j) = 3333$

Mình quay lui trên $Pascal$ ra $3095$ nên có thể bài mình bị sai đâu đó.


Bài viết đã được chỉnh sửa nội dung bởi bvd: 28-05-2016 - 22:35


#34
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

À sr, ý b bị xoá mất rồi, nếu như không ai làm được thì mình có thể gợi ý như sau:

-Đầu tiên xét $a_n$ là số các dãy nhị phân thoả mãn dãy đó có độ dài $n$ và số 1 đứng ở đầu trái của dãy và các khoảng cách nhị phân không quá 3. Ta có khoảng cách giữa số 1 thứ nhất và số 1 thứ 2 không quá 3 nên có 3 cách chọn số 1 thứ 2, từ đó có dãy truy hồi:

$a_{n+4}=a_{n+3}+a_{n+2}+a_{n+1}+a_n$ với $a_{1}=1;a_{2}=2,a_{3}=4,a_{4}=8$ (1)

-Tiếp theo xét các dãy nhị phân có dạng $x_{2}=101010...101$ với độ dài $n$ ( n là số lẻ). Ta đếm các số thoả mãn đề bài mà không vượt quá $x$ mà biểu diễn nhị phân của nó có độ dài $n$ , gọi số các số đó là $b_n$. Vì số 1 đầu tiên đã xác định nên có 4 cách chọn số 1 thứ 2:

-Nếu số 1 thứ 2 nằm ngay sau số 1 thứ nhất thì không có cách chọn dãy nhị phân thoả mãn

-Nếu nằm cách số 1 thứ nhất 1 số 0 thì có $b_{n-2}$ cách chọn dãy nhị phân thoả mãn vì tất cả các dãy nhị phân đó đều lớn hơn $x$

-Nếu nằm cách số 1 thứ nhất 2 số 0 thì có $a_{n-3}$ cách chọn dãy nhị phân thoả mãn

-Tương tự, nếu cách 3 số 0 thì có $a_{n-4}$ cách chọn dãy nhị phân thoả mãn

Ta có dãy truy hồi $b_{n}=b_{n-2}+a_{n-3}+a_{n-4}$

Từ đó cộng thêm kết quả câu a thì dễ dàng tìm ra đáp số (Câu a là $3095$ nhé, còn câu b là $3829$ )

P/s: Từ (1) ta cũng có thể dễ dàng suy ra câu a. Mà bài 8 của mình sao vẫn chưa có ai giải vậy  :mellow:


Bài viết đã được chỉnh sửa nội dung bởi JUV: 30-05-2016 - 07:48


#35
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Lời giải bài 10 : Trước tiên ta để ý rằng $4095=111111111111_{2}$ là số lớn nhất có $12$ chữ số trong hệ nhị phân

Nên ta đặt một số từ $1$ đến $4095$ là $\overline{a_{1}a_{2}....a_{12}}_{(2)}$ 

Gọi số số $1$ là $i$ thì có $12-i$ số $0$ , khoảng cách giữ hai số một là một trong $4$ số $0,1,2,3$

Xét dạng sau $1....1.....1....1....1....$

Trong đó có $i>1$ số $1$  , tổng các khoảng cách bằng tổng số các số $0$ là $12-i$

Vậy ta tìm số nghiệm nguyên của phương trình $x_{1}+x_{2}+....x_{i}=12-i$ ( vì lưu ý là nó không bắt đầu từ $0$)

Trong đó $0 \leq x_{i} \leq 3$

Quanh đi quẩn lại vẫn phải đệ quy sorry nãy làm sai , gọi số nghiệm của $\sum_{i=1}^{m}x_{i}=n$ là $S(m,n)$ với $0\leq x_{i} \leq 3$

Xét số $x_{1}=0$ thì số nghiệm là $S(i-1,12-i)$

Tương tự suy ra $S(i,12-i)=S(i-1,12-i)+S(i-1,11-i)+S(i-1,10-i)+S(i-1,9-i)$ 

Quy ước nếu $n>m$ thì $C_{m}^{n}=0$

Vậy đáp số là $\sum_{i=1}^{12}S(i,12-i)$ 

Buồn thế  :(  :(  :(  :(

Bài $8$ của JUV tẹo mình sẽ để lên đầu topic nhé 


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 28-05-2016 - 22:26

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#36
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Được sự cho phép của bangbang1412, mình sẽ đề xuất tiếp bài $11$

Bài 11: Trên $1$ đoạn thẳng từ trái sang phải có đặt $21$ hộp gỗ, trong mỗi hộp gỗ có đặt $1$ vài hòn bi. Biết rằng số hòn bi trong mỗi hộp gỗ nhận $1$ trong các giá trị từ $1$ đến $21$ và không có $2$ hộp nào chứa cùng số bi. Mỗi bước ta sẽ chọn $2$ hộp gỗ bất kì và nếu $1$ hộp chứa nhiều bi hơn hộp kia thì ta sẽ chuyển từ hộp nhiều bi hơn sang hộp ít bi hơn $1$ số bi đúng bằng số bi mà hộp ít bi hơn có trước khi chuyển bi. Hỏi có thể luôn chuyển được bi sao cho sau các bước chuyển đó,$ 21$ hộp có số bi nhận $1$ trong các giá trị từ $1$ đến $21$, không có $2$ hộp nào có cùng số bi và số bi của các hộp từ trái sang phải sắp xếp theo thứ tự tăng dần?


Bài viết đã được chỉnh sửa nội dung bởi JUV: 29-05-2016 - 01:03


#37
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Bài $10$ chạy py thử thì ra $3095$ thật, Bằng xem lại code đi


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 28-05-2016 - 22:48


#38
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Lời giải bài 8:

a/ Anne có thể gọi tên bài để đạt được mục đích: cô sẽ gọi $13$ lần, mỗi lần sẽ gọi lần lượt tên các lá bài từ Át đến K.Xét 1 lần gọi bất kì, không mất tính tổng quát, giả sử quân bài đầu tiên được di chuyển di chuyển theo chiều kim đồng hồ thì lúc đó quân bài thứ 2 được di chuyển là quân bài nằm cạnh ô trống và khác quân bài thứ nhất. Vì vậy quân bài đó sẽ di chuyển theo chiều kim đồng hồ, tương tự với lá bài thứ 3,4,.... Vì vậy mỗi quân bài được di chuyển sau mỗi lần đọc bài thì sẽ di chuyển theo 1 chiều nhất định. Xét sau lần đọc 1, xét 2 quân bài $a$,$b$ nằm cạnh ô trống. Nếu quân $b$ nằm bên phải, $a$ nằm bên trái ô trống thì nghĩa là trong lần đọc đầu, quân $a$ được di chuyển và quân $b$ không được di chuyển. Tất nhiên là quân $b$ được đọc trước $a$ vài nếu không thì nó sẽ nằm bên phải ô trống. Vì quân $b$ đọc trước $a$ nên trong lần đọc thứ 2 thì nó sẽ di chuyển về phía ô trống. Vì vậy sau mỗi lần đọc, có ít nhất $1$ quân không được di chuyển từ những lần trước được phép di chuyển theo chiều kim đồng hồ. Vì có $13$ lần đọc nên cả $13$ lá bài đều được di chuyển theo chiều kim đồng hồ ít nhất $1$ lần và vì trong mỗi lần, mỗi quân bài chỉ di chuyển tối đa 1 lần nên trong cả $13$ lần, $13$ quân bài di chuyển theo chiều kim đồng hồ nhiều nhất $13$ lần và ít nhất $1$ lần nên sau $13$ lần đọc thì các quân bài sẽ không còn ở vị trí cũ.

b/ Anne không thể đạt được mục đích nếu không có may mắn. Thât vậy nếu Alice sắp xếp bộ bài sao cho quân Át nằm cạnh ô trống, gọi đó là trạng thái 0 và Anne đưa Alice 1 tờ giấy ghi những lá bài mình sẽ gọi theo thứ tự nhất định từ trái sang phải cho đến khi dừng gọi. Alice sẽ ghi lại các quân bài đó trên bảng theo thứ tự ngược lại ( ví dụ như nếu Anne ghi $A,5,Q,K$ thì Alice sẽ ghi $K,Q,5,A$) và thực hiện các bước:

Gọi $n$ là số các lá bài được ghi trên giấy. Anne sẽ nhìn lên bảng và trong bước thứ $i$, xét quân bài thứ $i$ từ trái sang phải. Nếu lúc này quân bài đó nằm cạnh ô trống thì dịch chuyển quân bài đó về ô trống, còn nếu không thì không làm gì cả và chuyển qua bước $i+1$. Gọi trạng thái $i$ là cách sắp xếp bộ bài sau bước thứ $i$ thì cuối cùng sau $n$ bước thì bộ bài sẽ đạt trạng thái $n$. Ta chứng minh rằng nếu bộ bài được sắp xếp thế này và Anne đọc đúng hững quân bài được viết trên giấy theo đúng thứ tự thì cuối cùng, quân Át sẽ nằm cạnh ô trống. Ta sẽ chứng minh rằng sau lần đọc thứ $i$ thì bộ bài của $Anne$ sẽ trở về trạng thái $n-i$. Ta thấy trong lần đọc thứ $i$ thì Anne sẽ đọc quân bài thứ $n-i+1$. Ta thấy mệnh đề hiển nhiên đúng với $i=0$ vì Anne chưa đọc lá bài nào. Giả sử mệnh đề đúng với $i=k$, xét lần đọc thứ $k+1$. Trong lần này Anne sẽ đọc quân bài thứ $n-k$ trên bảng và bộ bài của Alice đang ở trạng thái $k$. Nếu quân bài Anne đang đọc không nằm cạnh ô trống trong trạng thái $n-k$ thì trong trạng thái $n-k-1$ nó cũng vậy, vì vậy nên Alice sẽ không làm gì và bộ bài sẽ trở về trạng thái $n-k-1$. Nếu quân bài đó nằm cạnh ô trống thì trong trạng thái $n-k-1$ nó cũng nằm cạnh ô trống nhưng ngược hướng so với trạng thái $n-k$, lúc đó Alice sẽ dịch chuyển quân bài đó về ô trống và bộ bài trở về trạng thái $n-k-1$. Chứng minh quy nạp hoàn tất. Vì vậy sau $n$ lần đọc thì bộ bài trở về trạng thái 0. Nhưng trong trạng thái này quân Át nằm cạnh ô trống nên Anne không thể đạt được mục đích. Vậy cho dù Anne có đọc thế nào thì cũng có 1 cách sắp xếp bộ bài sao cho cuối cùng quân Át cũng ở cạnh ô trống

Lời giải bài 11:

Với mỗi số $2\leq a\leq 21$ thì ta sẽ gọi $b$ là 1 số đối của $a$ nếu

-)$b<a$

-)Xét hộp $A$ chứa $a$ viên bi và hộp $B$ chứa $b$ viên bi. Sau một số bước chuyển bi giữa 2 hộp này thì hộp $A$ chứa $b$ viên bi và hộp $B$ có $a$ viên bi.

Nếu $a$ là số chẵn thì $a$ có 1 số đối là $\frac{a}{2}$

Nếu $a$ là số lẻ thì ta sẽ xây dừng cặp $(a;b)$ bới $b$ là số đối của $a$ như sau:

$(3;2),(5;4),(7;4),(9;8),(11;4);(13;4);(15;4);(17;16);(19;8);(21;4)$

Ta sẽ chứng minh bài toán tổng quát hơn:  Với $(a_{1};a_{2};...;a_{n})$ là 1 hoán vị của $(1;2;...;n)$ với $n\leq 21$ thì ta có thể thực hiện chuyển đổi giữa các hộp sao cho hộp thứ $i$ từ trái sang phải chứa $a_i$ viên bi. Mệnh đề đúng với $n=1,2$, giả sử mệnh đề đúng với $n=k<21$, xét $n=k+1$. Giả sử lúc đầu hộp $x$ chứa $k+1$ viên bi và 1 hộp thứ $y$ với $y\leq 21$ bất kì. Khi đó với $k$ hộp còn lại, theo mệnh đề quy nạp thì ta có thể chuyển bi sao cho với $b$ là số đối của $k+1$ thì hộp $y$ chứa $b$ viên bi. Ta thực hiện chuyển đổi liên tiếp giữa 2 hộp này thì cuối cùng hộp $y$ chứa $k+1$ viên bi, hộp $x$ chứa $b$ viên bi. Cho $y$ chạy từ $1$ đến $k+1$ thì lúc đó ta có thể di chuyển bi sao cho tất cả mọi hộp đều có thể chứa $k+1$ viên bi, hoán vị $k$ hộp còn lại ta sẽ tạo ra được tất cả các hoán vị của $(1;2;...;k+1)$. Vậy mệnh đề đúng với $n=k+1$, vì vậy mệnh đề đúng với $n=21$. Vì $(1;2;...;21)$ là 1 hoán vị của $(1;2;...;21)$ nên ta có thể chuyển bi sao cho các hộp chứa số bi thoả mãn

Bài 12: (USAMO 2016)

Cho $n,k$ là hai số nguyên, $n\geq k\geq 2$. Bạn tham gia vào một trò chơi với một phù thuỷ 

Phù thuỷ có $2n$ lá bài, với mỗi $i=1,2,...,n$ thì có đúng hai lá bài cùng được đánh số là $i$. Lúc đầu, phù thuỷ sắp úp tất cả lá bài trên một hàng, thứ tự bất kỳ.
Về phần bạn, bạn sẽ lặp lại các thao tác sau: chỉ vào $k$ lá bài bạn muốn chọn, phù thuỷ sẽ lật ngửa lên hộ bạn. Nếu lật lên, có hai tấm thẻ cùng được đánh 1 số, bạn thắng, game sẽ kết thúc. Nếu ngược lại, phù thuỷ sẽ hoán vị $k$ lá bài đó và lật úp chúng lại. Mỗi lần bạn làm vậy là một bước đi. Và bạn sẽ lặp lại thao tác trên.
Ta gọi game này là thành công nếu tồn tại $m$ nguyên dương nào đó và một chiến thuật nào đó ở tối đa $m$ bước đi, không quan trọng việc phù thuỷ xáo trộn bài của bạn.

Hỏi với $n$ và $k$ nào thì bạn có thể chiến thắng?


Bài viết đã được chỉnh sửa nội dung bởi JUV: 01-06-2016 - 09:00


#39
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 Bài viết

Lời giải bài 12:

Trước tiên, ta chứng minh với $k=n$ thì sẽ không có chiến thuật đảm bảo thắng.

Khi $k=n$ thì trường hợp xấu nhất ở lần chọn bài đầu tiên là ta chọn đúng $n$ lá bài mà các số trên đó là một hoán vị của $(1,2,...,n)$. Giả sử ở lần tiếp theo, ta chọn $l$ lá bài cũ và $n-l$ lá bài mới, khi đó tồn tại ít nhất 1 cách phù thuỷ xáo bài sao cho $n$ lá bài ở lần chọn này vẫn là một hoán vị của $(1,2,...,n)$. Dẫn tới, ở mọi lần chọn bài, ta đều có thể chọn phải $n$ lá bài mà các số trên đó là một hoán vị của $(1,2,...,n)$, hay nói cách khác là ta không thể đảm bảo có thể thắng trong hữu hạn lần chọn.

Ta sẽ chứng minh tiếp, với $2\le k<n$ thì ta sẽ có chiến thuật thắng bất chấp mọi cách xáo trộn bài của phù thuỷ.

Đánh số các quân bài từ $1$ đến $2n$. Giả sử mỗi lần bốc bài dưới đây đều rất "đen đủi" tức là không có 2 lá bài nào trong $k$ lá bài được chọn ghi cùng 1 số.

Đầu tiên ta sẽ bốc $k$ lá bài $(1,2,...,k)$ thì ta sẽ biết được tập hợp các số ghi trên các quân bài này. Sau đó, ta sẽ bốc $k$ lá bài $(2,3,...,k+1)$ thì ta sẽ biết được giá trị ghi trên lá bài thứ $k+1$ và từ đó ta sẽ biết được $k+1$ lá bài đầu tiên chứa các số như thế nào (cho dù xáo trộn các lá bài thì tập các số này vẫn không đổi). Cứ tiếp tục bốc $k$ lá bài $(i,i+1,...,i+k-1)$ với $i$ nhận giá trị lần lượt từ $3$ đến $2n-k$, khi đó ta sẽ biết được $2n-1$ lá bài đầu tiên chứa các số như thế nào. Từ đó ta sẽ suy ra được giá trị ghi trên lá bài thứ $2n$.

Bắt đầu lại quá trình trên một lần nữa theo cách tương tự, ta sẽ xác định được số ghi trên lá bài thứ $2n-1$. Cứ như vậy, ta sẽ xác định được giá trị ghi trên $2n-k$ lá bài từ $k+1$ đến $2n$.

Theo nguyên lý Dirichlet thì ta sẽ chọn được 2 lá bài ghi cùng 1 số, như vậy lần chọn cuối cùng này ta hoàn toàn có thể chọn được $k$ lá bài mà có 2 lá bài ghi cùng 1 số.

 

Mình xin phép đề xuất 1 bài tương đối dễ thở để các bạn có động lực với topic này hơn.

Bài 13: (Nguồn: Sưu tầm)

Cho $n$ là số nguyên dương, $n\ge 2$. Xét tập $X_n$ gồm các điểm nguyên $(x;y)$ trên mặt phẳng tọa độ $Oxy$ với $1\le x,y\le n$. Gọi $S_k$ là số cặp điểm là cặp đỉnh chung của $k$ hình vuông có các đỉnh thuộc $X_n$ với $k=\overline{0;3}$. Chứng minh rằng: $S_0=S_2+2S_3$.



#40
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Bạn xem lại đề 13 nhé. Trong TH $n=3$ thì $S_{3}=0$;$S_{2}=8$;$S_{0}=12$


Bài viết đã được chỉnh sửa nội dung bởi JUV: 03-06-2016 - 11:08






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: tổ hợp rời rạc, marathon

2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh