Đế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

#41
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 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 hoàn toàn đúng bạn ạ.

Với $n=3$ thì $S_0=8$ bạn nhé, chỉ có 8 cặp điểm nằm trên đường chéo của các hình chữ nhật $1\times 2$ mới thuộc $S_0$ thôi.



#42
JUV

JUV

    Trung sĩ

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

Đề bài hoàn toàn đúng bạn ạ.

Với $n=3$ thì $S_0=8$ bạn nhé, chỉ có 8 cặp điểm nằm trên đường chéo của các hình chữ nhật $1\times 2$ mới thuộc $S_0$ thôi.

Thế còn 2 cặp điểm $(2;3),(2;1)$ và $(1;2),(3;2)$ có phải là 2 đỉnh của hình vuông nào đâu

P/s: Thật ra mình đếm thì $S_{0}=10$ chứ không phải $12$



#43
IMOer

IMOer

    Hạ sĩ

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

square.png

 

Các cặp điểm đó là các cặp đỉnh của hình vuông đỏ trong hình đính kèm.



#44
IMOer

IMOer

    Hạ sĩ

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

Cũng đã lâu mà chưa ai giải quyết bài 13. Mình xin phép đăng luôn bài tiếp theo, nếu trong vòng 2 ngày tới không ai giải bài 13 thì mình sẽ đăng lời giải.

 

Bài 14: Có 2 con châu chấu nằm tại 2 điểm nguyên trên mặt phẳng toạ độ. Mỗi lần thổi còi, có đúng 1 con châu chấu nhảy tới một điểm nguyên khác sao cho khoảng cách giữa 2 con châu chấu luôn không đổi. Hỏi sau hữu hạn lần thổi còi, 2 con châu chấu có thể đổi chỗ cho nhau được không? (mỗi con sẽ nhảy tới vị trí ban đầu của con kia)



#45
JUV

JUV

    Trung sĩ

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

Lời giải bài 14:

Đánh dấu màu xanh tất cả vị trí mà con châu chấu đầu tiên nhảy được tới, màu đỏ các vị trí mà con thứ 2 có thể nhảy được tới. Gọi $d$ là khoảng cách của 2 con châu chấu, đặt $d^2=2^tq$ ($q$ là số lẻ). Xét 1 thời điểm bất kì con châu chấu đầu tiên ở vị trí $A(x_1;y_1)$, con thứ 2 ở vị trí $B(x_2;y_2)$. Giả sử con châu chấu đầu tiên nhảy từ $A$ đến $C(x_3;y_3)$, ta có $(x_1-x_2)^2+(y_1-y_2)^2=(x_3-x_2)^2+(y_3-y_2)^2=d^2=2^tq$.

Đặt $x_1-x_2=a_1; y_1-y_2=b_1; x_3-x_2=a_2; y_3-y_2=b_2$

Nếu $t$ là số chẵn, đặt $t=2n$, lúc đó cả $a_1;a_2;b_1;b_2$ đều chia hết cho $2^n$, vì vậy $(a_1-a_2)^2+(b_1-b_2)^2$ chia hết cho $2^{2n+1}$ hay $(x_1-x_3)^2+(y_1-y_3)^2$ chia hết cho $2^{t+1}$

Nếu $t$ là số lẻ, đặt $t=2n+1$, lúc đó cả $a_1;a_2;b_1;b_2$ đều chia hết cho $2^n$ nhưng không chia hết cho $2^{n+1}$. Đặt $a_1=2^na; a_2=2^nb; b_1=2^nc; b_2=2^nd$, có $a,b,c,d$ đều không chia hết cho 2 nên $(a_1-a_2)^2+(b_1-b_2)^2=2^{2n}((a-b)^2+(c-d)^2)$ chia hết cho $2^{2n+2}$ hay chia hết cho $2^{t+1}$ ( Vì $(a-b)^2+(c-d)^2$ chia hết cho $4$)

Trong cả 2 trường hợp thì $(x_1-x_3)^2+(y_1-y_3)^2$ đều chia hết cho $2^{t+1}$. Từ đó có thể chứng minh rằng bình phương khoảng cách của 2 điểm xanh bất kì trên toạ độ đều chia hết cho $2^{t+1}$. Vì vậy khoảng cách giữa 2 điểm xanh bất kì đều khác $d$. Vì vậy không có điểm nào trên toạ độ tô cả 2 màu xanh và đỏ. Cho nên con châu chấu thứ 2 không thể nào nhảy đến bất kì điểm nào mà con thứ nhất có thể nhảy đến, tương tự với con thứ nhất. Vì vậy 2 con châu chấu không thể đổi chỗ cho nhau

Bài 15: 

Một ảo thuật gia với $1$ bộ bài có $52$ quân bài, có $4$ loại bài là cơ, chuồn, rô, tép, mỗi loại bài có $13$ quân bài. Đầu tiên nhà ảo thuật sẽ đưa bộ bài cho khán giả xào bài, tất cả các quân bài sau khi được xào lại được đặt úp, chồng lên nhau. Trợ thủ của nhà ảo thuật được quyền xem thứ tự các quân bài sau đó viết $1$ trong $2$ số $0$ hoặc $1$ vào mặt sau mỗi quân bài nhưng không được sắp xếp lại bộ bài và cũng không được nói cho nhà ảo thuật biết thứ tự của bộ bài. Mỗi lượt nhà ảo thuật sẽ đoán loại bài của lá bài trên cùng của xấp bài, sau đó loại nó ra khỏi bộ bài. Nhà ảo thuật cứ tiếp tục như thế trong $52$ lượt. Hỏi có chiến lược nào giúp anh ta đoán được đúng loại bài của ít nhất $30$ quân bài không?


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


#46
IMOer

IMOer

    Hạ sĩ

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

Lời giải bài 13:

Gọi ${{P}_{n}}$ là số hình vuông có các đỉnh thuộc ${{X}_{n}}$.

Nhận xét: từ một hình vuông cạnh $s$ có cạnh song song với trục tọa độ, ta có thể dựng được thêm $s-1$ hình vuông nội tiếp.

Mà có ${{(n-s)}^{2}}$ hình vuông cạnh $s$ có cạnh song song với trục tọa độ.

$\displaystyle \Rightarrow {{P}_{n}}=\sum_{s=1}^{n-1}{{{(n-s)}^{2}}}s=\frac{{{n}^{2}}({{n}^{2}}-1)}{12}=\frac{C_{{{n}^{2}}}^{2}}{6}$

Mỗi hình vuông có 6 đoạn nối các cặp đỉnh nên có $6{{P}_{n}}$ đoạn nối các cặp đỉnh.

Số cặp điểm là:${{S}_{0}}+{{S}_{1}}+{{S}_{2}}+{{S}_{3}}=C_{{{n}^{2}}}^{2}=6{{P}_{n}}$.

Số cạnh và số đường chéo của ${{P}_{n}}$ hình vuông là: ${{S}_{1}}+2{{S}_{2}}+3{{S}_{3}}=6{{P}_{n}}$.

Từ đó suy ra: ${{S}_{0}}={{S}_{2}}+2{{S}_{3}}$.

 

Bạn JUV đăng bài tiếp theo lên nhé!



#47
IMOer

IMOer

    Hạ sĩ

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

Bài 15: 

Một ảo thuật gia với $1$ bộ bài có $52$ quân bài, có $4$ loại bài là cơ, chuồn, rô, tép, mỗi loại bài có $13$ quân bài. Đầu tiên nhà ảo thuật sẽ đưa bộ bài cho khán giả xào bài, tất cả các quân bài sau khi được xào lại được đặt úp, chồng lên nhau. Trợ thủ của nhà ảo thuật được quyền xem thứ tự các quân bài và cũng có thể viết $1$ trong $2$ số $0$ hoặc $1$ vào mặt sau mỗi quân bài nhưng không được sắp xếp lại bộ bài và cũng không được nói cho nhà ảo thuật biết thứ tự của bộ bài. Mỗi lượt nhà ảo thuật sẽ đoán loại bài của lá bài trên cùng của xấp bài, sau đó loại nó ra khỏi bộ bài. Nhà ảo thuật cứ tiếp tục như thế trong $52$ lượt. Hỏi có chiến lược nào giúp anh ta đoán được đúng loại bài của ít nhất $30$ quân bài không?

Mình có một số thắc mắc sau:

- Trợ lý và nhà ảo thuật có được thống nhất chiến thuật từ trước khi xáo bài hay không?

- Có bắt buộc trợ lý phải viết số vào sau lá bài không?



#48
JUV

JUV

    Trung sĩ

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

Mình có một số thắc mắc sau:

- Trợ lý và nhà ảo thuật có được thống nhất chiến thuật từ trước khi xáo bài hay không?

- Có bắt buộc trợ lý phải viết số vào sau lá bài không?

- Điều hiển nhiên là trợ lí phải giúp nhà ảo thuật đạt được mục đích nên cũng phải thống nhất chiến thuật

- Trợ lí bắt buộc phải viết số sau lá bài



#49
Kvant

Kvant

    Lính mới

  • Thành viên mới
  • 1 Bài viết

- Điều hiển nhiên là trợ lí phải giúp nhà ảo thuật đạt được mục đích nên cũng phải thống nhất chiến thuật

- Trợ lí bắt buộc phải viết số sau lá bài

Cho mình hỏi liệu rằng cần tất cả các lá bài phải đánh dấu không hay lá có lá không?



#50
JUV

JUV

    Trung sĩ

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

Cho mình hỏi liệu rằng cần tất cả các lá bài phải đánh dấu không hay lá có lá không?

Tất cả lá bài phải đánh dấu


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


#51
halloffame

halloffame

    Thiếu úy

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

Dạo này topic hơi bị chìm, nếu không có ai đăng bài mới thì mình xin được góp vui một bài:

Bài 14: Có tất cả bao nhiêu hoán vị $(a_1,a_2,...,a_{2019})$ của $(1,2,..,2019)$ mà thỏa mãn tập $A=(a_k -k;1 \leq k \leq 2019)$ có đúng $2$ phần tử?


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 27-06-2016 - 21:19

Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.


#52
TanSan26

TanSan26

    Hạ sĩ

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

Bài 15: Trên mặt phẳng cho 2016 điểm, khoảng cách giữa các điểm này đôi một khác nhau. Nối mỗi điểm trong số 2016 điểm này với điểm gần nhất. Với cách nối đó có thể nhận được gấp khúc khép kín hay không


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 04-06-2017 - 22:40

                                                                                                                                                                                                                                                A vẩu


#53
halloffame

halloffame

    Thiếu úy

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

Lời giải bài 15: Giả sử dựng được đường gấp khúc thỏa đề. Do khoảng cách giữa các điểm đã cho là đôi một khác nhau nên theo nguyên lí cực hạn, trong các đoạn thẳng cấu thành đường gấp khúc ta luôn chọn được đoạn dài nhất, giả sử là đoạn $AB.$ Giả sử $A$ được nối với $C$ khác $B,$ còn $B$ được nối với $D$ khác $A.$

Do tính dài nhất của đoạn $AB,$ ta suy ra $AB>AC$ và $AB>BD.$ Như vậy $A$ không phải là điểm gần $B$ nhất và $B$ không phải là điểm gần $A$ nhất, suy ra $A$ và $B$ không được nối với nhau, mâu thuẫn. Vậy không nhận được gấp khúc khép kín với cách dựng thỏa đề.

Bạn TanSan26 lưu ý, trong nội quy của topic có ghi là chỉ được đề xuất bài mới nếu bài cũ đã 7 ngày chưa ai giải được. Bài 14 mình mới đăng có 2 ngày mà bạn đã đăng bài 15 mặc dù chưa ai giải được bài 14, như vậy bạn đã vi phạm quy định của topic. Lần sau mong bạn chú ý hơn.


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 03-07-2016 - 17:42

Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.


#54
halloffame

halloffame

    Thiếu úy

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

Bài 14 đã 7 ngày chưa có lời giải. Mình xin được đề xuất 1 bài dễ thở để tiếp tục topic:

Bài 16: Có n người ngồi quanh một bàn tròn. Họ cùng chơi một trò chơi như sau: tại mỗi lượt, hai người nào đó ngồi cạnh nhau trên bàn sẽ đổi chỗ cho nhau. Hỏi phải sau bao nhiêu bước thì ta đạt được trạng thái mà tại đó, 2 người bất kì ngồi cạnh nhau ban đầu vẫn ngồi cạnh nhau nhưng theo chiều ngược lại ?


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

Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.


#55
wanderboy

wanderboy

    Binh nhất

  • Thành viên mới
  • 34 Bài viết

Em làm thử bài 14: Gọi 2 phần tử của A là x và y(x>y),số các số có dạng $k=a_{i}+x\left ( \Leftrightarrow k \in x\right )$ là t(>0) theo đề bài ta có :

$tx+(2019-t)y=0\rightarrow t(x-y)=-2019y=s(1)$ Với mỗi cặp x,y mỗi số của dãy chỉ viết được bằng 2 cách $k=a_{i}+y,k=a_{i-s}+y+s$

Vì x>y nên $a_{i}=1\in y \rightarrow a_{j<i}\in x,a_{m(1< m\leq x)}\in y$ Vậy ta chỉ có duy nhất 1 cách viết dãy s số đầu tiên như sau :$x+1,x+2,...,s-1,s,1,2,...,x$

Tương tự như vậy với các nhóm s số tiếp theo cũng chỉ có 1 cách viết và nếu nhóm không được viết đủ sẽ không được một dãy các số liên tiếp như đề bài

(vì x ở đầu dãy và x+1 ở cuối dãy) nên x-y\left |2019\rightarrow x-y\in  \left \{ 1,673,3,2019 \right \}

TH1:x-y=1 không có No thỏa mãn

TH2:x-y=3 có 2 No y thỏa mãn ......$\rightarrow$ có 2692 giá trị của y $\Leftrightarrow$ 2692 cặp x,y

Vậy có 2692 hoán vị của dãy 

p/s: Em hỏi bài 16 nếu tất cả trả lời giống nhau thì sao ạ


Bài viết đã được chỉnh sửa nội dung bởi wanderboy: 15-08-2016 - 18:25


#56
wanderboy

wanderboy

    Binh nhất

  • Thành viên mới
  • 34 Bài viết

Bài 16:Đánh số n người đó theo các số từ 1 đến n theo 1 chiều xác định, khi đó chiều ngược lại: $\Rightarrow 2\rightarrow n,3\rightarrow n-1,...$

Chia n người đó làm 2 phần sao cho độ dài cung từ vị trí ban đầu đến vị trí cần tới(ngược lại) là nhỏ nhất thì ta cần sắp dãy $q,q+1,...,k-1,k\rightarrow k,k-1,...q+1,q$ Với k=2 thì hiển nhiên cần ít nhất 1 lần đổi chỗ

Giả sử với k=m ta cần ít nhất a lần đỗi chỗ thì với k=m+1 ta cần ít nhất a+m-1 lần vì khi đó $k \rightarrow q$ cần m-1 lượt và khi đó ta phải sắp dãy k-1 số còn lại giống với TH k=m và vì khi $k \rightarrow q$ vị trí tương đối của k-1 số còn lại không đổi nên dù thay đổi thứ tự di chuyển k thì ta vẫn cần ít nhất a lần để thực hiên sắp xếp dãy còn lại Vậy Với k=m thì ta cần ít nhất số lượt là : $\sum_{1}^{m-1}= \frac{m(m-1)}{2}$

Với n lẻ ta được 2 phần là $\frac{n+1}{2},\frac{n-1}{2}\rightarrow a= \frac{(n-1)^2}{4}$

Với n chẵn ta được 2 phần là $\frac{n-2}{2},\frac{n+2}{2}\rightarrow a= \frac{(n-1)^2+3}{4}$



#57
wanderboy

wanderboy

    Binh nhất

  • Thành viên mới
  • 34 Bài viết

Bài 17: 1 bảng n x n được đánh số từ 1 đến $n^{2}$.CMR có ít nhất 2 ô cạnh nhau khác nhau ít nhất n đơn vị.


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 04-06-2017 - 22:42


#58
songuku

songuku

    Binh nhì

  • Thành viên mới
  • 10 Bài viết

Đề xuất tạm 1 bài  : 1 bảng n x n được đánh số từ 1 đến $n^{2}$.CMR có ít nhất 2 ô cạnh nhau khác nhau ít nhất n đơn vị.

Từ ô chứa 1 đến ô chứa n^2 có nhiều nhất là 2n -1 ô. Mà hiệu của 1 và n^2 là n^2-1 theo Drichlet có 2 ô kề nhau có hiệu 2 lớn bằng n? 


Bài viết đã được chỉnh sửa nội dung bởi songuku: 26-09-2016 - 13:03


#59
songuku

songuku

    Binh nhì

  • Thành viên mới
  • 10 Bài viết

Bài 18: Cho tập A = {1,2,3...,2016}. Hỏi lấy ra nhiều nhất bao nhiêu phần tử từ tập A để trong những phần tử lấy ra không có phần tử nào bằng tích của hai phần tử còn lại


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 04-06-2017 - 22:42


#60
halloffame

halloffame

    Thiếu úy

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

Từ ô chứa 1 đến ô chứa n^2 có nhiều nhất là n -2 ô. Mà hiệu của 1 và n^2n^2-1 theo Drichlet có 2 ô kề nhau có hiệu 2 lớn bằng n

_Mình nghĩ từ ô chứa $1$ đến ô chứa $n^2$ không phải có nhiều nhất là $n-2$ ô đâu. Ví dụ như bạn điền vào bảng các số theo thứ tự sau:

  Hàng $1: 1,2,...,n.$

  Hàng $2: n+1,n+2,...,2n.$

  $...$

  Hàng $n: n^2-n+1,n^2-n+2,...,n^2.$

  Khi đó ô $1$ và ô $n^2$ sẽ cách nhau $2n-1$ ô bạn ạ.

_Những chỗ mình bôi màu đỏ bạn chịu khó sử dụng Latex để bài viết dễ nhìn hơn nhé.


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 25-09-2016 - 23:19

Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.






Đượ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

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

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