Đến nội dung

Hình ảnh

Marathon tổ hợp rời rạc VMF 2018

- - - - -

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

#1
Minhnksc

Minhnksc

    Sĩ quan

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

Sau khi đã bàn bạc với NHoang1608 một số mem khác của diễn đàn; mình quyết định mở lại topic này để khuấy động bầu không khí hè của diễn đàn cũng như tạo nơi để giao lưu; trao đổi về các bài toán nói chung và tổ hợp rời rạc nói riêng. 

Thôi; không dài dòng nữa; mình xin được trích các quy định trong topic trước của anh bangbang1412

Các quy định phải tuân thủ : 

 1. Chỉ đăng các bài toán về tổ hợp rời rạc

 2. Không được giải bài toán do chính mình đề xuất , không được đăng bài toán của các cuộc thi vẫn chưa kết thúc ở các tạp chí , diễn đàn , ....

 3. Ghi rõ nguồn bài toán nếu có . ( nếu tự nghĩ bạn có thể ghi tên mình ) 

 4. Không spam , lời giải rõ ràng , không vắn tắt làm khó hiểu người đọc . 

 5. Mỗi bài đăng của bạn sẽ theo form sau mỗi khi bạn giải xong bài toán thứ n

    Lời giải bài toán n : 

   Bài toán n+1 ( nguồn ) : Tiếp đó là bài mà bạn đề xuất

6. Không đăng các bài toán mở , các giả thuyết , ...

7. Nếu một bài toán trong 4 ngày không được giải chúng ta sẽ đăng bài toán khác và đánh dấu lại bài toán đó . 

8. Các bài toán đăng lên độ khó nhất định , có thể không quá khó nhưng yêu cầu tư duy và suy nghĩ .

 

9. Lưu ý nếu một bài toán khó các bạn có ý tưởng cũng có thể chia sẻ để mọi người cùng nhau giải .

Topic này không giới hạn độ tuổi và kiến thức [chỉ có giới hạn là toán rời rạc sơ cấp thôi :D]


Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 31-05-2018 - 14:58

Sống khỏe và sống tốt :D


#2
Minhnksc

Minhnksc

    Sĩ quan

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

Bài toán 1: Cho $2017$ số thực là $a_{1};a_{2};...;a_{2017}$ trong đó $a_{i} \in \left\{1;-1\right\}$ . Giả sử tồn tại một số $a_{i}$ thỏa mãn

$a_{i}+a_{i+1}+...+a_{i+k}>0$ và $a_{i}+a_{i-1}+...+a_{i-k}>0$ trong đó $a_{2017+l}=a_{l}$ với mọi $l$ nguyên và $k$ nguyên thỏa mãn $1\le k < 2017 $

Tìm số lớn nhất các số là $-1$ trong các số thực đã cho.


Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 31-05-2018 - 16:20

Sống khỏe và sống tốt :D


#3
YoLo

YoLo

    Thượng sĩ

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

Bài 1: Ta xếp 2017 số$a_{1};a_{2};a_{3};...;a_{2017}$ lên vòng tròn theo chiều kim đồng hồ ( cho dễ nhìn)

Như vậy theo đề bài thì $\exists 1$ số trên đường tròn sao tổng k số về 2 phía của số đó >0

Vì giả thiết đúng với mọi k nên cho $k=2$

=> $\exists a_{i}$ mà $a_{i}+a_{i-1}>0;a_{i}+a_{i+1}>0$

=>$a_{i}=a_{i-1}=a_{i+1}=1$

Tức là nếu với 1 số lượng số bằng $-1$ mà $\exists$ 1 dãy không có 3 số 1 đứng liền nhau sẽ vô lý

Dễ thấy nếu có $673$ số bằng $-1$

Có dãy $-1;1;1;-1;1;1;...;-1;1;1;-1$ không thỏa mãn bài

 

Nếu có $672$ số $-1$ khi đó tồn tại $3$ số $1$ đứng cạnh nhau

chọn $a_{i}=1$ khi đó $\exists a_{i}$ thỏa mãn bài

P/s: Theo mk hiểu đề bài  thì là dãy số trên đúng với mọi cách chọn với số lượng các số -1 hay tìm sao cho $\exists$ 1 dãy với số lượng các số  -1 tm bài ???


Bài viết đã được chỉnh sửa nội dung bởi YoLo: 31-05-2018 - 17:33

Người ta không mắc sai lầm vì dốt mà là vì tưởng là mình giỏi :closedeyes:


#4
NHoang1608

NHoang1608

    Sĩ quan

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

Vẫn chưa hiểu lời giải bài 1 cho lắm  :D

Bài toán 2: (VMO 2002 ?) Tìm hiểu kết quả ở 1 lớp học, người ta nhận thấy rằng hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn toán cũng đồng thời đạt điểm giỏi hơn môn vật lí, hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn vật lí cũng đồng thời đạt điểm giỏi ở môn văn, hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn văn cũng đồng thời đạt điểm giỏi ở môn lịch sử, và hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn lịch sử cũng đạt điểm giỏi ở môn toán.

 

a) Chứng minh rằng trong lớp học nói trên , có ít nhất $1$ học sinh đạt điểm giỏi ở cả $4$ môn toán, vật lí, văn, lịch sử.

b) Hỏi có thể thay thế số $\frac{2}{3}$ ở trên bởi 1 thực $k$ thuộc $(0,1)$ nào hay không để bài toán vẫn đúng ?


Bài viết đã được chỉnh sửa nội dung bởi NHoang1608: 31-05-2018 - 22:01

The greatest danger for most of us is not that our aim is too high and we miss it, but that it is too low and we reach it.

----- Michelangelo----


#5
nghiemkythu

nghiemkythu

    Binh nhất

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

VMO

 

Vẫn chưa hiểu lời giải bài 1 cho lắm  :D

Bài toán 2: (VMO 2002 ?) Tìm hiểu kết quả ở 1 lớp học, người ta nhận thấy rằng hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn toán cũng đồng thời đạt điểm giỏi hơn môn vật lí, hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn vật lí cũng đồng thời đạt điểm giỏi ở môn văn, hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn văn cũng đồng thời đạt điểm giỏi ở môn lịch sử, và hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn lịch sử cũng đạt điểm giỏi ở môn toán.

 

a) Chứng minh rằng trong lớp học nói trên , có ít nhất $1$ học sinh đạt điểm giỏi ở cả $4$ môn toán, vật lí, văn, lịch sử.

b) Hỏi có thể thay thế số $\frac{2}{3}$ ở trên bởi 1 thực $k$ thuộc $(0,1)$ nào hay không để bài toán vẫn đúng ?

VMO bảng B - 2005 nha bạn :)



#6
YoLo

YoLo

    Thượng sĩ

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

Bài 3:(ITOT 2016???)

Có $N$ bạn học sinh đứng xếp thành $1$ hàng thẳng. Chiều cao của các bạn ấy đôi một phân biệt. Thầy giáo muốn thực hiện việc chuyển chỗ theo quy tắc sau. Mỗi lần chuyển chỗ , trước hết các bạn học sinh được chia thành các nhóm với chiều cao tăng dần từ trái qua phải (mỗi nhóm có thể gồm $1$ bạn) sao cho số các nhóm là ít nhất. Sạu đó thầy giáo xếp lại sao cho thứ tự các bạn trong nhóm bị đảo ngược nghĩa là trong mỗi nhóm các học sinh sẽ đứng theo chiều cao giảm dần từ trái qua phải.(Sau mỗi bước chuyển chỗ thì việc chia nhóm được lặp lại theo quy tắc trên) Chứng minh thầy giáo sau $N-1$  bước đổi chỗ như vậy, các bạn học sinh sẽ đứng theo chiều cao giảm dần từ trái qua phải.


Bài viết đã được chỉnh sửa nội dung bởi YoLo: 07-06-2018 - 23:20

Người ta không mắc sai lầm vì dốt mà là vì tưởng là mình giỏi :closedeyes:


#7
ThuanTri

ThuanTri

    Hạ sĩ

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

Vẫn chưa hiểu lời giải bài 1 cho lắm  :D

Bài toán 2: (VMO 2002 ?) Tìm hiểu kết quả ở 1 lớp học, người ta nhận thấy rằng hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn toán cũng đồng thời đạt điểm giỏi hơn môn vật lí, hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn vật lí cũng đồng thời đạt điểm giỏi ở môn văn, hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn văn cũng đồng thời đạt điểm giỏi ở môn lịch sử, và hơn $\frac{2}{3}$ số học sinh đạt điểm giỏi ở môn lịch sử cũng đạt điểm giỏi ở môn toán.

 

a) Chứng minh rằng trong lớp học nói trên , có ít nhất $1$ học sinh đạt điểm giỏi ở cả $4$ môn toán, vật lí, văn, lịch sử.

b) Hỏi có thể thay thế số $\frac{2}{3}$ ở trên bởi 1 thực $k$ thuộc $(0,1)$ nào hay không để bài toán vẫn đúng?

a) Gọi a là số học sinh đạt điểm giỏi Toán và VL không giỏi các môn còn lại 

           b là số học sinh đạt điểm giỏi  Văn và VL không giỏi các môn còn lại

           c là số học sinh đạt điểm giỏi  Văn và LS không giỏi các môn còn lại

           d là số học sinh đạt điểm giỏi Toán và LS không giỏi các môn còn lại 

           e là số học sinh đạt điểm giỏi Toán, VL, LS không giỏi Văn 

           f  là số học sinh đạt điểm giỏi  VL, LS, Văn không giỏi Toán 

           g là số học sinh đạt điểm giỏi  Toán, VL, Văn không giỏi LS  

           h là số học sinh đạt điểm giỏi  Toán, LS, Văn không giỏi VL 

           m là số học sinh đạt điểm giỏi Toán không giỏi các môn còn lại 

           n là số học sinh đạt điểm giỏi  Văn  không giỏi các môn còn lại

           p là số học sinh đạt điểm giỏi  LS không giỏi các môn còn lại

           q là số học sinh đạt điểm giỏi  VL không giỏi các môn còn lại 

           i là số học sinh đạt điểm giỏi cả 4 môn

           x là số HS của lớp $\rightarrow$ a+b+c+d+e+f+g+h+i =x-m-n-p-q (x là số nguyên dương, x$\geq$3)

Theo đề cho ta có a+e+g+i $\geq$ 2/3 x  

                              g+b+f +i $\geq$ 2/3 x   

                              i+h+c+f  $\geq$ 2/3 x 

                              i+h+d+e $\geq$ 2/3 x 

Suy ra     x-m-n-p-q+3i $\geq$ 8/3 x  $\leftrightarrow$ 3i-m-n-p-q $\geq$ 5/3 x

                                                           $\leftrightarrow$ 3i              $\geq$ 5/3 x +m+n+p+q

                                                           $\leftrightarrow$ i                $\geq$ 5/9 x +m+n+p+q

Mà m,n,p,q $\geq$ 0, x $\geq$ 3  nên ta có i $\geq$ 1

b) giải tương tự như trên, đặt tỉ lệ = a/b rồi giải ra


   Trăm năm Kiều vẫn là Kiều

Sinh viên thi lại là điều tất nhiên.


#8
Minhnksc

Minhnksc

    Sĩ quan

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

Bài 1: Ta xếp 2017 số$a_{1};a_{2};a_{3};...;a_{2017}$ lên vòng tròn theo chiều kim đồng hồ ( cho dễ nhìn)

Như vậy theo đề bài thì $\exists 1$ số trên đường tròn sao tổng k số về 2 phía của số đó >0

Vì giả thiết đúng với mọi k nên cho $k=2$

=> $\exists a_{i}$ mà $a_{i}+a_{i-1}>0;a_{i}+a_{i+1}>0$

=>$a_{i}=a_{i-1}=a_{i+1}=1$

Tức là nếu với 1 số lượng số bằng $-1$ mà $\exists$ 1 dãy không có 3 số 1 đứng liền nhau sẽ vô lý

Dễ thấy nếu có $673$ số bằng $-1$

Có dãy $-1;1;1;-1;1;1;...;-1;1;1;-1$ không thỏa mãn bài

 

Nếu có $672$ số $-1$ khi đó tồn tại $3$ số $1$ đứng cạnh nhau

chọn $a_{i}=1$ khi đó $\exists a_{i}$ thỏa mãn bài

P/s: Theo mk hiểu đề bài  thì là dãy số trên đúng với mọi cách chọn với số lượng các số -1 hay tìm sao cho $\exists$ 1 dãy với số lượng các số  -1 tm bài ???

Chỉ cần tồn tại chứ không cần đúng với mọi cách chọn các số 1 và -1. Tức là nói theo cách khác; khi xếp trên đường tròn; nếu có một điểm mà tổng thành phần gồm các số liên tiếp nhau bắt đầu từ điểm đó theo mọi phía là một số dương thì số lớn nhất các số -1 là bao nhiêu. Mình nghĩ bạn hiểu sai đề ở chỗ nào đó; hoặc là mình không hiểu lời giải của bạn


Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 02-07-2018 - 19:57

Sống khỏe và sống tốt :D


#9
Minhnksc

Minhnksc

    Sĩ quan

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

Như đã hẹn; bài toán số 3 vẫn chưa có người giải nên mình post bài mới:

Bài toán 4:

Gần đây; cảnh sát đang điều tra một vụ đánh cắp tài khoản ngân hàng. Để tìm ra tài khoản của hung thủ; ta cần biết một số thông tin: tài khoản ngân hàng gồm 14 chữ số từ 0 tới chín. Mỗi tài khoản được đánh dấu là đáng nghi nếu bị nghi ngờ là tài khoản của hung thủ; còn không đáng nghi trong trường hợp ngược lại. Sau khi điều tra; người ta thấy rằng nếu tài khoản $x_1x_2x_3...x_{14}$  đáng nghi thì trong các tài khoản $y_1y_2y_3...y_{14}$ thỏa mãn tồn tại tập $S$ sao cho $S\subset \left\{1;2;...;14\right\}$ và $|S|=13$ sao cho $x_i=y_i \forall i\in S$; có ít nhất chín tài khoản đáng nghi. Tìm số nhỏ nhất các tài khoản đáng nghi


Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 02-07-2018 - 20:11

Sống khỏe và sống tốt :D


#10
YoLo

YoLo

    Thượng sĩ

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

Chỉ cần tồn tại chứ không cần đúng với mọi cách chọn các số 1 và -1. Tức là nói theo cách khác; khi xếp trên đường tròn; nếu có một điểm mà tổng thành phần gồm các số liên tiếp nhau bắt đầu từ điểm đó theo mọi phía là một số dương thì số lớn nhất các số -1 là bao nhiêu. Mình nghĩ bạn hiểu sai đề ở chỗ nào đó; hoặc là mình không hiểu lời giải của bạn

Mình lại hiểu đề bài là với max số lượng các số  $-1$ đó thì với mọi cách sắp xếp phải thỏa mãn bài

Mình xin giải lại như sau

cho xếp $2017$ số trên vòng tròn theo chiều kim đồng hồ

theo giả thiết thì $\exists 1$ số trên đường tròn mà tổng $k$ số về 2 phía của số đó lớn hơn $0$

Giả thiết cho đúng với mọi $k$ nên với $k=1008$ thì tổng $1009$ số về $2$ phía của số $a_{i}>0$

với $k=1$ => $a_{i}+a_{i-1}>0;a_{i}+a_{i+1}>0$

=> $a_{i}=a_{i-1}=a_{i+1}=1$

Xét $k=1008$ => $1009$ số theo chiều kim đồng hồ có tổng $>0$=> phải có tối thiểu $505$ số $1$

                             $1009$ số theo ngược kim đồng hồ có tổng $>0$=> phải có tối thiểu $505$ số $1$

=> có tối thiểu là $1010$ số $1$

=> có tối đa $1007$ số $-1$

nếu số lượng $-1$ là $1007$ ta có $1;1;-1;1;-1;1;...;-1;1$ xếp theo chiều kim đồng hồ khi đó số $a_{1}$ là số mà tổng $k$ số bất kì về 2 phía nó  $>0$

=> số lượng lớn nhất các số $-1$ là $1007$


Bài viết đã được chỉnh sửa nội dung bởi YoLo: 06-07-2018 - 23:13

Người ta không mắc sai lầm vì dốt mà là vì tưởng là mình giỏi :closedeyes:


#11
Hr MiSu

Hr MiSu

    Thượng sĩ

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

Như đã hẹn; bài toán số 3 vẫn chưa có người giải nên mình post bài mới:

Bài toán 4:

Gần đây; cảnh sát đang điều tra một vụ đánh cắp tài khoản ngân hàng. Để tìm ra tài khoản của hung thủ; ta cần biết một số thông tin: tài khoản ngân hàng gồm 14 chữ số từ 0 tới chín. Mỗi tài khoản được đánh dấu là đáng nghi nếu bị nghi ngờ là tài khoản của hung thủ; còn không đáng nghi trong trường hợp ngược lại. Sau khi điều tra; người ta thấy rằng nếu tài khoản $x_1x_2x_3...x_{14}$  đáng nghi thì trong các tài khoản $y_1y_2y_3...y_{14}$ thỏa mãn tồn tại tập $S$ sao cho $S\subset \left\{1;2;...;14\right\}$ và $|S|=13$ sao cho $x_i=y_i \forall i\in S$; có ít nhất chín tài khoản đáng nghi. Tìm số nhỏ nhất các tài khoản đáng nghi

Thực ra bài toán hơi đáng ngờ, vì có $10$ chữ số từ $0$ tới $9$ lận

Theo đề thì có ít nhất $1$ tài khoản đáng nghi,

do đó có thêm ít nhât $9$ tài khoản đáng nghi nữa, vậy có ít nhất 10 tài khoản đáng nghi

đây là số nhỏ nhất bởi: chỉ cần giữ nguyên $13$ chữ số, chữ số còn lại thay bởi các chữ số khác chữ số đó trong tập {$0,1,...,9$} ;)

Đề xuất Bài toán 5:

Cho tập hợp $A=\begin{Bmatrix} 1,2,3,4,5,6,7,8,9,10 \end{Bmatrix}$. Tìm số $k$ lớn nhất có thể chọn được $k$ tập con thỏa mãn hợp của $4$ tập con bất kì không vượt quá $8$ phần tử.

< Đề chọn đội tuyển KHTN 2014-2015 vòng 2 ngày 2>


Bài viết đã được chỉnh sửa nội dung bởi Hr MiSu: 22-08-2018 - 20:14

s2_PADY_s2

Hope is a good thing, maybe the best thing, and no good thing ever dies





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

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