How do you solve the circular table problem?












14












$begingroup$


One classic puzzle has many different forms, but the basic strategy is the same.




Once upon a time there was a crazy king who had a very wise minister
with him. The king had a habit of playing a strange game on a circular table.



The game was played as follows: The king told his minister a different number everyday -
let's say he says 5. Then minister would then arrange five people and ask
them to sit in a circular table with five chairs. Starting from a specific person, the king would then kill every
second person on the table, until only one remained at the end, to which he would give 1,000 gold coins.



For example, if there were five people on the table, starting from
person 1, he would kill person 2, person 4, person 1, and person 5 (skipping over persons 2 and 4 since they are already dead),
leaving person 3 as the survivor and winner.



Now the wise minister was so clever as to calculate the winner
beforehand as soon as king said the number, and asked his man to sit
at particular seat so as to not be killed and also win some gold.



How did the minister decide the winner?







mathematics josephus-problem







share|improve this question











$endgroup$








  • 2




    $begingroup$
    How does the king decide where to start killing?
    $endgroup$
    – Kevin
    May 22 '14 at 12:47










  • $begingroup$
    Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday.
    $endgroup$
    – PM.
    May 22 '14 at 13:16
















14












$begingroup$


One classic puzzle has many different forms, but the basic strategy is the same.




Once upon a time there was a crazy king who had a very wise minister
with him. The king had a habit of playing a strange game on a circular table.



The game was played as follows: The king told his minister a different number everyday -
let's say he says 5. Then minister would then arrange five people and ask
them to sit in a circular table with five chairs. Starting from a specific person, the king would then kill every
second person on the table, until only one remained at the end, to which he would give 1,000 gold coins.



For example, if there were five people on the table, starting from
person 1, he would kill person 2, person 4, person 1, and person 5 (skipping over persons 2 and 4 since they are already dead),
leaving person 3 as the survivor and winner.



Now the wise minister was so clever as to calculate the winner
beforehand as soon as king said the number, and asked his man to sit
at particular seat so as to not be killed and also win some gold.



How did the minister decide the winner?







mathematics josephus-problem







share|improve this question











$endgroup$








  • 2




    $begingroup$
    How does the king decide where to start killing?
    $endgroup$
    – Kevin
    May 22 '14 at 12:47










  • $begingroup$
    Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday.
    $endgroup$
    – PM.
    May 22 '14 at 13:16














14












14








14


2



$begingroup$


One classic puzzle has many different forms, but the basic strategy is the same.




Once upon a time there was a crazy king who had a very wise minister
with him. The king had a habit of playing a strange game on a circular table.



The game was played as follows: The king told his minister a different number everyday -
let's say he says 5. Then minister would then arrange five people and ask
them to sit in a circular table with five chairs. Starting from a specific person, the king would then kill every
second person on the table, until only one remained at the end, to which he would give 1,000 gold coins.



For example, if there were five people on the table, starting from
person 1, he would kill person 2, person 4, person 1, and person 5 (skipping over persons 2 and 4 since they are already dead),
leaving person 3 as the survivor and winner.



Now the wise minister was so clever as to calculate the winner
beforehand as soon as king said the number, and asked his man to sit
at particular seat so as to not be killed and also win some gold.



How did the minister decide the winner?







mathematics josephus-problem







share|improve this question











$endgroup$




One classic puzzle has many different forms, but the basic strategy is the same.




Once upon a time there was a crazy king who had a very wise minister
with him. The king had a habit of playing a strange game on a circular table.



The game was played as follows: The king told his minister a different number everyday -
let's say he says 5. Then minister would then arrange five people and ask
them to sit in a circular table with five chairs. Starting from a specific person, the king would then kill every
second person on the table, until only one remained at the end, to which he would give 1,000 gold coins.



For example, if there were five people on the table, starting from
person 1, he would kill person 2, person 4, person 1, and person 5 (skipping over persons 2 and 4 since they are already dead),
leaving person 3 as the survivor and winner.



Now the wise minister was so clever as to calculate the winner
beforehand as soon as king said the number, and asked his man to sit
at particular seat so as to not be killed and also win some gold.



How did the minister decide the winner?







mathematics josephus-problem




mathematics josephus-problem






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Jun 13 '14 at 21:16









Gilles

3,42731837




3,42731837










asked May 22 '14 at 11:25









PM.PM.

170313




170313








  • 2




    $begingroup$
    How does the king decide where to start killing?
    $endgroup$
    – Kevin
    May 22 '14 at 12:47










  • $begingroup$
    Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday.
    $endgroup$
    – PM.
    May 22 '14 at 13:16














  • 2




    $begingroup$
    How does the king decide where to start killing?
    $endgroup$
    – Kevin
    May 22 '14 at 12:47










  • $begingroup$
    Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday.
    $endgroup$
    – PM.
    May 22 '14 at 13:16








2




2




$begingroup$
How does the king decide where to start killing?
$endgroup$
– Kevin
May 22 '14 at 12:47




$begingroup$
How does the king decide where to start killing?
$endgroup$
– Kevin
May 22 '14 at 12:47












$begingroup$
Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday.
$endgroup$
– PM.
May 22 '14 at 13:16




$begingroup$
Let's say chair very next to his place to sit is considered as first chair daily. But its the same everyday.
$endgroup$
– PM.
May 22 '14 at 13:16










1 Answer
1






active

oldest

votes


















16












$begingroup$

This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2cdot 3+1=7$, or $19_{10}=10011_2$ Left rotating one space gives $00111_2=7_{10}$






share|improve this answer











$endgroup$













  • $begingroup$
    See also A006257.
    $endgroup$
    – SQB
    May 22 '14 at 13:05










  • $begingroup$
    Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
    $endgroup$
    – PM.
    May 22 '14 at 13:22








  • 2




    $begingroup$
    In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
    $endgroup$
    – Ross Millikan
    May 22 '14 at 13:29














Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f371%2fhow-do-you-solve-the-circular-table-problem%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









16












$begingroup$

This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2cdot 3+1=7$, or $19_{10}=10011_2$ Left rotating one space gives $00111_2=7_{10}$






share|improve this answer











$endgroup$













  • $begingroup$
    See also A006257.
    $endgroup$
    – SQB
    May 22 '14 at 13:05










  • $begingroup$
    Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
    $endgroup$
    – PM.
    May 22 '14 at 13:22








  • 2




    $begingroup$
    In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
    $endgroup$
    – Ross Millikan
    May 22 '14 at 13:29


















16












$begingroup$

This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2cdot 3+1=7$, or $19_{10}=10011_2$ Left rotating one space gives $00111_2=7_{10}$






share|improve this answer











$endgroup$













  • $begingroup$
    See also A006257.
    $endgroup$
    – SQB
    May 22 '14 at 13:05










  • $begingroup$
    Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
    $endgroup$
    – PM.
    May 22 '14 at 13:22








  • 2




    $begingroup$
    In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
    $endgroup$
    – Ross Millikan
    May 22 '14 at 13:29
















16












16








16





$begingroup$

This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2cdot 3+1=7$, or $19_{10}=10011_2$ Left rotating one space gives $00111_2=7_{10}$






share|improve this answer











$endgroup$



This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2cdot 3+1=7$, or $19_{10}=10011_2$ Left rotating one space gives $00111_2=7_{10}$







share|improve this answer














share|improve this answer



share|improve this answer








edited Jun 13 '14 at 20:08









Gilles

3,42731837




3,42731837










answered May 22 '14 at 13:04









Ross MillikanRoss Millikan

5,8732138




5,8732138












  • $begingroup$
    See also A006257.
    $endgroup$
    – SQB
    May 22 '14 at 13:05










  • $begingroup$
    Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
    $endgroup$
    – PM.
    May 22 '14 at 13:22








  • 2




    $begingroup$
    In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
    $endgroup$
    – Ross Millikan
    May 22 '14 at 13:29




















  • $begingroup$
    See also A006257.
    $endgroup$
    – SQB
    May 22 '14 at 13:05










  • $begingroup$
    Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
    $endgroup$
    – PM.
    May 22 '14 at 13:22








  • 2




    $begingroup$
    In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
    $endgroup$
    – Ross Millikan
    May 22 '14 at 13:29


















$begingroup$
See also A006257.
$endgroup$
– SQB
May 22 '14 at 13:05




$begingroup$
See also A006257.
$endgroup$
– SQB
May 22 '14 at 13:05












$begingroup$
Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
$endgroup$
– PM.
May 22 '14 at 13:22






$begingroup$
Sorry for dumb question but I did not get the definition of m, n and p. Can you please explain what are the values of m,n and p in the example I explained in question?
$endgroup$
– PM.
May 22 '14 at 13:22






2




2




$begingroup$
In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
$endgroup$
– Ross Millikan
May 22 '14 at 13:29






$begingroup$
In your example, $n=5, m=2, p=1$, because there are $5=2^2+1$ people at the table and the winner is in seat $2 cdot 1+1=3$. For another example (because with small numbers it can be confusing what comes from where), if there were $19$ people at the table, we would write $19=2^4+3$ and the winner would be in seat $2 cdot 3+1=7$
$endgroup$
– Ross Millikan
May 22 '14 at 13:29




















draft saved

draft discarded




















































Thanks for contributing an answer to Puzzling Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f371%2fhow-do-you-solve-the-circular-table-problem%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

How to label and detect the document text images

Image
1 $begingroup$ This is what I mean as document text image: I want to label the texts in image as separate blocks and my model should detect these labels as classes. NOTE: This is how the end result should be like: The labels like Block 1, Block 2, Block 3,.. should be Logo, Title, Date,.. Others, etc. Work done: First approach : I tried to implement this method via Object Detection, it didn't work. It didn't even detect any text. Second approach : Then I tried it using PixelLink. As this model is build for scene text detection, it detected each and every text in the image. But this method can detect multiple lines of text if the threshold values are increased. But I have no idea how do I add labels to the text blocks. PIXEL_CLS_WEIGHT_all_ones = 'PIXEL_CLS_WEIGHT_all_ones' PIXEL_C...
Read more

Vallis Paradisi

Image
Coordinata: .mw-parser-output .geo-default,.mw-parser-output .geo-dms,.mw-parser-output .geo-dec{display:inline}.mw-parser-output .geo-nondefault,.mw-parser-output .geo-multi-punct{display:none}.mw-parser-output .longitude,.mw-parser-output .latitude{white-space:nowrap} 33°03′S 71°37′W  /  33.05°S 71.617°W  / -33.05; -71.617 Vallis Paradisi Res apud Vicidata repertae: Civitas : Chilia Numerus incolarum : 296 655 Zona horaria : UTC-4 Situs interretialis Nomen officiale : Valparaíso Gubernium Consilium : municipal council of Valparaíso Geographia Superficies : 401 600 000 Metrum quadratum Coniunctiones urbium Urbes gemellae : Ovetum , Badalona , Santa Fe , Ora longa , Sciamhaevum , Quantunia , Callao , Bat Yam , Melaka , Novorossiysk , Busan , Corduba , Odessa , Rosario , Malacca , Barcino , Soteropolis , Franciscopolis (California) , Guanajuato, Silao Tabula aut despectus Despectus in portum sinumque et urbem Vallis Paradisi Vallis Para...
Read more

Tabula Rosettana

Image
Tabula multilinguis Rosettana in Museo Britannico ostenditur. Tabula Rosettana, [1] etiam titulo OGIS 90 agnita, est stela decreto de rebus sacris in Aegypto anno 196 a.C.n. lato inscripta. Tabula iuxta Rosettam Aegypti, urbem in delta Nili et ad oram maris Mediterranei iacentem, anno 1799 a milite Francico reperta est. Inventio stelae, linguis duabus scripturisque tribus inscriptae, eruditis Instituti Aegypti statim nuntiata est; ibi enim iussu imperatoris Napoleonis eruditi omnium scientiarum (sub aegide Commissionis Scientiarum et Artium) properaverant cum expeditione Francica. Qua a Britannis mox debellata, tabula Rosettana Londinium missa hodie apud Museum Britannicum iacet. Textus Graecus cito lectus interpretationi textuum Aegyptiorum (in formis hieroglyphica et demotica expressorum) gradatim adiuvit. Denique textum plene interpretatus est Ioannes Franciscus Champollion. Ab opere eruditorum cumulativo coepit hodiernus scripturae hieroglyphicae linguaeque Aegyptiae a...
Read more