Đến nội dung

The Gunner

The Gunner

Đăng ký: 11-04-2012
Offline Đăng nhập: 14-05-2017 - 03:42
****-

#640983 Dạng toán: tìm quy luật dãy số

Gửi bởi The Gunner trong 18-06-2016 - 07:03

tìm quy luật dãy số {1, 2, 3, 5, 8, 10, 13, 16, 23, 32, 44, 56, 76, 102, 132, 174, 227}

dãy Conway 1,11,21,1211,111221, 312211,....

ví dụ 11 là do số trước nó có 1 số 1

21 là do số trước nó 11 có 2 số 1

1211 là do số trước nó có 1 số 2 và 1 số 1 nên viết thành 1211

tiếp tục 1211 có 1 số 1, 1 số 2, 2 số 1 => 111221

các số của dãy  {1, 2, 3, 5, 8, 10, 13, 16, 23, 32, 44, 56, 76, 102, 132, 174, 227} là tương ứng là tổng các chữ số của từng số hạng trong dãy Conway




#611069 Cmr: $m\geq n^2-n+1$

Gửi bởi The Gunner trong 26-01-2016 - 09:01

Gọi $S_n$ là số cạnh đơn vị không thuộc cạnh lớn của tam giác được chia thành $n^2$ tam giác đều. ta có $S_1=0, S_2=3, S_n=S_{n-1}+3(n-1)$ suy ra được $S_n=\frac{3n(n-1)}{2}$

Ta có nhận xét rằng để đánh dấu được một độ dài $m$ thì ta phải dùng $m-1$ cạnh đơn vị nối giữa những tam giác đó, ta tô màu đỏ những cạnh đó. Hơn nữa một tam giác con không có cạnh nằm trên cạnh của tam giác lớn thì sau khi đã được đánh dấu, cạnh còn lại không được chọn để nối với tam giác khác cũng không còn giá trị, ta tô màu xanh cho những cạnh này . Vì vậy để đánh dấu được $m$ tam giác ta đã phải tô màu ít nhất $m-1 +[\frac{m}{2}]$ cạnh đơn vị ( tại nếu xét một đường đi dọc theo biên của tam giác lớn thì ta có xem kẽ những tam giác có cạnh nằm trên cạnh lớn sẽ không tính cạnh đó).

Ta có $m-1 +[\frac{m}{2}] \leq  S_n=\frac{3n(n-1)}{2} $ 

suy ra: $m-1+ \frac{m-1}{2} \leq \frac{3n(n-1)}{2}$

ta được $m \leq n^2-n+1$




#510259 1 bài tổ hợp trong gặp gỡ toán học lần IV

Gửi bởi The Gunner trong 02-07-2014 - 01:49

Không rõ là có chỗ nào nhầm lẫn không vì ở điều kiện 4,suy ra có nhiều nhất 2 bạn mua 3 tựa sách giống nhau, nếu số học sinh là nhiều nhất thì với mỗi cách mua 3 tựa sách thỏa mãn thì sẽ có 2 học sinh mua giống nhau nên số học sinh nhiều nhất phải là số chẵn.

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

Xét 673 tựa sách tương ứng với 673 điểm không thẳng hàng trong không gian, mỗi tam giác nối 3 điểm tương ứng với mỗi học sinh chọn 3 tựa sách. theo các điều kiện trên ta thấy, hai tam giác bất kì phải chung đỉnh hoặc chung cạnh và chỉ có nhiều nhất 2 tam giác có cùng chung 3 đỉnh. Trước tiên ta khoan xét điều kiện 4 tức là chỉ có nhiều nhất 2 tam giác giống nhau. Ta có nhận xét sau. nếu có 4 tam giác cùng chung 1 đỉnh thì tam giác thứ 5 cũng phải chung đỉnh đó vì nếu không thì nó thành tứ giác mất rồi. Nhưng do không có điểm nào là điểm chung của tất cả các tam giác theo điều kiện 3) do đó ta xét đến yếu tó chung cạnh để tạo nên hai điểm chung khi đó sẽ ko có điểm nào là điểm chung của tất cả các tam giác. xét 3 điểm làm tam giác trung tâm, ta có mỗi điểm trong không gian tạo với ta giác này một tứ diện và có thêm 3 mặt là 3 tam tam thỏa mãn dó đó ta có nhiều nhất là 670 tứ diện chung mặt là tam giác trung tâm, tức là có thêm 2010 tam giác mới cộng với tam giác trung tâm là 2011 tam giác tương ứng với 2011 học sinh nếu thêm điều kiên 4 vào thì có nhiều nhất là 4022 học sinh




#510245 Tìm $a$ thỏa tồn tại song ánh $f:\{1;2;...;n\...

Gửi bởi The Gunner trong 01-07-2014 - 23:44

Với $a=0$ thỏa mãn, khi đó ta có song ánh $f(i)=i$

ta xét các số nguyên $a >0$.

giả sử tồn tại song ánh, ta có $f(i)=i+a$ (ta gọi là hàm cộng) hoặc $f(i)=i-a$ (gọi là hàm trừ)

Nếu $n$ lẻ xét tổng $\sum f(i)=\sum i$ do đó số hàm cộng và hàm trừ phải bằng nhau nên số hàm phải chẵn, tức là $n$ phải là số chẵn, với $n$ lẻ ta chỉ có $a=0$

Đặt $n=2k$ nếu $a>k$ thì dó $f(i)>0$ nên $f(i)=i+a$ với $i=1,..,k+1$ lúc đó số hàm chẵn nhiều hơn số hàm trừ, vô lí. DO đó $a <= k$

Với $a=1$ ta có sóng ánh như sau : giá trị của $f(i)$ chính là hoán vị của từng cặp số trong dãy ví dụ như $f(1)=2;f(2)=1;f(3)=4;f(4)=3;f(5)=6;f(6)=5;...$ (*)

Với $a=k$ thì $f(i)=i+a$ với $i=1,..,k$ và $f(i+a)=i$ với $i=1,...,k$

Bây giờ ta xét các giá trị của $a$ với $1<a<k$

Ta phân hoạch dãy ${1,2,..,2k}$ thành dãy các cấp số cộng công sai là $a$

nếu $k$ không chia hết cho $a$ thì số trong các dãy đã phân hoạch phải tồn tại ít nhất một dãy có số phần tử là số lẻ, gọi tập đó là $S$

ta có nếu $f(i) \in S$ thì $i+a \in S$ hoặc $i-a \in S$. Do đó số hàm cộng và hàm lẻ trong $S$ cũng phải là số chẵn, vô lí, suy ra $k$ phải chia hết cho $a$

tức là $n=2aq$. khi đó ta có song ánh sau. Xét trong mỗi dãy đã phân hoạch ta làm tương tự như (*). ví dụ $f(1)=a+1;f(a+1)=1;f(2a+1)=3a+1;f(3a+1)=f(2a+1)...$

Tóm lại.
$n$ lẻ thì $a=0$

$n=2k$ thì $a=0$ và các ước dương của $k$

Ps: Nhờ mod sửa hộ em latex, lâu rồi không dùng nên cũng quên vài cái




#394130 [Giải trí]Cặp đôi hoàn hảo VMF 2013

Gửi bởi The Gunner trong 06-02-2013 - 22:58

ơ, cặp 5 có cô bạn xinh thế...chắc ko vote :))


#374668 Tìm số nguyên dương s

Gửi bởi The Gunner trong 02-12-2012 - 22:09

anh nghĩ bài này các nghiệm ko phân biệt mới khó nguyenta98 à.
Bài này nếu tìm $s$ thì thấy hình như hơi bị nhiều, ta xét cái bình phương là lũy thừa $m$ như sau
với phương trình mới là $\frac{1}{x_1^m}+\frac{1}{x_2^m}+...+\frac{1}{x_s^m}=1$
1) Ta nhận thấy rằng với $s=a^m$ thì ta có bộ nghiệm là $(a,a,...,a)$
2) Nếu mà $s$ thỏa mãn pt có nghiệm thì $s+a^m-1$ cũng thỏa mãn vì khi đó ta có bộ $(ax_1,ax_2,...,ax_s,a,a,....,a)$
Do đó pt có nghiệm khi $s$ có dạng $s=k(a^m-1)+l(b^m-1)+1$ (*)
Mà ta có bài toán sau với $(a,b)=1$ và $s \geq ab-a-b+1=(a-1)(b-1)$ thì với mọi $s \in \mathbb{N}$ thì luôn tồn tại $k,l$ sao cho $s=ka+lb$
Thật vậy giả sử $s \equiv m (\mod a)$ vì $s \geq (a-1)(b-1)$ nên các số $m,m+a,...,m+(b-1)a$ là một hệ thặng dư đầy đủ modulo b vì $(a,b)=1$
nên tồn tại $k$ để$m+ka \equiv 0 (\mod b)$
do đó tồn tại $k,l$ để $s=ka+lb$
khi $s$ đủ lớn thì nó luôn biểu diễn được dưới dạng (*), lúc đó pt luôn có nghiệm
Với bài toán này $m=2$ thì mình tính sơ ko bik đúng ko thì khi $s \geq 2.34+1=69$ thì pt luôn có nghiệm, còn nếu nhỏ hơn thì chắc xét mấy số có biểu diễn như (*) chẳng hạn (chỗ này mình vẫn chưa kiếm đc cách nào để tính cho dễ)


#374505 Tại 3 đỉnh của $\Delta ABC$ có ghi tương ứng 3 số

Gửi bởi The Gunner trong 02-12-2012 - 12:01

Bài này áp dụng bđt sau, với $a+b+c=0$ thì ta có $2(a^2+b^2+c^2) \leq (a+b-2c)^2+(b+c-2a)^2+(a+c-2b)^2$
Từ đó đặt $S_n=a_n^2+b_n^2+c_n^2$ với $a_n,b_n,c_n$ là số tại các đỉnh A,B,C sau n bước thực hiện suy ra $S_{n+1}\geq 2S_{n}$
suy ra $S_n \geq 2^{n-1}S_1$ ( vì $a,b,c$ đôi một khác nhau nên $S_1>0$)
Do đó ta luôn có S_n lớn tùy ý nên các trong các số $|a_i|,|b_i|,|c_i|$ sẽ có ít nhất một số lớn tùy ý mà vì $a+b+c=0$ nên nếu có số tiến đến âm vô cùng thì phải có một số tiếng đến dương vô cùng. Do đó tồn tại một đỉnh trong tam giác có số tại đó có thể lớn tùy ý, suy ra có ít nhất một số lớn hơn 2012


#372025 Bài toán xếp người

Gửi bởi The Gunner trong 24-11-2012 - 08:39

Ta đánh số các vị trí trên bàn tròn lần lượt là $1,2,...,2013$
người ở vị trí thứ $i$ sau giờ giải lao sẽ ngồi vào vị trí $f(i)$ với $f(1),f(2),...,f(2013)$ là một hoán vị của $1,2,...,2013$
ta chứng minh tồn tại hai số $a$ và $b$ thỏa mãn $f(a)-a \equiv f(b)-b (\mod 2013)$
Thật vậy, giả sử phản chứng ko tồn tai thì $f(i)-i$ lập thành một hệ thặng dư đầy đủ modulo 2013
lấy xích ma lại suy $0 \equiv 0+1+2+...+2012 \equiv 0 (\mod 2013)$
Thấy chả vô lí nhỉ, hình như bài này thì đk phải là số chẵn tức 2013 là ko tồn tại còn nếu thay 2013 là số chẵn thì ok :D
ví dụ với 5 thì ta xếp đc 1,2,3,4,5->1,4,2,5,3 thỏa mãn số đại biểu sau h giải lao giữa 2 người bất kì có thay đổi :D


#368642 Cách chia các đội bơi

Gửi bởi The Gunner trong 11-11-2012 - 10:08

Bài này nó khác bài trên ở chỗ cái giao 3 tập là rỗng nên sử dụng ý tưởng truy hồi như cách truy hồi trên cũng ko khác là mấy.
Đặt các dãy tương tự như trên với $P_n,Q_n,R_n,S_n$ là số bộ $ A,B,C$ thỏa mãn trong 3 số $|A \cap B|,|B \cap C|,|C \cap A|$ lần lượt có 0,1,2,3 số bằng 0. Thì theo cách lí luận như cách mình bài trên thì xây dựng đc hệ sau
$P_{n+1}=6P_n+Q_n$
$Q_{n+1}=5Q_n+2R_n$
$R_{n+1}=4R_n+3S_n$
tính đc $S_n=3^n$
suy ngược lại $P_n=3.4^n+6^n-3^n-3.5^n$
Nếu ko tính tứ tự thì là $\frac{P_n}{6}$


#368064 Cách chia các đội bơi

Gửi bởi The Gunner trong 09-11-2012 - 10:05

nice solution :)
Nhìn bài này mới nhớ có một bài khá đẹp và khá giống bài này:
Cho tập $M=(1,2,...,n)$ tính số các phân hoạch M thành 3 tập con $A,B,C$ thỏa mãn các đk
$|A \cap B|>0,|B \cap C|>0,|C \cap A|>0,|A \cup B \cup C|=M,|A \cap B \cap C|=0$
---------------------------------------------------------------------------------------------------
Giải bài này luôn anh!


#367157 Cách chia các đội bơi

Gửi bởi The Gunner trong 05-11-2012 - 00:26

Haiz mấy bài đếm này làm toát mồ hôi mà chả bik đúng ko nữa. Mình post sơ ý tưởng trước xem thử:
gọi $P_n,Q_n,R_n,S_n$ là số các bộ $F_1,F_3,F_3,F_4$ thỏa mãn trong $|F_1 \cap F_2|,|F_2 \cap F_3|,|F_3 \cap F_4|$ lần lượt có 0,1,2,3 số bằng 0.
Bài toán sẽ đưa về đếm $P_n$
mà ta nhận thấy
Xét $P_{n+1}$. nếu bỏ đi 1 phần tử thì nó có thể thuộc một trong 4 tập $|F_i|$ hoặc giao của 2 , của 3 hoặc của 4 tập đó nên ta có $\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}$ cách chèn vào trong $P_n$. Mà phần tử này có thể thuộc phần giao của của các tập $F_i$ nên ta có thể suy ra được $P_{n+1}=15P_n+Q_n+R_n+S_n $ (1)
bây giờ ta lại xây dựng cho $Q_n$. Tương tự như trên ta sẽ suy ra $Q_{n+1}=11Q_{n}+2R_{n}+3S_{n}$ (2)
ở đây $11=\binom{4}{1}+\binom{4}{2}-1+\binom{4}{3}-2 $
ở chỗ tô màu đỏ là do xét 1 số bằng 0 chẳng hạn $|F_1 \cap F_2|$ thì trường này ko đc tính vì ko có phần tử chung. tương tự như ở chỗ màu xanh
con với $2R_{n}$ là do xét trường hợp n phần tử mà trong 3 số đang xét có 2 số bằng 0 thì ta chỉ có 2 cách để bổ sung phần tử $n+1$ để 3 số đang xét còn 1 số bằng 0, tương tự với xét $3S_n$
Tiep tục như thế ta xây dựng được $R_{n+1}=8R_n+3S_n$(3)
Ta tinh $S_n$. vì trường hợp này 3 số đang xét ở trên đều bằng 0 tức là mỗi phần tử của tập n phần tử đều ko thuộc giao của 3 tập trên. tức là mỗi phần tử sẽ có $15-3=12$ cách chọn nên có $S_n=12^n$ (4)
Tư (1),(2),(3) và (4) ta có thể suy ngược lại công thức của $P_n$.

P/s:Trên đây chỉ là ý tưởng,mình chưa tính ra rõ ràng có thể có sai sót mình sẽ edit sau.
@ai có thể giúp mình tính nốt phần còn lại được ko :)


#366335 Hỏi quân xe có thể "đứng" qua tất cả các ô trên bảng hay không?

Gửi bởi The Gunner trong 01-11-2012 - 16:09

Ta đánh số bảng như sau:
0 1 2 3 0...
1 2 3 0 1...
2 3 0 1 2...
3 0 1 2 3...
0 1 2 3 0...
ta cứ đánh số như vậy cho đến hết bảng thì ta thấy ở ô đánh số $i$ thì nó sẽ có đường đi đến các ô có giá trị như sau ( tính theo mod 4
$i \to i+1 \to i+3 \to i \to i+2 \to i+3 \to i+1 \to i+2 \to i$ (*)
Đk cần để tồn tại một chu trình là bắt đầu từ ô $i$ cũng phải kết thúc tại ô $i$
Nếu $n$ lẻ thì có $n^2$ bước đi , mà khi đó bước đi cuối cùng là cạnh 1 nên theo (*) thì số bước đi có dạng $4k+3$ vô lí
Nếu $n$ chẵn thì bước đi cuối cùng có cạnh 2 nên theo (*) số bước đi phải chia hết cho 8 nên suy ra $ n^2$ chia hết cho 8. do đó $n$ phải chia hết cho 4
Vói $n=4k$ thì em chưa tìm được thuật toán tổng quát hi vọng thầy hxthanh có thể tìm đc thuật toán tổng quát cho TH này. còn với bài toán trên $n=10$ là ko thể :)


#366027 Tập hợp hữu hạn

Gửi bởi The Gunner trong 30-10-2012 - 21:08

Vì mỗi tập đều chứa quá nửa phần tử của X nên ta có $|A_1|+|A_2|+...+|A_{50}|>\frac{50|X|}{2}=25|X|$ do đó theo Dirichlet phải có một phần tử thuộc ít nhất 26 tập. ta chọn phần tử đó thuộc tập A là $x_1$
Bỏ phần 26 tập trên xét 24 tập còn lại tương tự như trên phải tồn taị một phần tử thuộc ít nhất 13 tập, chọn phần tử này thuộc A là $x_2$
tương tự xét 11 tập còn lại thì phải có một phần tử $x_3$ thuộc ít nhất 6 tập.Lại xét 5 tập còn lại thì phải có $x_4$ thuộc ít nhất 3 tập. Xét 2 tập còn lại chọn phần tử $x_5$ chung của 2 tập này vì hai tập bất kì giao nhau . Do đó tồn tại tập A có $|A|\leq 5$ và $|A \cap A_i | \geq 1$. đpcm


#363882 Hoán vị giống ban đầu?

Gửi bởi The Gunner trong 22-10-2012 - 19:13

ta nhận thấy là với mỗi số để đưa nó về lại vị trí ban đầu thì phải cần một số chẵn lần hoán vị, vì mỗi hoán vị ta chỉ đổi chỗ hai số liên tiếp nên suy ra để trở về một hoán vị ban đầu sẽ phải có một số chẵn lần biến đổi


#363866 Chiến lược thắng cuộc

Gửi bởi The Gunner trong 22-10-2012 - 18:21

Viết các số trên bảng $1,2,3,...,2004$. Có hai người chơi theo quy tắc, đến lược mỗi người được quyền xoá $2$ số tuỳ ý $a,b$ trên bảng và thay đổi vào đó số $a^b$. Trò chơi kết thúc khi trên bảng còn lại $1$ số nếu số đó tận cùng là $2,3,7,8$ thì người đi trước được xem là thắng cuộc, ngược lại thì người đi sau thắng. Hỏi ai là người có chiến lược thắng?

theo mình nghĩ người thứ 2 có thể thắng. Đặt X là tập các số tận cùng bởi 0,1,4,5,6,9. Y là tập các số tận cùng bởi 2,3,6,8 ta thấy nếu chọc hai số trong X thì khi thay vào số mới thì số đó cũng thuộc X. Tập X nhiều hơn Y nên người thứ 2 mỗi lần chơi cứ chọn a thuộc X, b thuộc Y thì sau mỗi lần chơi thì tập Y giảm, tập X ko đổi. Còn người thứ nhất sau mỗi lược chơi chỉ làm giảm đc tối đa 1 số thuộc X do |X|>|Y| nên suy ra số còn lại cuối cùng phải thuộc X. Suy ra người thứ 2 thắng.


-------------------------------------------
Lời giải rất hay, mang tính công phá cao!