Đến nội dung


Hình ảnh

Mọt toán làm đẹp


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

#1 WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản trị
  • 1322 Bài viết
  • Giới tính:Nam

Đã gửi 20-02-2014 - 01:14

Bài toán .

Ở 1 xứ sở nọ nơi cách rất xa nơi chúng ta đang ở, nơi Mọt Toán sinh sống, các Mọt Toán có hình dạng là 1 dãy các khoang trắng và đen. 1 Mọt Toán được gọi là "đẹp" nếu chỉ gồm toàn các khoang trắng. Việc làm đẹp (tẩy trắng) 1 Mọt Toán được tiến hành như sau :

Nếu khoang cuối của Mọt có màu đen, bác sĩ có thể cắt bỏ và ghép 1 khoang màu trắng hoặc đen tùy ý lên đầu con Mọt.

Nếu khoang cuối của nó màu trắng, thì khoang cuối này sẽ tự biến mất và Mọt Toán tự mọc thêm vào trên đầu 1 khoang (nhưng bác sĩ không biết đc là trắng hay đen).

Mặc dù quá trình tẩy trắng phức tạp như vậy nhưng Bác Sĩ Cuội vẫn khắng định có thể làm đẹp 1 mọt toán bất kì. Hỏi bác sĩ nói có đúng không ?


Bài viết đã được chỉnh sửa nội dung bởi E. Galois: 04-07-2014 - 23:03

$$n! \sim \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$$

 

“We can only see a short distance ahead, but we can see plenty there that needs to be done.” - Alan Turing


#2 chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2072 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 22-02-2014 - 18:08

Bài toán .

Ở 1 xứ sở nọ nơi cách rất xa nơi chúng ta đang ở, nơi Mọt Toán sinh sống, các Mọt Toán có hình dạng là 1 dãy các khoang trắng và đen. 1 Mọt Toán được gọi là "đẹp" nếu chỉ gồm toàn các khoang trắng. Việc làm đẹp (tẩy trắng) 1 Mọt Toán được tiến hành như sau : Nếu khoang cuối của Mọt có màu đen, bác sĩ có thể cắt bỏ và ghép 1 khoang màu trắng hoặc đen tùy ý lên đầu con Mọt, nếu khoang cuối của nó màu trắng, thì khoang cuối này sẽ tự biến mất và Mọt Toán tự mọc thêm vào trên đầu 1 khoang (nhưng bác sĩ không biết đc là trắng hay đen). Mặc dù quá trình tẩy trắng phức tạp như vậy nhưng Bác Sĩ Cuội vẫn khắng định có thể làm đẹp 1 mọt toán bất kì. Hỏi bác sĩ nói có đúng không ?

Mọt Toán muốn " làm đẹp " thì trước hết phải làm cho cực " xấu " (tức là phải " làm đen toàn thân ", ấy gọi là " bĩ cực thái lai " hay là " khổ nhục kế " :luoi: !!!)

Cụ thể, với $1$ cô Mọt bất kỳ, bác sĩ thẩm mỹ sẽ làm như sau ($2$ giai đoạn) : 

Giai đoạn $1$ :

+ Nếu khoang cuối màu Đen, bác sĩ sẽ cắt bỏ khoang đó và ghép $1$ khoang Đen lên đầu cô ấy.

+ Nếu khoang cuối màu Trắng, quá trình làm đẹp sẽ làm biến mất khoang ấy và sẽ xuất hiện $1$ khoang khác (Trắng hoặc Đen) ở trên đầu.

+ Các công đoạn trên cứ lặp đi lặp lại.Sau mỗi công đoạn, số khoang Đen sẽ giữ nguyên hoặc tăng thêm $1$ khoang.Chắc chắn đến một lúc nào đó, tất cả các khoang của cô Mọt sẽ có màu Đen.Giai đoạn $1$ kết thúc.

 

Giai đoạn $2$ :

+ Mỗi lần cắt bỏ $1$ khoang cuối (màu Đen), bác sĩ lại gắn lên đầu $1$ khoang Trắng.

+ Cứ tiếp tục thực hiện như vậy cho đến khi cô Mọt trắng hoàn toàn.Kết thúc quá trình làm đẹp.

 

Kết luận : Mặc dù lời bác sĩ Cuội nói thì phải cảnh giác, nhưng trong trường hợp này thì có thể ... tạm tin được  >:) !


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#3 PolarBear154

PolarBear154

    Sĩ quan

  • Thành viên
  • 396 Bài viết
  • Giới tính:Nữ
  • Đến từ:Cát bụi
  • Sở thích:Ngất ngưởng =)

Đã gửi 05-07-2014 - 16:04

Mọt Toán muốn " làm đẹp " thì trước hết phải làm cho cực " xấu " (tức là phải " làm đen toàn thân ", ấy gọi là " bĩ cực thái lai " hay là " khổ nhục kế " :luoi: !!!)

Cụ thể, với $1$ cô Mọt bất kỳ, bác sĩ thẩm mỹ sẽ làm như sau ($2$ giai đoạn) : 

Giai đoạn $1$ :

+ Nếu khoang cuối màu Đen, bác sĩ sẽ cắt bỏ khoang đó và ghép $1$ khoang Đen lên đầu cô ấy.

+ Nếu khoang cuối màu Trắng, quá trình làm đẹp sẽ làm biến mất khoang ấy và sẽ xuất hiện $1$ khoang khác (Trắng hoặc Đen) ở trên đầu.

+ Các công đoạn trên cứ lặp đi lặp lại.Sau mỗi công đoạn, số khoang Đen sẽ giữ nguyên hoặc tăng thêm $1$ khoang.Chắc chắn đến một lúc nào đó, tất cả các khoang của cô Mọt sẽ có màu Đen.Giai đoạn $1$ kết thúc.

 

Giai đoạn $2$ :

+ Mỗi lần cắt bỏ $1$ khoang cuối (màu Đen), bác sĩ lại gắn lên đầu $1$ khoang Trắng.

+ Cứ tiếp tục thực hiện như vậy cho đến khi cô Mọt trắng hoàn toàn.Kết thúc quá trình làm đẹp.

 

Kết luận : Mặc dù lời bác sĩ Cuội nói thì phải cảnh giác, nhưng trong trường hợp này thì có thể ... tạm tin được  >:) !

Trường hợp số khoang đen giữ nguyên thì làm sao bạn? Tức là tới trạng thái có 1 khoang trắng đang ở vị trí cuối cùng, nó biến mất, xuất hiện khoang ở đầu cũng màu trắng, lúc này cái quy luật đen chuyển hết thành đen vẫn tiếp tục nhưng mình không khống chế được khoang trắng mà? Nếu khoang đó cứ cứng đầu trắng->trắng tuần hoàn thế thì xem ra k bôi đen hết được rồi, bạn nhỉ :)


Trong bất cứ hoàn cảnh công việc nào, không cúi đầu trước cái ác, không lùi trước hiểm nạn. Nhìn thẳng và đi trên con đường mình đã chọn: con đường mà sự nhẫn nại bao dung là những bước đi tới, hành trang là những ước mơ vô cùng bé nhỏ- chỉ xin làm một cành dương tưới trên cuộc đời đầy rẫy khô khát và bất trắc... 


#4 chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2072 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 05-07-2014 - 16:51

Trường hợp số khoang đen giữ nguyên thì làm sao bạn? Tức là tới trạng thái có 1 khoang trắng đang ở vị trí cuối cùng, nó biến mất, xuất hiện khoang ở đầu cũng màu trắng, lúc này cái quy luật đen chuyển hết thành đen vẫn tiếp tục nhưng mình không khống chế được khoang trắng mà? Nếu khoang đó cứ cứng đầu trắng->trắng tuần hoàn thế thì xem ra k bôi đen hết được rồi, bạn nhỉ :)

Đề bài nói rằng : "Nếu khoang cuối của nó màu trắng, thì khoang cuối này sẽ tự biến mất và Mọt Toán tự mọc thêm vào trên đầu $1$ khoang (nhưng bác sĩ không biết được là trắng hay đen)"

Như vậy có nghĩa là màu của khoang mọc thêm trên đầu (trắng hay đen) là hoàn toàn ngẫu nhiên.Nói theo kiểu xác suất - thống kê là xác suất xuất hiện khoang đen là $a$ ($0< a< 1$), và xác suất xuất hiện khoang trắng là $1-a$.

Lưu ý rằng $a\neq 0$ và $a\neq 1$.Vì nếu $a=0$ tức là bác sĩ sẽ biết trước khoang đó màu trắng, còn nếu $a=1$ thì bác sĩ sẽ biết trước khoang đó màu đen (trái với giả thiết là bác sĩ không biết trước màu của khoang này).

Vì xác suất xuất hiện khoang đen là khác $0$ nên nếu cứ lặp lại mãi các công đoạn ở giai đoạn $1$ thì chắc chắn sẽ đến lúc nào đó, khi khoang trắng cuối cùng biến mất thì khoang mới xuất hiện có màu đen.Khi đó giai đoạn $1$ kết thúc.Mọt Toán được "làm đen" hoàn toàn !


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#5 PolarBear154

PolarBear154

    Sĩ quan

  • Thành viên
  • 396 Bài viết
  • Giới tính:Nữ
  • Đến từ:Cát bụi
  • Sở thích:Ngất ngưởng =)

Đã gửi 05-07-2014 - 17:05

Đề bài nói rằng : "Nếu khoang cuối của nó màu trắng, thì khoang cuối này sẽ tự biến mất và Mọt Toán tự mọc thêm vào trên đầu $1$ khoang (nhưng bác sĩ không biết được là trắng hay đen)"

Như vậy có nghĩa là màu của khoang mọc thêm trên đầu (trắng hay đen) là hoàn toàn ngẫu nhiên.Nói theo kiểu xác suất - thống kê là xác suất xuất hiện khoang đen là $a$ ($0< a< 1$), và xác suất xuất hiện khoang trắng là $1-a$.

Lưu ý rằng $a\neq 0$ và $a\neq 1$.Vì nếu $a=0$ tức là bác sĩ sẽ biết trước khoang đó màu trắng, còn nếu $a=1$ thì bác sĩ sẽ biết trước khoang đó màu đen (trái với giả thiết là bác sĩ không biết trước màu của khoang này).

Vì xác suất xuất hiện khoang đen là khác $0$ nên nếu cứ lặp lại mãi các công đoạn ở giai đoạn $1$ thì chắc chắn sẽ đến lúc nào đó, khi khoang trắng cuối cùng biến mất thì khoang mới xuất hiện có màu đen.Khi đó giai đoạn $1$ kết thúc.Mọt Toán được "làm đen" hoàn toàn !

Mình chưa học về xác suất, chỉ nghĩ đơn giản là phải xét tới tất cả các trường hợp có thể xảy ra :)


Trong bất cứ hoàn cảnh công việc nào, không cúi đầu trước cái ác, không lùi trước hiểm nạn. Nhìn thẳng và đi trên con đường mình đã chọn: con đường mà sự nhẫn nại bao dung là những bước đi tới, hành trang là những ước mơ vô cùng bé nhỏ- chỉ xin làm một cành dương tưới trên cuộc đời đầy rẫy khô khát và bất trắc... 


#6 WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản trị
  • 1322 Bài viết
  • Giới tính:Nam

Đã gửi 05-07-2014 - 20:12

 

Vì xác suất xuất hiện khoang đen là khác $0$ nên nếu cứ lặp lại mãi các công đoạn ở giai đoạn $1$ thì chắc chắn sẽ đến lúc nào đó, khi khoang trắng cuối cùng biến mất thì khoang mới xuất hiện có màu đen.Khi đó giai đoạn $1$ kết thúc.Mọt Toán được "làm đen" hoàn toàn !

Bạn có chắc chắn dòng in đậm không :-/ ?

Hay mình thử lấy ví dụ thế này nhé, giả sử có 1 con mọt "cứng đầu" có các khoang là Đen Trắng Đen từ trên xuống dưới, nếu làm theo thuật toán bên trên của bạn + với việc khoang trắng của con mọt luôn trở thành khoang trắng sau khi biến đổi (Vì con mọt "cứng đầu" mà ) vậy nên số khoang trắng luôn $\geq 1$....
P/s : Bài toán này không phải của mình mà là mình học được trong đợt ôn thi, nhưng chắc chắn là đề bài đúng vì mình đã có lời giải ;)


$$n! \sim \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$$

 

“We can only see a short distance ahead, but we can see plenty there that needs to be done.” - Alan Turing


#7 chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2072 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 05-07-2014 - 21:28

Bạn có chắc chắn dòng in đậm không :-/ ?

Hay mình thử lấy ví dụ thế này nhé, giả sử có 1 con mọt "cứng đầu" có các khoang là Đen Trắng Đen từ trên xuống dưới, nếu làm theo thuật toán bên trên của bạn + với việc khoang trắng của con mọt luôn trở thành khoang trắng sau khi biến đổi (Vì con mọt "cứng đầu" mà ) vậy nên số khoang trắng luôn $\geq 1$....
P/s : Bài toán này không phải của mình mà là mình học được trong đợt ôn thi, nhưng chắc chắn là đề bài đúng vì mình đã có lời giải ;)

Không phải đề bài sai, mà là có chỗ chưa chặt chẽ (dẫn đến việc có $2$ cách hiểu)

Đó là chỗ "bác sĩ không biết được (khoang mọc thêm) là trắng hay đen" 

Thông thường, người ta hiểu là khoang mọc thêm đó, CÓ THỂ là trắng, cũng CÓ THỂ là đen (khả năng nào cũng CÓ THỂ, chính vì thế mà bác sĩ không biết trước được).Mà nếu màu đen có thể xảy ra thì xác suất xuất hiện màu đen sẽ lớn hơn $0$, có nghĩa là trong một ngàn lần, một triệu lần, một tỷ lần (hay nhiều hơn nữa ...) khoang trắng biến mất thì cũng sẽ có ít nhất $1$ lần (không thể $0$ lần) khoang đen xuất hiện.Như vậy, giả thiết "bác sĩ không biết (khoang mọc thêm) là đen hay trắng" đồng nghĩa với "con mọt cứng đầu" mà bạn nói, không thể tồn tại.(Mình hiểu theo cách này nên mới có lời giải như trên)

Lại có thể có cách hiểu khác là khoang mọc thêm đó, CÓ THỂ là trắng, CÓ THỂ là đen (nhưng điều này chỉ đúng với một số cá thể mọt), còn với một số cá thể mọt khác thì lại là LUÔN LUÔN trắng (hoặc LUÔN LUÔN đen).Nếu hiểu theo cách này thì "con mọt cứng đầu" như bạn nói, có thể tồn tại và không thể "làm đen" nó được.

Vậy là lời giải thế nào còn tùy thuộc vào cách hiểu đề ra sao, tiếc rằng đề chưa rõ ràng mà không thể gặp người ra đề để hỏi cho rõ (!)


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#8 ChinhLu

ChinhLu

    Binh nhất

  • Thành viên
  • 38 Bài viết
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 06-07-2014 - 23:17

Mình thấy bài toán này vẫn chưa được giải quyết trọn vẹn. Không hiểu sau mod lại đưa ra thêm bài mới. Như vậy liệu có mâu thuẫn với tiêu chí của ban tổ chức không? 

 

Lời giải của bạn chanhquocnghiem là khá hay và thú vị. Tuy nhiên nếu hiểu đề bài theo nghĩa "mới" (theo như người ra đề đã giải thích) thì sẽ tồn tại một con mọt thông minh (vì nó là mọt Toán mà). Vì nó thông minh nên mỗi lần đổi màu khoang trắng nó sẽ làm cho bác sỹ phải thất vọng. Lúc này nếu bác sỹ làm theo kế sách của bạn chanhquocnghiem thì bác sỹ sẽ kiên nhẫn ngồi chờ sơ hở của con mọt. 

 

Có cách nào để làm trắng mọi con mọt không, kể cả những con mọt thông minh và không muốn bị tẩy trăng? 

 

Sau đây, mình xin trình bày một cách tẩy trắng universal (có tác dụng trên tất cả mọt). Cách làm của mình dựa theo ý tưởng của bác sỹ chanhquocnghiem. 

 

Giả sử ta cần tẩy trắng một con mọt Toán. Ta đánh dấu các khoang trắng bởi các số $0$ và khoang đen bởi số $1$ và chọn một vị trí gốc để sao cho số nhị phân thu được là lớn nhất (viết theo chiều từ đầu đến đuôi rồi quay lại nếu vẫn còn khoang phía sau). Ta gọi số này là độ trắng của mọt. Để dễ hình dung ta xét ví dụ sau:

 

Mọt có các khoang là  :  DTDTDT 

Khi đó (chọn gốc ở chỗ nào thì cũng tính đươc cùng một độ trắng) độ trắng của mọt là $101010 = 2^5 +2^3+2^1=42$.

 

Áp dụng ý tưởng của bác sỹ chanhquocnghiem chúng ta cần một thuật toán để làm tăng độ trắng của mọt.

 

Xét một con mọt bất kỳ và ta đánh dấu vị trí gốc của nó (có thể có nhiều, khi đó chỉ cần chọn một gốc là được). Ta cũng đánh dấu vị trị ngọn (khoang màu đen cuối cùng tính từ gốc theo hướng từ đầu đến đuôi).  Nếu ngọn không nằm ở đuôi thì ta cứ chờ. Vì nếu như mọt tự biến một khoang trắng thành đen thì độ trắng sẽ tăng lên mà ta chưa cần phải làm gì cả. Nếu ngọn nằm ở đuôi thì ta làm trắng khoan đấy. Tiếp theo nếu mọt làm đen bất cứ khoan nào trước khoang gốc thì độ trắng cũng sẽ tăng lên (Đây là một tính chất khá thú vị của số nhị phân, Exercise?).  Nếu mọt không chịu chuyển màu thì ta cứ việc chuyển đen thành trắng và mọt sẽ trắng toàn thân. 

 

Như vậy sau mỗi bước, mọt sẽ hoặc là trắng toàn thân hoặc là tăng độ trặng Khi mà độ trắng maximum rồi thì mọt đen toàn thân và bác sỹ chanhquocnghiem đã chỉ cho chúng ta cách tẩy trắng một con mọt đen toàn thân như thế nào.


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





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

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