Toán mà không phải toán thì làm sao giải?

#1

Chào mọi người, vì lâu quá ko thấy forum discuss vấn đề gì thật sự có liên quan chút gì đó đến programming, nên nay mình thả chút bait cho mọi người chửi chơi, vì như đã discuss ở Discord thì gần như đa số đều đồng ý là chỉ có toán là ngôn ngữ chung mà đa số chúng ta có thể tham gia discuss, nên nay nhân mùa COVID-19, mình nhận được câu hỏi của một bác sỹ giấu tên bên ở một bệnh viện nổi tiếng ở Biên Hoà gởi đến, mong nhận được giải đáp của mọi người.
Vì là mùa COVID-19 nên đề có hơi ghê:

  • Có 23 bệnh nhân bị đưa đến khi cách ly, và sẽ được cách ly trong các phòng đánh số thứ tự từ 1-23.

  • Các phòng này là tách biệt hoàn toàn khỏi bên ngoài, ko có cách nào liên lạc với bên ngoài or giữa các phòng với nhau.

  • Có 1 phòng đặc biệt riêng là phòng số 0, bên trong có 2 cái công tắc được đặt tên lần lượt là X và Y, hai công tắc này chỉ có thể bật/tắt. và hiện tại ko biết trạng thái của mỗi công tắc là gì.

  • Ai cũng sẽ được đưa vào phòng số 0, và mỗi người khi vào phòng chỉ được bật 1 công tắc duy nhất và chỉ được bật 1 lần duy nhất và bắt buộc phải bật.

  • Không có giới hạn cách chuyển bệnh nhân vào phòng số 0, không có giới hạn số lần 1 bệnh nhân được chuyển vào phòng số 0. Tức là có thể chuyển theo bất cứ thứ tự nào, có thể một người được vô nhiều lần.

  • Tại bất cứ lúc nào, bất cứ bệnh nhân nào cũng có thể tuyên bố là 23 bệnh nhân đều đã ít nhất 1 lần vào phòng số 0, nếu đúng tất cả được tự do, nếu sai tất cả bị nhốt vĩnh viễn. Tức là chỉ được trả lời duy nhất 1 lần bởi bất cứ ai và tại bất cứ thời điểm nào.

  • Trước khi bắt đầu việc đưa các bệnh nhân vào phòng số 0, thì tất cả bệnh nhân được họp mặt 1 lần duy nhất.

Câu hỏi: Làm sao để tất cả bệnh nhân được thả?

10 Likes
#2

Mình không hiểu đoạn này “nếu đúng” là đúng cái gì? Ai đúng? Ai giải thích giúp với.

1 Like
#3

Tức là khi có bất kỳ người nào tự tuyên bố là:“tất cả chúng tôi đã vào phòng số 0” mà nếu đúng là vậy thì được thả.

4 Likes
#4

Theo mọi người, ở bài toán này chúng ta có phải “khử nhiễu” trước khi tiến hành giải không? Yếu tố nhiễu ở đây là công tắc điện, nó chẳng có giá trị gì để biết vì không hai công tắc phối hợp sẽ có các trạng thái:
00
01
10
11
Có dính dáng gì đến con số 23? Loại công tắc này chắc không hiển thị số lần bật tắt trên mặt công tắc.

Nếu là bài toán thực sự, ở đây sẽ bỏ các yếu tố gọi là đố mẹo kiểu chim đứng trên cây bắn phát súng nổ.

Vậy thì ta chỉ có thể đoán rằng nếu người tuyên bố là trong buổi chiều, tức là một quãng thời gian đủ dài để lần lượt 22 người kia đủ vào, thế có một người lười biếng chẳng thèm vào đó thì hỏng bét.

23 người kia sẽ bàn với nhau cách gì? Liệu 2 công tác kia có thể sử dụng làm dụng cụ đánh Morse code ra tín hiệu qua đèn chớp nháy tít tít tè tè gì đó không hay hai công tắc đó chẳng nối với thiết bị nào, chỉ để bật qua bật lại?

Bài toán này có lẽ không phải là bài toán máy tính có thể giải đơn giản vì phải đặt giả thiết rồi loại suy logic?

5 Likes
#5

Với mỗi người, lần đầu sẽ bật công tắc X, các lần sau chỉ bật công tắc Y.

3 Likes
#6

đề có thêm câu ko có giới hạn số lần chuyển bệnh nhân vào phòng số 0 vào mà, vậy nghĩa là có nhiều hơn 2 bit X Y đó. Thật ra có vô tận X1Y1, X2Y2, X3Y3, … vậy chắc chắn sẽ có cách truyền thông tin N người đã vào phòng số 0 hay chưa.

3 Likes
#7

Bật 1 lần duy nhất. Tức người đó vô thấy chưa bật thì bật? Nếu vậy 2 công tắc bật rồi thì sao? :thinking:
Có 2 công tắc, bật 1 lần. Vậy mỗi công tắc buộc phải bật 1 lần? Hay chỉ được 1 làn bật 1 công tắc?

3 Likes
#8

Bật ở đây chắc là toggle chứ nhỉ :thinking: chứ nếu bật theo đúng nghĩa là “bật sáng” thì đến trạng thái bật - bật là game dừng rồi.

2 Likes
#9

Có nghĩa là nếu một người phải phòng người đó chỉ được bật công tắc X or Y, bắt buộc phải bật một trong 2, ko có chuyện bật xong 1 cái rồi lại bật tiếp cái nữa. Ko quan tâm trạng thái công tắt lúc mới vào phòng, cứ vào là phải bật 1 cái bất kỳ.

4 Likes
#10

Điều các bệnh nhân biết chỉ trạng thái hiện tại của X và Y. Tức tối đa 4 trạng thái. Mà mọi trạng thái của X và Y có vô tận phép biến đổi. Người bị giam không biết bao nhiêu lượt vào/ra phòng số 0. Nên không có cách nào truy vết X và Y đang ở trạng thái thứ mấy được.

Như nếu vào gặp 00
Thì có bét nhất 5 cách
11 -> 01 -> 00
11 -> 10 -> 00
01 -> 00
10 -> 00
00

Chưa kể trường hợp: 01 -> 00 -> 01 -> 00 -> 01 bởi 1 người duy nhất

Với dù nếu có biết số lượt ra / vào thì trường hợp 1 người vào ra liên tục cũng gây nhiễu vì bắt buộc phải thay đổi trạng thái
00 -> 01 -> 00 -> 01 -> …

Mình nghĩ bài này thiếu/sai dữ kiện hoặc chỉ là đố mẹo chứ không phải là toán :woman_shrugging:

3 Likes
#11

2 cái nối kiểu XOR rồi đếm số lần thay đổi trạng thái :smile:

2 Likes
#12

Đây là một bài đố mẹo, nên giải quyết đơn giản.

Đề không giới hạn thời gian. 23 ông ngồi với nhau cứ phân công ông này hôm nay vào, ông kia hôm thứ 2, ông khác hôm thứ 3… ông thứ 23 có nhiệm vụ vào bật đại cái công tắc nào đó rồi chốt sổ.

6 Likes
#13

Bạn đang tính mỗi người sở hữu một công tắc hay sao? Mình thì không thấy được sự phức tạp vấn đề như vậy vì tại mỗi thời điểm khi nhìn vào công tắc (không tính quá trình) thì ta chỉ thấy như sau
tắt tắt
bật tắt
bật bật
tắt tắt

Không rõ bạn có trạng thái nào nữa thì cho mình biết? Hay là có công tắc nó:
không bật - không tắt. Nếu có trường hợp này thì càng phải nhanh chóng loại bỏ yếu tố gây nhiễu là công tắc ra khởi vấn đề cần xử lý.

Ta chỉ cần xử lý vấn đề là tại thời điểm nào đó ai đó làm thầy bói đoán rằng mọi người khác đã từng ghé qua căn phòng. Có lẽ mỗi người vào đó thì nằm bò xuống đất ngửi mùi trước khi tè một bãi (vì đề toán không cấm việc này, và việc tè thì không cần phải có thêm dụng cụ gì mang theo). Làm sao chắc rằng đã có 23 người tè rồi, đó là cái chúng ta phải tìm.

3 Likes
#14

dân coder bị lậm số nhị phân quá :rofl: bài này ko liên quan gì tới số nhị phân đâu. Nó liên quan tới signal hơn. Mình cũng gg ra kết quả chứ có giải được đâu vì cũng bị rớt xuống lỗ nhị phân đó.

đại khái nó thế này: dùng 1 công tắc để signal cho người đếm số biết có người mới vào phòng này hay chưa. Nếu người đếm số vào thấy công tắc ví dụ là X đó bật, mà trước đó người đếm số đã tắt X, nghĩa là đã có người vào trước người đếm số, vậy người đếm số tắt X và tăng biến đếm lên 1, cứ thế tới 22 là ok.

chi tiết cách thực hiện thì tự suy luận nha =] mà đọc lời giải thì thấy nếu 23 người bị đưa vào phòng số 0 theo 1 quy luật nhất định thì có thể ko bao giờ ra khỏi khu cách ly =]
edit: và số 23 cũng là ngẫu nhiên thì phải? Cho chạy tới 1 tỷ người cũng được :V

3 Likes
#15

Cách đơn giản nhất là … trốn.

5 Likes
#16

Nhưng mới đầu đâu biết trạng thái X? :thinking:
Như bật thì liệu nó bật từ trước hay có người trước bật?
Tương tự những người còn lại cũng đâu biết rằng X được bật hay tắt là đã được đếm rồi?

4 Likes
#17

thì vậy mới nói là tự suy luận các bước, if else đâu :expressionless: đưa lời giải ra thì còn gì vui :unamused:

4 Likes
#18

:kissing: Thì thấy sai báo lại thui mà
Như người đếm kêu mị thấy công tắc mở = có người mới vô. Ai vô rồi thì qua Y mà bật, đừng dụng X nữa.
Cái người đếm được vô đầu tiên, công tắc mở -> đếm 1.
Cứ vậy đếm tới 22 (tín hcar người đếm) nhưng lần đầu bị đếm vô rồi -> sai mất rồi :thinking:

4 Likes
#19

thì người đếm nếu là lần đầu tiên vô phòng số 0, mà thấy X bật thì tắt, nhưng đừng tăng biến đếm, đơn giản :unamused:

5 Likes
#20

Hmmm
hMhmhM

image
image.jpg800×450 63.3 KB

THật thú vị

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?