Welcome, %1$s. Please login or register.

February 21, 2018, 05:11:22 PM
: 1
: Who survives?  ( 9519 )
« : June 05, 2007, 01:26:02 PM From spazinvader»



Who survives?


There are totally 2000 persons in a great hall.Everyone is named in numbers such as 1 to 2000(including 1 and 2000).They are arranged in the ascending order.A gun is given to the person 1.Person 1 will shoot the one next to him and give it to the person who is surviving next to the dead person.
(i.e)1 will kill 2 and give it to 3,
3 will kill 4 and give it to 5,
and so on.
This process is repeated continuously until there are two persons left.
Who are the two people survives in the end?

HINT:Person 1 will not always get the gun to start.

 
Liked It? Share it!

              


« #1 : June 11, 2007, 05:22:47 PM From TU»

Pl specify when 1999 kills 2000 then the gun would be passed to 1 or 1997.
ans whether can they kill in descending order after that.

 ::)
« #2 : June 11, 2007, 05:30:23 PM From TU»

Assuming them to be standing in circular fashion i.e. 1 after 2000 the solution comes out to be 801 and 1601 will survive in the end. :-\
« #3 : June 12, 2007, 04:06:45 PM From Ria»

I tried applying Geometric progression formulae to it but failed to arrive at a precise answer as this puzzle doesn't encourage people to half murder or quarter-murder anyone. Smiley The puzzle would have been easier if the number involved were in powers of 2, 2048 for example.

Since the number is 2000, lets see how many rounds it will take to reach the number 2.

2000->1000->500->250->125->63->31->16->8->4->2

Number of rounds is 10 after which only 2 will be left.
After every round the difference between the survivors will be a multiple of 2. Hence after 10 rounds it will be 2^10 which is 1024.

Now lets find the first survivor.
It cannot be one as after round 5 person 1 will be shot. Now the next survivor who will get the gun after round 5 is 2^5 + 1=32 + 1=33.
After round 6, person 33 will be shot. So the next survivor will be 2^6 + 33 = 64 + 33 = 97
There isn't any odd number of survivor again and hence 97 survives till the end.
The second survivor is 97+1024= 1121

Hence the 2 survivors are 97 & 1121.
« #4 : June 16, 2007, 10:10:00 PM From spazinvader»

No
Both the answers are wrong.
The persons are standing in a circular way and the gun will not be reversed in its direction.
« #5 : June 22, 2007, 10:39:35 AM From clnbabu»

1 and 1999 will survive
« #6 : June 30, 2007, 01:15:38 AM From prithvi»

1 and 1025 will survive
« #7 : July 08, 2007, 07:16:38 PM From spazinvader»

1 will never survives upto the end.
Anymore answers?Or shall i give the answer?
« #8 : July 10, 2007, 07:08:00 PM From Prateek»

The last 2 people who will survive are 465 and 977.
 :)
« #9 : July 10, 2007, 07:09:41 PM From Prateek»

The C Code that I used is here
-----------------------------------

int getNextAlive(int people[], int current_alive );

int _tmain(int argc, _TCHAR* argv[])
{
   int people[1001];
   int i = 1;
   int last_alive;

   memset( people, 0, 1001 * sizeof(int));

   while(1)
   {
      last_alive = i;
      i = getNextAlive(people, i);
      if( i == -1 )
      {
         printf("Last person Standing %d\n", last_alive);
         return 0;
      }

      printf(" %d ", i);
      // Kill him
      people[ i ] = 1;

      last_alive = i;
      i = getNextAlive(people, i);
      if( i == -1 )
      {
         printf("Last person Standing %d\n", last_alive);
         return 0;
      }
   }
}


int getNextAlive(int people[], int current_alive )
{
   for(int i = current_alive + 1; i<= 1000 ; i++ )
      if( !people[ i ] )return i;

   printf("\n------------------------------------\n");
   for(int i = 1; i < current_alive ; i++ )
      if( !people[ i ] )return i;

   return -1;
}


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


Last person Standing 977

« #10 : July 11, 2007, 10:47:43 PM From Ria»

Yes the answer is 977

Solution:

Let us find a generic formula. Let there be n people, numbered from 1 to n.
Now,

if n=2, then 1 will survive
if n=3, then 3 will survive
if n=4, then 1 will survive
if n=5, then 3 will survive
if n=6, then 5 will survive
if n=7, then 7 will survive
if n=8, then 1 will survive
if n=9, then 3 will survive
if n=10, then 5 will survive

Means, in general, if there are (2^n + x) persons, then (2x+1)th person will survive.
Just try the above stated situations on a paper and you'll come to know the relation for why is it so. :)
Actually on every addition of one person in the circle, surviving person shifts by two positions. And this process continues till the number of persons becomes a power of 2.

Now, as 1000 = 2^9 + 488, so 977th person (2*488 + 1) will survive.
« #11 : July 14, 2007, 07:51:44 PM From spazinvader»

Wow Prateek.
You are excellent one.It is the correct answer for 1000 persons.
But the question is for 2000 persons.
Try for the size as 2001 and give the answer man.
Surely you will do it in a minute.
Looking for your answer.
« #12 : July 14, 2007, 11:18:33 PM From Prateek»

Oh Sorry.. For 2000 the answer will be 929 & 1953  :)
« #13 : August 14, 2007, 07:39:56 PM From atul»

If there are 2^n people 1st person will survive (Check it out)

The 2^n type number closest to 2000 is 1024. So after after 2000-1024 i.e. 976 people are killed there would be exactly 1024 person left and person will the gun will survive in the end !

Mr. (976 *2 -1 ) i.e Mr. 1951 will kill Mr. 1952 and hand over the gun to Mr 1953. This is the time when 976 persons would have been killed and person starting the circle i.e. 1953 would survive in the end.
« #14 : August 15, 2007, 02:58:12 PM From atul»

Oh didn't notice that you had asked for the last two persons alive. In case of 2^n persons the last two persons are 1 and (2^n)/2 +1 i.e. for 1024 it will be 1 and 513.

I know last person is 1953. I need to find the 512nd person from that point in circle. easy way would be to go 512 persons back in circle, as half are dead so answer  = 1953 - 1024 = 929

Long way going 512 persons forward
2000-1953 = 47 still in circle
512 - 47 = 465 to be traversed from the number 1
that would be 465*2-1 = 929 because half the persons are dead
« #15 : August 15, 2007, 11:23:17 PM From spazinvader»

This is my part of logical explanation.
If u r calculating for n persons,and n is greater than 1000(to ensure that it is divisible by 2,4,8 and not a power of 2) and the value is like 1000,2000,4000,...
then they will strictly follow this.
The last 2 survivals will be in this format
(x*15)-(x/2)+1 and
(x*31)-(x/2)+1
where x is the power of 2 which could divide the n multiplied by 2.

For example,
In the case of 2000,it is divisible by 1,2,4,8,16 and not divisible by 32.
So here x is 32*2=64.
So the answer will be (64*15)-(64/2)+1=929
and (64*31)-(64/2)+1=1953.

For the case of 1000, the persons will be 465 and 977.
This works only if the range is 1000,2000,4000,.....
« #16 : August 17, 2007, 03:11:10 PM From atul»

I don't understand why you quote your formula in such a complicated manner instead of saying
X*29-1 and X*61-1
where x is the power of 2 which could divide the n !

there is difference of X*32... now i guess this would work only for 2000 and not work for  3000 because the difference between the two for the case of 3000 prisoner will be 2048 !

-Atul


This is my part of logical explanation.
If u r calculating for n persons,and n is greater than 1000(to ensure that it is divisible by 2,4,8 and not a power of 2) and the value is like 1000,2000,4000,...
then they will strictly follow this.
The last 2 survivals will be in this format
(x*15)-(x/2)+1 and
(x*31)-(x/2)+1
where x is the power of 2 which could divide the n multiplied by 2.

For example,
In the case of 2000,it is divisible by 1,2,4,8,16 and not divisible by 32.
So here x is 32*2=64.
So the answer will be (64*15)-(64/2)+1=929
and (64*31)-(64/2)+1=1953.

For the case of 1000, the persons will be 465 and 977.
This works only if the range is 1000,2000,4000,.....
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer