Đến nội dung

Hình ảnh

Chứng mình rằng Mary có chiến thuật để bảo đảm thắng cuộc chơi .


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

#1
caubeyeutoan2302

caubeyeutoan2302

    Nhà dược sĩ mê toán

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

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.


CỐ GẮNG THÀNH SINH VIÊN ĐẠI HỌC Y DƯỢC THÀNH PHỐ HỒ CHÍ MINH

#2
demon311

demon311

    Thượng sĩ

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

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
PSW

PSW

    Những bài toán trong tuần

  • Quản trị
  • 493 Bài viết

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.


1) Thể lệ
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! :luoi:

#4
demon311

demon311

    Thượng sĩ

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

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


Ngoài ngoại hình ra thì ta chả có cái gì cả =))


#5
QDV

QDV

    Trung sĩ

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

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





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

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