Maximum number of kings on the chessboard subject to some rules
up vote
0
down vote
favorite
The chess king moves one square in any direction (horizontally, vertically, or diagonally). The goal is to place as many king as possible on an r×c board subject to the following two conditions:
- There is at most one king in any cell of the board.
- Each king has at least one possible move into a free cell on the board.
I tried to solve it by placing the kings on the corners of the chess board and adding them with the squares it will occupy in the middle of the board using alternating pattern based on the floor of the number of kings placed into the remaining rows and the number of remaining columns they can be kept.
I have taken into account that for a particular row and column the transpose of the chessboard will also give the same max number of kings.
However i am getting wrong answer for some cases.
Please let me know if my above approach is correct or is there any generalized formula which can be derived from the above?
combinatorics contest-math recreational-mathematics chessboard
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
add a comment |
up vote
0
down vote
favorite
The chess king moves one square in any direction (horizontally, vertically, or diagonally). The goal is to place as many king as possible on an r×c board subject to the following two conditions:
- There is at most one king in any cell of the board.
- Each king has at least one possible move into a free cell on the board.
I tried to solve it by placing the kings on the corners of the chess board and adding them with the squares it will occupy in the middle of the board using alternating pattern based on the floor of the number of kings placed into the remaining rows and the number of remaining columns they can be kept.
I have taken into account that for a particular row and column the transpose of the chessboard will also give the same max number of kings.
However i am getting wrong answer for some cases.
Please let me know if my above approach is correct or is there any generalized formula which can be derived from the above?
combinatorics contest-math recreational-mathematics chessboard
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The chess king moves one square in any direction (horizontally, vertically, or diagonally). The goal is to place as many king as possible on an r×c board subject to the following two conditions:
- There is at most one king in any cell of the board.
- Each king has at least one possible move into a free cell on the board.
I tried to solve it by placing the kings on the corners of the chess board and adding them with the squares it will occupy in the middle of the board using alternating pattern based on the floor of the number of kings placed into the remaining rows and the number of remaining columns they can be kept.
I have taken into account that for a particular row and column the transpose of the chessboard will also give the same max number of kings.
However i am getting wrong answer for some cases.
Please let me know if my above approach is correct or is there any generalized formula which can be derived from the above?
combinatorics contest-math recreational-mathematics chessboard
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
The chess king moves one square in any direction (horizontally, vertically, or diagonally). The goal is to place as many king as possible on an r×c board subject to the following two conditions:
- There is at most one king in any cell of the board.
- Each king has at least one possible move into a free cell on the board.
I tried to solve it by placing the kings on the corners of the chess board and adding them with the squares it will occupy in the middle of the board using alternating pattern based on the floor of the number of kings placed into the remaining rows and the number of remaining columns they can be kept.
I have taken into account that for a particular row and column the transpose of the chessboard will also give the same max number of kings.
However i am getting wrong answer for some cases.
Please let me know if my above approach is correct or is there any generalized formula which can be derived from the above?
combinatorics contest-math recreational-mathematics chessboard
combinatorics contest-math recreational-mathematics chessboard
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
asked Dec 4 at 19:19
Sumeet ten Doeschate
31
31
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
If the number of rows and columns are multiples of $3$, you can break the board into $3 times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 bmod 3$. You can't for $1 bmod 3$ because you lose some of the central squares. Here are my best shots for $12 times 9$ and $10 times 7$. Kings are in the red cells.
answered Dec 4 at 19:33
Ross Millikan
290k23195368
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
add a comment |
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: "69"
};
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',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3026006%2fmaximum-number-of-kings-on-the-chessboard-subject-to-some-rules%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
up vote
0
down vote
accepted
If the number of rows and columns are multiples of $3$, you can break the board into $3 times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 bmod 3$. You can't for $1 bmod 3$ because you lose some of the central squares. Here are my best shots for $12 times 9$ and $10 times 7$. Kings are in the red cells.
answered Dec 4 at 19:33
Ross Millikan
290k23195368
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
add a comment |
up vote
0
down vote
accepted
If the number of rows and columns are multiples of $3$, you can break the board into $3 times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 bmod 3$. You can't for $1 bmod 3$ because you lose some of the central squares. Here are my best shots for $12 times 9$ and $10 times 7$. Kings are in the red cells.
answered Dec 4 at 19:33
Ross Millikan
290k23195368
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
If the number of rows and columns are multiples of $3$, you can break the board into $3 times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 bmod 3$. You can't for $1 bmod 3$ because you lose some of the central squares. Here are my best shots for $12 times 9$ and $10 times 7$. Kings are in the red cells.
answered Dec 4 at 19:33
Ross Millikan
290k23195368
If the number of rows and columns are multiples of $3$, you can break the board into $3 times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 bmod 3$. You can't for $1 bmod 3$ because you lose some of the central squares. Here are my best shots for $12 times 9$ and $10 times 7$. Kings are in the red cells.
answered Dec 4 at 19:33
Ross Millikan
290k23195368
answered Dec 4 at 19:33
Ross Millikan
290k23195368
answered Dec 4 at 19:33
Ross Millikan
290k23195368
answered Dec 4 at 19:33
Ross Millikan
290k23195368
290k23195368
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
add a comment |
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Thanks but can there be a generalized representation for the above?
– Sumeet ten Doeschate
Dec 4 at 20:06
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Yes, the number of blanks in a column of length $n$ that has blanks is $lceil frac n3 rceil$, so the total number of blanks in $m times n$ is $lceil frac m3 rceil cdot lceil frac n3 rceil$
– Ross Millikan
Dec 4 at 20:21
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
Thanks the problem is solved by the above formula with m and n not equal to 3
– Sumeet ten Doeschate
Dec 4 at 20:40
add a comment |
Thanks for contributing an answer to Mathematics 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3026006%2fmaximum-number-of-kings-on-the-chessboard-subject-to-some-rules%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
