Bài toán:
Alex và Mary thay nhau viết các chữ số $0$ hay $1$ cho đến khi mỗi người viết được $2001$ chữ số. Mary sẽ là người thắng cuộc nếu cô ấy viết được một số trong biểu diễn nhị phân sao cho số đó không thể viết được dưới dạng tổng $2$ số chính phương. Chứng mình rằng Mary có chiến thuật để bảo đảm thắng cuộc chơi.
Chứng mình rằng Mary có chiến thuật để bảo đảm thắng cuộc chơi .
#1
Đã gửi 04-09-2011 - 10:04
- hxthanh, LNH, nghiemthanhbach và 6 người khác yêu thích
#2
Đã gửi 03-09-2014 - 13:59
Cho em hỏi là Alex với Mary ai viết trước và chữ số đầu tiên có bắt buộc là chữ số 1 không?
Ngoài ngoại hình ra thì ta chả có cái gì cả =))
#3
Đã gửi 05-09-2014 - 15:56
Bài toán này thuộc Gameshow NHỮNG BÀI TOÁN TRONG TUẦN. Bài toán đã được công bố lại nhiều ngày nhưng chưa ai giải được. BTC đã đặt hoa hồng hi vọng cho bài toán này.
Nếu hết ngày 07/09 mà vẫn không có ai giải được, BTC sẽ công bố bài toán khác, tuy nhiên hoa hồng hi vọng sẽ vẫn tồn tại cho đến khi có người giải được bài toán này.
- E. Galois và hoctrocuaZel thích
2) Danh sách các bài toán đã qua: 1-100, 101-200, 201-300, 301-400
Còn chờ gì nữa mà không tham gia!
#4
Đã gửi 06-09-2014 - 12:32
Tất cả những số xét tới đây đều là số nguyên dương cả nhé
Ta có: do $a^2+b^2 \not \equiv 3 \ (mod \ 4)$
$\Rightarrow a^2+b^2 \not \equiv 3.4^k \ (mod \ 4.4^k)$ (đồng dư)
Cho Alex viết trước và viết chữ số 1 đầu tiên
Khi viết thêm chữ số 0 vào sau 1 số, số đó tăng 2 lần
Khi viết thêm chữ số 1 vào sau 1 số, số đó tăng 2 lần cộng thêm 1 đơn vị
Chiến thuật để Mary thắng đó là khi Alex viết chữ số nào thì Mary cũng viết chữ số đó
Đâu tiên ta có số 11 ở lượt đầu tiên
Tổng của 2 số chính phương thì chia 4 dư 0 hoặc 1 hoặc 3 (Fermat)
Cho số x
Viết thêm 2 chữ số 11:
$(x.2+1).2+1=4x+3 \equiv 3 \ (mod \ 4)$ không phải tổng của 2 số chính phương
Nếu như Alex và Mary viết tiếp sao cho 2 chữ số cuối cùng là 11 thì Mary sẽ thắng cuộc
Nên Alex chỉ có lựa chọn là kết thức 2 bằng 2 chữ số 0
Cho số $4x+3$
Viết 2 lần số 0 thì giá trị tăng lên $4$ lần
$4(4x+3)=16x+12=16x+3.4^1$
Giả sử tồn tại $a ,b<16$ sao cho $(16t+a)^2+(16t+b)^2=16x+3.4^1 $
$\Leftrightarrow 16^2t^2+2.16t(a+b)+a^2+b^2=16x+3.4^1$ (1)
Mà $16^2t^2+2.16t(a+b) \equiv 16x \ (mod \ 16)$ và $a^2+b^2 \not \equiv 3.4^1 \ (mod \ 4.4^1)$ nên (1) không thỏa mãn
Chứng minh tương tự, ta sẽ được: $4^kx+3.4^{k-1}$ không thể biểu diễn dưới dạng $a^2+b^2 \forall x,k$
Do đó, với chiến thuật là Alex viết số nào mình viết số đó, Mary sẽ thằng cuộc chơi
- nghiemthanhbach và tohoproirac thích
Ngoài ngoại hình ra thì ta chả có cái gì cả =))
#5
Đã gửi 28-10-2015 - 09:45
Bài toán:
Alex và Mary thay nhau viết các chữ số $0$ hay $1$ cho đến khi mỗi người viết được $2001$ chữ số. Mary sẽ là người thắng cuộc nếu cô ấy viết được một số trong biểu diễn nhị phân sao cho số đó không thể viết được dưới dạng tổng $2$ số chính phương. Chứng mình rằng Mary có chiến thuật để bảo đảm thắng cuộc chơi.
Ta CM bổ đề $A^{2}+B^{2}\vdots 2^{2n}\Leftrightarrow A\vdots 2^{n}\cap B\vdots 2^{n}$
VP-->VT hiển nhiên. Bây giờ ta CM VT-->VP bằng phản chứng
Lưu ý do tính chất chia hết nếu $A\vdots 2^{n}\Rightarrow B\vdots 2^{n}$
Giả sử $A=2^{k_{1}}q_{1},B=2^{k_{2}}q_{2}(k_{1}\leq k_{2}< n,q_{i} là số lẻ)$.Từ
$A^{2}+B^{2}=2^{2n}q\Rightarrow q_{1}^{2}+2^{2(k_{2}-k_{1})}q_{2}^{2}=2^{2(n-k_{1})}q$
Lúc đó VT không chia hết cho 4,VP chia hết cho 4 vô lý .Suy ra điều phải CM
Bây giờ trở lại bài toán.Dễ thấy Alex luôn đánh số có giá trị 0 hoặc $2^{2k}(k\in N)$
Bằng cách đánh giống như Alex. Gọi i là lần viết số thứ i của Alex đống thời số được viết là 1.Giá trị của số được đánh theo hệ thập phân là (Gọi j là lần đầu tiên Alex viết số 1)
$\sum_{1\leq j=i\leq 2001}(2^{2(i-1)}+2^{2(i-1)+1})=3*2^{2(j-1)}\sum_{1\leq j=i\leq 2001}2^{2(i-j)}$
Gỉa sử $A^{2}+B^{2}= 3*2^{2(j-1)}\sum_{1\leq j=i\leq 2001}2^{2(i-j)}\Rightarrow A_{1}^{2}+B_{1}^{2}=3\sum_{1\leq j=i\leq 2001}2^{2(i-j)}$ (Theo bổ đề đã CM )
Mà $\sum_{1\leq j=i\leq 2001}2^{2(i-j)}\equiv 1(mod4)\Rightarrow 3*\sum_{1\leq j=i\leq 2001}2^{2(i-j)}\equiv 3(mod4)$
Trong khi $A_{1}^{2}+B_{1}^{2}\not\equiv 3(mod4)$.Vô lý
Vậy với việt số giống như Alex, Mary luôn thắng cuộc chơi như yêu cầu bài toán
Bài viết đã được chỉnh sửa nội dung bởi QDV: 28-10-2015 - 10:21
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh