Khó quá chưa ai giải dc.... ^.^

[TRUNG-TIGER]

Bài toán như sau:
Có 100 người rủ nhau tự sát. Mọi người đứng thành vòng tròn, đánh số thứ tự từ 1 đến 100. Luật chơi là đếm lần lượt theo vòng tròn từ 1 đến 3, ai đếm 3 thì người đó phải tự sát, rồi người tiếp theo đếm lại từ 1. Bắt đầu từ người thứ nhất, đếm 1, đưa súng cho người thứ 2, đếm 2, đưa súng cho người thứ 3, đếm 3 rồi tự sát, người thứ 4 nhặt súng lên đếm 1, đưa súng cho người thứ 5, đếm 2, ... cứ thế đến khi chỉ còn lại 1 người cuối cùng (tới người 100 thì vòng lại 1). Hỏi người sống sót là người ở vị trí nào?


Xin trích lời bạn phương " rủ nhau tự sát " tức là thế này :

Câu chuyện là 1 bọn phản loạn gì đó, bị quân triều đình truy đuổi và bị dồn vào 1 cái hang. Nếu ai đầu hàng thì được sống, còn lại sẽ phải chết. Trong số 42 người của quân phản loạn kia có 1 nhà toán học; tất cả 42 người đều muốn chết, chỉ trừ 2 người muốn sống vì ở nhà còn mẹ già con côi j đó : D. Họ đã nói nhỏ với nhà toán học kia và ông đã bày ra trò chơi kia, ông đã sắp chỗ cho 2 người kia và họ là 2 người cuối cùng phải tự tự. Đương nhiên họ sẽ ra đầu hàng để thoát chết.....

[phuong]

Nếu đã là "rủ nhau tự sát" thì làm gì có người sống sót? Chẳng lẽ có kẻ nghĩ lại, không tự sát nữa?

[The Old Man]

Viết chương trình giải bài toán này thì rất dể. Nếu phải tính nhẩm hay làm toán bằng tay thì rắc rối dể lầm lẩn.
Không khó lắm nếu phải viết soft cho nó.

[15804]

Bài toán như sau:
Có 100 người rủ nhau tự sát. Mọi người đứng thành vòng tròn, đánh số thứ tự từ 1 đến 100. Luật chơi là đếm lần lượt theo vòng tròn từ 1 đến 3, ai đếm 3 thì người đó phải tự sát, rồi người tiếp theo đếm lại từ 1. Bắt đầu từ người thứ nhất, đếm 1, đưa súng cho người thứ 2, đếm 2, đưa súng cho người thứ 3, đếm 3 rồi tự sát, người thứ 4 nhặt súng lên đếm 1, đưa súng cho người thứ 5, đếm 2, ... cứ thế đến khi chỉ còn lại 1 người cuối cùng (tới người 100 thì vòng lại 1). Hỏi người sống sót là người ở vị trí nào?


Áp dụng lý thuyết số vào tính trong 10 giây thì người sống sót là người ở vị trí thứ 5. Không biết có đúng không nữa?

[atasi]

người sống sót là người ở vị trí thứ 58 :)

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

[hjpb0y_kute]

người số 58 đã ko tự sát nhưng anh ta lại bị nhà vua ra lệnh chém đâu+chu di 9 họ!=))

[TRUNG-TIGER]

khó nên ít bài thi quá :D

[vn999vn]

Không có người sống sót, đơn giản là vì ko ai muốn sống nên mới rủ nhau tự sát!..chỉ mẹo thôi mà...

[vn999vn]

Không có người sống sót, đơn giản là vì ko ai muốn sống nên mới rủ nhau tự sát!..chỉ mẹo thôi mà...

[luongmai]

Có đến 2 người sống sót chứ không phải 1 đó là người thứ 62 và 73
Haha

[TRUNG-TIGER]

các ông bác toàn "mò cua bắt ốc" thì sao ra đáp số dc ^_^

[ips]

Hai người sống sót là người thứ 31 và 77.
Nếu đếm tiếp thì người thứ 77 là người sóng sót cuối cùng.
Cách giải rất dài dòng, sẽ gửi đáp án sau.

[vneye]

Bài toán như sau:
Có 100 người rủ nhau tự sát. Mọi người đứng thành vòng tròn, đánh số thứ tự từ 1 đến 100. Luật chơi là đếm lần lượt theo vòng tròn từ 1 đến 3, ai đếm 3 thì người đó phải tự sát, rồi người tiếp theo đếm lại từ 1. Bắt đầu từ người thứ nhất, đếm 1, đưa súng cho người thứ 2, đếm 2, đưa súng cho người thứ 3, đếm 3 rồi tự sát, người thứ 4 nhặt súng lên đếm 1, đưa súng cho người thứ 5, đếm 2, ... cứ thế đến khi chỉ còn lại 1 người cuối cùng (tới người 100 thì vòng lại 1). Hỏi người sống sót là người ở vị trí nào?


Phải luôn luôn có 2 người sống chứ đâu phải 1 phải ko bạn, vì luôn phải đếm 1,2 rồi 3 mới chết mà.

Mình giải = Excel thử thì thấy 51 và 98 sống. Có giải thuật để tính ra điều này, để mình kiểm tra lại kỹ rồi post lên.

Câu hỏi khá hay, chừn nào giải đáp vậy?

[amida]

người ở vị trí số 1 sống :)

[homesweethome]

Tổng quát với n người:

F(n)
{
if(n==0)return 0;else return (F(n-1)+2)% n +1;
}

100 người => F(100)
1000 người => F(1000)


Tôi có 2 cách chứng minh :
-quy nạp
-tua ngược sự việc:đầu tiên có 1 người, đếm 123 thì sinh ra 1 người ... đến khi đủ 100 người thì dừng lại.

[amida]

The Josephus problem (or Josephus permutation) is a theoretical problem occurring in computer science and mathematics.
Cái này có thể dùng đệ quy thì phải :)
Vẫn có thể dùng dynamic programming đc :D Wiki họ bảo vậy:


The easiest way to solve this problem in the general case is to use dynamic programming. This approach gives us the recurrence:

f(n,k) = (f(n − 1,k) + k)mod n, with f(1,k) = 0

which is evident when considering how the survivor number changes when switching from n − 1 to n. This approach has running time O(n), but for small k and large n there is another approach. The second approach also uses dynamic programming but has running time O(klogn). It is based on considering killing k-th, 2k-th, ..., [n/k]-th people as one step, then changing the numbering.

[ktvthang]

phai con 2 nguoui song
55 vva 83
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 56 27
28 29 30
31 32 33
34 35 36
37 38 39
40 41 42
43 44 45
46 47 48
49 50 51
52 53 54
55 56 57
58 59 60
61 62 63
64 65 66
67 68 69
70 71 72
73 74 75
76 77 78
79 80 81
82 83 84
85 86 87
88 89 90
91 92 93
94 95 96
97 98 99
100
cac ban thu coi co dung khong nah
vi phai co nguoi dem 1va 2 moi duoc .va nguoi dem 1và cuoi cung la so 55 va 83

[songoku881]

Bạn nói là có hai người sống sót.Vậy mà lại hỏi "Hỏi người sống sót là người ở vị trí nào?"

Thế là thế nèo!!

[thai123]

nói wa nói lại em thấy bác"phuong" là nói có lý nhất "đã gọi là tự sát là ko còn ai sóng sót cả"

[khettiengdeptrai]

tôi nhớ báo toán học và tuổi trẻ đã từng nói và giải bài toán tổng quát cho n người co m người muốn sống. Bạn chịu khó mượn lại của ai đó báo trên ( nhất là của những người thích học toán )

[TRUNG-TIGER]

nói wa nói lại em thấy bác"phuong" là nói có lý nhất "đã gọi là tự sát là ko còn ai sóng sót cả"

tóm lại là " vẫn chưa ai giải dc" lol

[XPfake]

2 người sống sót nằm ở vị trí 58 và 91 đúng không?

[quangvu]

Công thức tìm người sống sót là
Với 2^n + c người, thì người sống sót là 2c+1 (với 2^n là số lớn nhất có thể, c < 2^n) .
Ví dụ :
người ---2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18
sống ---1---3---1---3----5--7---1---3---5----7----9---11--13--15--1---3---5

==> với 100 người, ta có
2^6 + 36 = 100 ===> n=6,c = 36
KQ : người sống sót là người thứ 73 .

Tham khảo thêm tại : http://www.pballew.net/josephus.html
Test lại tại đây, nhưng chỉ được đến 50 : http://www.cut-the-knot.org/recurrence/flavius.shtml

[quangvu]

Câu giải của tui đúng hem, sau kg thấy chủ topic trả lời nhở !?

[lee_huynh306]

Hình như còn 2 mạng sống sót là 58 và 91.

[TRUNG-TIGER]

bác chưa koi kỹ tiêu đề roài ^__^

[meoden8x]

Người thứ 100 phải không bác?

[meoden8x]

Hình như là có 2 người, người thứ 1 và 100 thì phải.

[luckyluke0110]

Chào các bạn. Lâu lém mới lên diễn đàn. Mình giải thử nhé.
Các người phải chết theo thứ tự sau:
3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54 ,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99 ==> 33 người
2,7,11,16,20,25,29,34,38,43,47,52,56,61,65,70,74,7 9,83,88,92,97 ==> 22 người
1,8,14,22,28,35,41,49,55,62,68,76,82,89,95 ==> 15 người
4,13,23,32,44,53,64,73,85,94
5,19,37,50,67,80,98
17,40,59,86
10,46,77
26,71
31,100
Còn lại 2 người ở vị trí 58 và 91

[luckyluke0110]

Mình nghĩ chính xác rồi đó. cho đáp án đi nha

[luckyluke0110]

Chào các bạn. Lâu lém mới lên diễn đàn. Mình giải thử nhé.
Các người phải chết theo thứ tự sau:
3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54 ,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99 ==> 33 người
2,7,11,16,20,25,29,34,38,43,47,52,56,61,65,70,74,7 9,83,88,92,97 ==> 22 người
1,8,14,22,28,35,41,49,55,62,68,76,82,89,95 ==> 15 người
4,13,23,32,44,53,64,73,85,94
5,19,37,50,67,80,98
17,40,59,86
10,46,77
26,71
31,100
Còn lại 2 người ở vị trí 58 và 91

[minhquan1712]

(tới người 100 thì vòng lại 1)

không hiểu ý câu này cho lắm. Có phải là đếm đến người thứ 100 thì quay lại đếm bắt đầu từ 1 không?(Nếu như vậy thì qúa dễ rồi) 1 đề bài không rõ ràng thì càng gây tò mò :D

[linh2307]

Mình làm theo cách nông dân là viết hêt ra và loại trừ (mình quên hết cách làm theo phương pháp toán học rồi)Mình thấy có 2 người ở vị trí 58 và 91 là sống sót.

[quangvu]

Chào các bạn. Lâu lém mới lên diễn đàn. Mình giải thử nhé.
Các người phải chết theo thứ tự sau:
3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54 ,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99 ==> 33 người
2,7,11,16,20,25,29,34,38,43,47,52,56,61,65,70,74,7 9,83,88,92,97 ==> 22 người
Còn lại 2 người ở vị trí 58 và 91

Mình nghĩ người số 2 chết rồi sẽ đến người số 5 chứ !

[nguchet]

Mình nghĩ người số 2 chết rồi sẽ đến người số 5 chứ !
:D josephus đây mà,
người thứ 2 rồi đếm tiếp 3 người nữa, vì người thứ 3 và 6 "chết" rồi bạn àh :)

[dat@]

Bài này chỉ có 1 người sống sót thôi. Nếu còn 2 người thì phải đếm lần lượt vòng tròn 2 người tới lượt ai cuối thì người đó chết.

[Nổ]

Bài này chỉ có 1 người sống sót thôi. Nếu còn 2 người thì phải đếm lần lượt vòng tròn 2 người tới lượt ai cuối thì người đó chết.

Và còn một người cuối cùng cũng tự đếm 1,2,3... sau đó cũng chết luôn. lol

[mh_61_mh]

Mình nghĩ người số 2 chết rồi sẽ đến người số 5 chứ !

bài giải đúng rồi đó bạn. số qua lượt 2 sẽ còn 100 1 2 4 5 7 8 ....
số 2 chết rồi tới số 7.

[TRUNG-TIGER]

thế nào rồi các bác, giải xong chưa nào ? ^^

[xitrumcan]

có 2 người sống ở vị trí thứ 58 và 86 (dung hok ta)

[mh_61_mh]

Theo mình, các bạn ra đáp án là 58 và 91 là đúng rồi.

[phuthinh100]

Theo mình hai người sống sót cuối cùng là số 58 và 91

[binhkien]

cuoi cung la nguoi thu may song noi ro cho minh biet thanks

[trantue]

ban tra loi duoc o giua la nguoi thu may khong

[zengla]

Đã là rủ nhau tự sát thì con ai sống đâu, các bạn áp dụng tính toán wa' nhiều đấy

[Let's-me-see]

1 người sống sót . người doa' o vi trí dầu tiên.

[vnhack]

Bắn 1 hồi hết đạn còn sống quá chời. he he.
Cái thằng sống sót là cái thằng ngồi ngoài đếm đó, bực mình! Trả lời thử coi, nếu không Logic tui cho đi theo đám đó luôn.
Bài này có gì mà khó ông bạn, ý ông bạn muốn sao, tui làm biếng tính lắm
Nhưng thấy hình như

[rungram]

có phải là 54 với 98 kô.tui lấy giấy viết ra 100 số ,cứ tới 3 là tôi gạch ,kakakaka .gạch tới cuối là trở về >>> hahaha,đúng kô bác

[cuong_war3]

Không có người sống sót, đơn giản là vì ko ai muốn sống nên mới rủ nhau tự sát!..chỉ mẹo thôi mà...

hay quá.tớ ủng hộ câu trả lời này

[thai123]

hi hay nhỉ
máy suy giào ốc tượng wá