How to make any natural numbers (placed in the chessboard cells) divisible by 10 by using the given tools...
$begingroup$
The original condition is:
In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a chain of such operations that will make all numbers in all cells of the board divisible by 10? (The problem is taken from the book https://mirtitles.org/2013/01/01/combinatorial-mathematics-vilenkin/ by author https://en.wikipedia.org/wiki/Naum_Ya._Vilenkin)
combinatorics combinations combinatorial-game-theory combinatorial-proofs
asked Jan 10 at 5:02
MelinaMelina
83
$endgroup$
closed as off-topic by Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra Jan 10 at 9:55
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
The original condition is:
In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a chain of such operations that will make all numbers in all cells of the board divisible by 10? (The problem is taken from the book https://mirtitles.org/2013/01/01/combinatorial-mathematics-vilenkin/ by author https://en.wikipedia.org/wiki/Naum_Ya._Vilenkin)
combinatorics combinations combinatorial-game-theory combinatorial-proofs
asked Jan 10 at 5:02
MelinaMelina
83
$endgroup$
closed as off-topic by Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra Jan 10 at 9:55
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Can any naturals be placed in starting setup? Do they need to be distinct for different squares? Or even more, are they the numbers from $1$ to $64$?
$endgroup$
– coffeemath
Jan 10 at 5:27
1
$begingroup$
There is nothing about numbers being distinct or from 1 to 64. Just any natural numbers.
$endgroup$
– Melina
Jan 10 at 5:37
add a comment |
$begingroup$
The original condition is:
In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a chain of such operations that will make all numbers in all cells of the board divisible by 10? (The problem is taken from the book https://mirtitles.org/2013/01/01/combinatorial-mathematics-vilenkin/ by author https://en.wikipedia.org/wiki/Naum_Ya._Vilenkin)
combinatorics combinations combinatorial-game-theory combinatorial-proofs
asked Jan 10 at 5:02
MelinaMelina
83
$endgroup$
The original condition is:
In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a chain of such operations that will make all numbers in all cells of the board divisible by 10? (The problem is taken from the book https://mirtitles.org/2013/01/01/combinatorial-mathematics-vilenkin/ by author https://en.wikipedia.org/wiki/Naum_Ya._Vilenkin)
combinatorics combinations combinatorial-game-theory combinatorial-proofs
combinatorics combinations combinatorial-game-theory combinatorial-proofs
asked Jan 10 at 5:02
MelinaMelina
83
asked Jan 10 at 5:02
MelinaMelina
83
asked Jan 10 at 5:02
MelinaMelina
83
asked Jan 10 at 5:02
MelinaMelina
83
asked Jan 10 at 5:02
MelinaMelina
83
83
closed as off-topic by Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra Jan 10 at 9:55
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra Jan 10 at 9:55
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, mrtaurho, Abcd, Cesareo, Riccardo.Alestra
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Can any naturals be placed in starting setup? Do they need to be distinct for different squares? Or even more, are they the numbers from $1$ to $64$?
$endgroup$
– coffeemath
Jan 10 at 5:27
1
$begingroup$
There is nothing about numbers being distinct or from 1 to 64. Just any natural numbers.
$endgroup$
– Melina
Jan 10 at 5:37
add a comment |
$begingroup$
Can any naturals be placed in starting setup? Do they need to be distinct for different squares? Or even more, are they the numbers from $1$ to $64$?
$endgroup$
– coffeemath
Jan 10 at 5:27
1
$begingroup$
There is nothing about numbers being distinct or from 1 to 64. Just any natural numbers.
$endgroup$
– Melina
Jan 10 at 5:37
$begingroup$
Can any naturals be placed in starting setup? Do they need to be distinct for different squares? Or even more, are they the numbers from $1$ to $64$?
$endgroup$
– coffeemath
Jan 10 at 5:27
$begingroup$
Can any naturals be placed in starting setup? Do they need to be distinct for different squares? Or even more, are they the numbers from $1$ to $64$?
$endgroup$
– coffeemath
Jan 10 at 5:27
1
1
$begingroup$
There is nothing about numbers being distinct or from 1 to 64. Just any natural numbers.
$endgroup$
– Melina
Jan 10 at 5:37
$begingroup$
There is nothing about numbers being distinct or from 1 to 64. Just any natural numbers.
$endgroup$
– Melina
Jan 10 at 5:37
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Unfortunately I don't have enough reputation points to comment, so I guess I'll have to make it as an answer.
Anyway, observe that it is sufficient to use the mod-10 integers to denote a board position and to count how many times you added a 1 to a 3x3 or 4x4 sub-board, and observe that the order of the adding moves has no overall effect.
If we identify each solution of a board position with a $5^2+6^2=61$ tuplet of mod-10 integers corresponding to how many times we added a 1 to each of the 61 3x3 or 4x4 sub-boards, we find that in fact there are $10^{61}$ possible solutions in total.
But observe that one solution can only correspond to at most one board position, thus there are at most $10^{61}$ solvable board positions in total. However as there are $10^{64}$ possible board positions, we may conclude that not all of them are solvable.
answered Jan 10 at 6:05
Edward H.Edward H.
1739
$endgroup$
add a comment |
$begingroup$
Are the 3x3 and 4x4 squares allowed to overlap the edges of the board?
If no: I'll let another user answer this one.
If yes: Then it is possible to make all numbers divisible by 10. Start at the bottom left cell of the board. Add ones until it is divisible by 10 using a 3x3 square whose bottom left corner coincides with this cell. Next do the same thing one cell to the right. Again, this cell coincides to the bottom left corner of the 3x3 square. Complete the entire bottom row like this. Then do the next row up in the exact same way. Do all the rows like this.
This strategy works because once we have done each cell, we don't ever touch it again. But it requires some of our squares to extend off the edge of the chess board.
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
$endgroup$
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Unfortunately I don't have enough reputation points to comment, so I guess I'll have to make it as an answer.
Anyway, observe that it is sufficient to use the mod-10 integers to denote a board position and to count how many times you added a 1 to a 3x3 or 4x4 sub-board, and observe that the order of the adding moves has no overall effect.
If we identify each solution of a board position with a $5^2+6^2=61$ tuplet of mod-10 integers corresponding to how many times we added a 1 to each of the 61 3x3 or 4x4 sub-boards, we find that in fact there are $10^{61}$ possible solutions in total.
But observe that one solution can only correspond to at most one board position, thus there are at most $10^{61}$ solvable board positions in total. However as there are $10^{64}$ possible board positions, we may conclude that not all of them are solvable.
answered Jan 10 at 6:05
Edward H.Edward H.
1739
$endgroup$
add a comment |
$begingroup$
Unfortunately I don't have enough reputation points to comment, so I guess I'll have to make it as an answer.
Anyway, observe that it is sufficient to use the mod-10 integers to denote a board position and to count how many times you added a 1 to a 3x3 or 4x4 sub-board, and observe that the order of the adding moves has no overall effect.
If we identify each solution of a board position with a $5^2+6^2=61$ tuplet of mod-10 integers corresponding to how many times we added a 1 to each of the 61 3x3 or 4x4 sub-boards, we find that in fact there are $10^{61}$ possible solutions in total.
But observe that one solution can only correspond to at most one board position, thus there are at most $10^{61}$ solvable board positions in total. However as there are $10^{64}$ possible board positions, we may conclude that not all of them are solvable.
answered Jan 10 at 6:05
Edward H.Edward H.
1739
$endgroup$
add a comment |
$begingroup$
Unfortunately I don't have enough reputation points to comment, so I guess I'll have to make it as an answer.
Anyway, observe that it is sufficient to use the mod-10 integers to denote a board position and to count how many times you added a 1 to a 3x3 or 4x4 sub-board, and observe that the order of the adding moves has no overall effect.
If we identify each solution of a board position with a $5^2+6^2=61$ tuplet of mod-10 integers corresponding to how many times we added a 1 to each of the 61 3x3 or 4x4 sub-boards, we find that in fact there are $10^{61}$ possible solutions in total.
But observe that one solution can only correspond to at most one board position, thus there are at most $10^{61}$ solvable board positions in total. However as there are $10^{64}$ possible board positions, we may conclude that not all of them are solvable.
answered Jan 10 at 6:05
Edward H.Edward H.
1739
$endgroup$
Unfortunately I don't have enough reputation points to comment, so I guess I'll have to make it as an answer.
Anyway, observe that it is sufficient to use the mod-10 integers to denote a board position and to count how many times you added a 1 to a 3x3 or 4x4 sub-board, and observe that the order of the adding moves has no overall effect.
If we identify each solution of a board position with a $5^2+6^2=61$ tuplet of mod-10 integers corresponding to how many times we added a 1 to each of the 61 3x3 or 4x4 sub-boards, we find that in fact there are $10^{61}$ possible solutions in total.
But observe that one solution can only correspond to at most one board position, thus there are at most $10^{61}$ solvable board positions in total. However as there are $10^{64}$ possible board positions, we may conclude that not all of them are solvable.
answered Jan 10 at 6:05
Edward H.Edward H.
1739
edited Jan 10 at 6:14
answered Jan 10 at 6:05
Edward H.Edward H.
1739
answered Jan 10 at 6:05
Edward H.Edward H.
1739
answered Jan 10 at 6:05
Edward H.Edward H.
1739
1739
add a comment |
add a comment |
$begingroup$
Are the 3x3 and 4x4 squares allowed to overlap the edges of the board?
If no: I'll let another user answer this one.
If yes: Then it is possible to make all numbers divisible by 10. Start at the bottom left cell of the board. Add ones until it is divisible by 10 using a 3x3 square whose bottom left corner coincides with this cell. Next do the same thing one cell to the right. Again, this cell coincides to the bottom left corner of the 3x3 square. Complete the entire bottom row like this. Then do the next row up in the exact same way. Do all the rows like this.
This strategy works because once we have done each cell, we don't ever touch it again. But it requires some of our squares to extend off the edge of the chess board.
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
$endgroup$
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
add a comment |
$begingroup$
Are the 3x3 and 4x4 squares allowed to overlap the edges of the board?
If no: I'll let another user answer this one.
If yes: Then it is possible to make all numbers divisible by 10. Start at the bottom left cell of the board. Add ones until it is divisible by 10 using a 3x3 square whose bottom left corner coincides with this cell. Next do the same thing one cell to the right. Again, this cell coincides to the bottom left corner of the 3x3 square. Complete the entire bottom row like this. Then do the next row up in the exact same way. Do all the rows like this.
This strategy works because once we have done each cell, we don't ever touch it again. But it requires some of our squares to extend off the edge of the chess board.
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
$endgroup$
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
add a comment |
$begingroup$
Are the 3x3 and 4x4 squares allowed to overlap the edges of the board?
If no: I'll let another user answer this one.
If yes: Then it is possible to make all numbers divisible by 10. Start at the bottom left cell of the board. Add ones until it is divisible by 10 using a 3x3 square whose bottom left corner coincides with this cell. Next do the same thing one cell to the right. Again, this cell coincides to the bottom left corner of the 3x3 square. Complete the entire bottom row like this. Then do the next row up in the exact same way. Do all the rows like this.
This strategy works because once we have done each cell, we don't ever touch it again. But it requires some of our squares to extend off the edge of the chess board.
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
$endgroup$
Are the 3x3 and 4x4 squares allowed to overlap the edges of the board?
If no: I'll let another user answer this one.
If yes: Then it is possible to make all numbers divisible by 10. Start at the bottom left cell of the board. Add ones until it is divisible by 10 using a 3x3 square whose bottom left corner coincides with this cell. Next do the same thing one cell to the right. Again, this cell coincides to the bottom left corner of the 3x3 square. Complete the entire bottom row like this. Then do the next row up in the exact same way. Do all the rows like this.
This strategy works because once we have done each cell, we don't ever touch it again. But it requires some of our squares to extend off the edge of the chess board.
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
answered Jan 10 at 5:52
Ricky TensorRicky Tensor
58819
58819
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
add a comment |
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
$begingroup$
Yes,the squares are allowed to overlap the edges of the chessboard. Thank you:))
$endgroup$
– Melina
Jan 10 at 11:48
add a comment |
$begingroup$
Can any naturals be placed in starting setup? Do they need to be distinct for different squares? Or even more, are they the numbers from $1$ to $64$?
$endgroup$
– coffeemath
Jan 10 at 5:27
1
$begingroup$
There is nothing about numbers being distinct or from 1 to 64. Just any natural numbers.
$endgroup$
– Melina
Jan 10 at 5:37