Brainteaser

CFA General
#1
  • There are 1000 people standing in line. They are labeled 1 through 1000.
  • Person 1 has a sword that he will use to kill the person who is next in line, i.e. Person 2.
  • Person 1 will then pass the sword to the next person, Person 3.
  • Person 3 will kill Person 4 and pass the sword to Person 5. This continues to the end of the line.
  • The survivor at the end of the line will pass the sword to the survivor at the front of the line. In this case, Person 999 will pass the sword back to Person 1.
  • The killing spree starts over with Person 1 killing Person 3 and passing the sword to Person 5. This continues until one survivor remains.

The question, as you have already guessed, is: Who is the last killer standing? Hint: It’s not Person 1.

#2

977?

#3

Jay-Z

#4

My wild-ass guess is that it’s the highest prime number less than 1000, I’m not sure what that is off the top of my head.

Looking up a table of prime numbers, that would be person 997.

Amazing that no one runs away while they are waiting or tries to fight back.

#5

Wrote some R code to solve the problem and villnius is right. How to get to that answer quickly is hard for me to see, but here are the results:

Survivor: 977

Fallen (in order):

(bracketed [numbers] are index counts, so ignore them)

[1] 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 [19] 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 [37] 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 [55] 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 [73] 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 [91] 182 184 186 188 190 192 194 196 198 200 202 204 206 208 210 212 214 216 [109] 218 220 222 224 226 228 230 232 234 236 238 240 242 244 246 248 250 252 [127] 254 256 258 260 262 264 266 268 270 272 274 276 278 280 282 284 286 288 [145] 290 292 294 296 298 300 302 304 306 308 310 312 314 316 318 320 322 324 [163] 326 328 330 332 334 336 338 340 342 344 346 348 350 352 354 356 358 360 [181] 362 364 366 368 370 372 374 376 378 380 382 384 386 388 390 392 394 396 [199] 398 400 402 404 406 408 410 412 414 416 418 420 422 424 426 428 430 432 [217] 434 436 438 440 442 444 446 448 450 452 454 456 458 460 462 464 466 468 [235] 470 472 474 476 478 480 482 484 486 488 490 492 494 496 498 500 502 504 [253] 506 508 510 512 514 516 518 520 522 524 526 528 530 532 534 536 538 540 [271] 542 544 546 548 550 552 554 556 558 560 562 564 566 568 570 572 574 576 [289] 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610 612 [307] 614 616 618 620 622 624 626 628 630 632 634 636 638 640 642 644 646 648 [325] 650 652 654 656 658 660 662 664 666 668 670 672 674 676 678 680 682 684 [343] 686 688 690 692 694 696 698 700 702 704 706 708 710 712 714 716 718 720 [361] 722 724 726 728 730 732 734 736 738 740 742 744 746 748 750 752 754 756 [379] 758 760 762 764 766 768 770 772 774 776 778 780 782 784 786 788 790 792 [397] 794 796 798 800 802 804 806 808 810 812 814 816 818 820 822 824 826 828 [415] 830 832 834 836 838 840 842 844 846 848 850 852 854 856 858 860 862 864 [433] 866 868 870 872 874 876 878 880 882 884 886 888 890 892 894 896 898 900 [451] 902 904 906 908 910 912 914 916 918 920 922 924 926 928 930 932 934 936 [469] 938 940 942 944 946 948 950 952 954 956 958 960 962 964 966 968 970 972 [487] 974 976 978 980 982 984 986 988 990 992 994 996 998 1000 3 7 11 15 [505] 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 [523] 91 95 99 103 107 111 115 119 123 127 131 135 139 143 147 151 155 159 [541] 163 167 171 175 179 183 187 191 195 199 203 207 211 215 219 223 227 231 [559] 235 239 243 247 251 255 259 263 267 271 275 279 283 287 291 295 299 303 [577] 307 311 315 319 323 327 331 335 339 343 347 351 355 359 363 367 371 375 [595] 379 383 387 391 395 399 403 407 411 415 419 423 427 431 435 439 443 447 [613] 451 455 459 463 467 471 475 479 483 487 491 495 499 503 507 511 515 519 [631] 523 527 531 535 539 543 547 551 555 559 563 567 571 575 579 583 587 591 [649] 595 599 603 607 611 615 619 623 627 631 635 639 643 647 651 655 659 663 [667] 667 671 675 679 683 687 691 695 699 703 707 711 715 719 723 727 731 735 [685] 739 743 747 751 755 759 763 767 771 775 779 783 787 791 795 799 803 807 [703] 811 815 819 823 827 831 835 839 843 847 851 855 859 863 867 871 875 879 [721] 883 887 891 895 899 903 907 911 915 919 923 927 931 935 939 943 947 951 [739] 955 959 963 967 971 975 979 983 987 991 995 999 5 13 21 29 37 45 [757] 53 61 69 77 85 93 101 109 117 125 133 141 149 157 165 173 181 189 [775] 197 205 213 221 229 237 245 253 261 269 277 285 293 301 309 317 325 333 [793] 341 349 357 365 373 381 389 397 405 413 421 429 437 445 453 461 469 477 [811] 485 493 501 509 517 525 533 541 549 557 565 573 581 589 597 605 613 621 [829] 629 637 645 653 661 669 677 685 693 701 709 717 725 733 741 749 757 765 [847] 773 781 789 797 805 813 821 829 837 845 853 861 869 877 885 893 901 909 [865] 917 925 933 941 949 957 965 973 981 989 997 9 25 41 57 73 89 105 [883] 121 137 153 169 185 201 217 233 249 265 281 297 313 329 345 361 377 393 [901] 409 425 441 457 473 489 505 521 537 553 569 585 601 617 633 649 665 681 [919] 697 713 729 745 761 777 793 809 825 841 857 873 889 905 921 937 953 969 [937] 985 1 33 65 97 129 161 193 225 257 289 321 353 385 417 449 481 513 [955] 545 577 609 641 673 705 737 769 801 833 865 897 929 961 993 49 113 177 [973] 241 305 369 433 497 561 625 689 753 817 881 945 17 145 273 401 529 657 [991] 785 913 81 337 593 849 209 721 465

Clearly it would suck severely to be person #465.

Interestingly, 977 is a prime number.

#6

You just keep doing this… Divide survivors by 2 if N is previously even. Minus 1 and divide by two if N is previously odd. If N is previously odd, remove lead survivor in next round and start with the next guy. Since the increments below scale by x2 in each round, this method scales quickly to large N and you can feasible calculate this by hand, even if N = 5000, 10,000, 100,000, etc.

Round 1 Survivors (1000)= 1, 1+1, 1+2, 1+3… [increment by 1]

Round 2 Survivors (500) = 1, 1+2, 1+3, 1+5… [increment by 2]

Round 3 Survivors (250) = 1, 1+4, 1+8, 1+12… [increment by 4: from now on, assume increment is x2 of the previous increment]

Round 4 Survivors (125) = 1, 1+8, 1+16… [8]

Round 5 Survivors (62, assuming the “jump” over Number 1 is in Round 4, so remove the first element. Do this whenever the previous round N is odd): 1+16, 1+32, 1+48… [16]

Round 6 Survivors (31): 1+16, 1+48, 1+80… [32]

Round 7 Survivors (15): 1+80, 1+144, 1+208… [64]

Round 8 Survivors (7): 1+208, 1+336, 1+464… [128]

Round 9 Survivors (3): 1+464, 1+720, 1+976 [256]

Round 10 Survivors (1): 1+976 = 977

#7

how many stabs does it take to kill one person?

if number 1 pass the sword to number 3 thinking number 2 is dead but he actually isn’t, then in round 2 the person gets up and can grab the sword from number 1 and kill number 1 and 3…

#8

My exact thought.

#9

Interesting that person #1 is the 938th person to die, given that 999 people end up dying. Person #1 lasts a fairly long line but ultimately bites it, rather like a Battlestar Galactica or Walking Dead character.

It does seem to follow Ohai’s rules well, though. #1 bites it at the start of round 5. At that point there are 1000/ 2^4 = 62.5 (round up to 63) people left. Of these 63 people, #1 dies, 61 others die after him/her, and person #977 survives.

#10

read wrongly from excel…deleted

#11

Good one!

But what’s the generic expression in terms of a total N number of people to start with?

#12

… and then throws the sword away!?

#13

There’s a passage from a PG Wodehouse story that springs to mind (I paraphrase):

A lion hunter was going to have his picture taken next to a lion that he had shot; he died because of a misunderstanding: he thought that the lion was dead; the lion thought that it wasn’t.

#14

“Thanks for coming in today, it was nice meeting you.”

#15

Worked it out…finally.

The last man standing is the person x, where

x = (2 * N + 1 ) - 2 ^ (INT(log(N,2)) +1)

N is the total number of people to start with

INT is the integer part of the number

log(x,y) is the log of x with base y

For N = 1000

x = (2 * 1000 +1) - 2^(INT(log(1000,2)) +1)

= 2001 - 2 ^ (INT(9.96) +1)

= 2001 - 2^(9+1)

= 2001 - 2^10

= 2001 - 1024

= 977

#16

Great question! My take on this: no closed form solution is possible for this problem. Rationale: the key issue in solving this problem is finding out which rounds end with the the sword in the hands of the person in ‘last position’ when the given round began. This is a simple task for the initial round, as it merely depends whether the number of ‘players’ (N in this case) is odd or even. In subsequent rounds however, you’ll see this depends on the resultant quotient from dividing 2 into the number of given players (if the total is even) or the number of players less 1 (if the total is odd). Finding an general expression for this quotient is very difficult to do for any N, as it is a direct consequence of whats called the ‘prime facorization’ on N. We (generally speaking here, mathematicians) still haven’t figured out how to generalize this expression for any given number (its easy to calulate using brute force), as such we’re stuck using compuational methods/simulation…

TLDR: To have a general solution, you need to know more about prime numbers than we currently do.

#17

2*N - 2 ^ (INT(log(N,2)+1) +1

seems to be working for me

#18

Very nice! My take above was assuming elementray functions - but your relation above certainly seems to work. NIce!

#19

So - just curious - how was this derived?

#20

Respect!