===Open Problem #1===

This is an open question. There is currently no known answer.

On a chessboard of any size, is there a configuration of kings and knights such that each king attacks exactly 2 kings and 2 knights, and each knight attacks exactly 2 kings and 2 knights?

(Sub-problem -- if it is possible, what's the smallest board needed?)

WIKI PAGE DEDICATED TO THE PROBLEM; WE CAN COLLECT OUR DATA HERE

Source.

Details: Kings can attack any adjacent square, including diagonally. Knights move in an L shape as shown below.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

If we assume the chessboard is infinite, it could be done this way... I guess...

Novak Radivojević - 3 years, 7 months ago

That's extremely neat! This is a legitimate discovery (while I think the people tackling the other problem were all restricting to the finite case, the infinite case is still quite interesting, and I'm curious if it could be used to form a finite case).

I don't suppose you could post a problem to the group that asks the above question "is it possible on an infinite grid?" yes/no (with the answer yes) and then post this answer?

https://brilliant.org/groups/open-problems-group/

Put "Related to Open Problem #1" somewhere in the text of the title.

Jason Dyer Staff - 3 years, 7 months ago

Thanks! I'll post the problem, and I think there might be even more such patterns which we can follow to make other infinite solutions.

Novak Radivojević - 3 years, 7 months ago

@Novak Radivojević – Yes, and by having it as a problem, we can collect all the infinite solutions in one place.

Jason Dyer Staff - 3 years, 7 months ago

If we assume some smallest, finite board exists, we know the following about that board: 1. The board will have an edge on the left, on the top, on the right, and on the bottom 2. To guarantee the board can’t get shrunken, the board needs at least one piece on each edge

With those two ideas I started looking at a corner. I assumed a piece is put in the corner and kept extrapolating until I arrived at a contradiction. All of my work is over here: https://docs.google.com/document/d/1fEALESsS72xeT1e8YamxNqrrOEg6qAn-3mTHk9Rgxnk/edit?usp=sharing

Assuming I made no mistakes, the conclusion I reached was: There are no pieces on the squares A1, A2, A3, B1, and C1.

Stefan van der Waal - 3 years, 7 months ago

If that's true, then you can't place a king on B2.

Novak Radivojević - 3 years, 7 months ago

Can you prove your point after #3 a bit more rigorously? "Since the K in A2 has the same going on as the K on B1, A3 should also be a K and B3 should be a N." It feels like this assumes that any solution would be symmetric. I might be missing something, but as a reader I'm going to question it unless proven otherwise.

Marcus Luebke - 3 years, 7 months ago

Now I look back at what I wrote, I realize that step made sense in my head, but I worded it awfully (and later on I made a leap based on a similar argument that was about 5 times as big). I just added a bit of clarification, which hopefully makes it a bit more clear, even though I'm still not sure if it's rigorous enough.

Stefan van der Waal - 3 years, 7 months ago

@Stefan van der Waal – Another way to prove that particular point, A3 and B3 need to be 1K and 1N in order for A2 to work. If we put N(Knight) we have a similar case to #2, which does not work. Thus, K must be on A3 andN must be on B3. Hope this helped.

Mike Harding - 3 years, 7 months ago

Just proved (visually) that A4 and D1 cannot have knights on them, and therefore B2 is empty. (Assuming there are no pieces on the squares A1, A2, A3, B1, and C1) See https://docs.google.com/spreadsheets/d/1yuFJck60D0HHRelXdyzsC79sqiBwOUpBzIryzvpVZ3Y/edit#gid=1329517548

Marcus Luebke - 3 years, 7 months ago

Is there a way this could be summarized as a posted question to the group that you then answer yourself, the same way we did with an infinite grid?

Jason Dyer Staff - 3 years, 7 months ago

@Jason Dyer – Was that aimed at me or Marcus? If it was aimed at me, I'll see what I can do to summarize my work, and turn it into a question.

Stefan van der Waal - 3 years, 7 months ago

@Stefan van der Waal – @Stefan van der Waal That was to you. Thanks!

Jason Dyer Staff - 3 years, 7 months ago

However, I wasn't able to exclude kings from A4 and D1, and upon further consideration I realized that B2 is not necessarily empty. Sorry.

Marcus Luebke - 3 years, 7 months ago

@Marcus Luebke – I proved that B2 must be empty. I don't have fancy google docs, so if you want to add this to your doc, go ahead, just credit me. :)

Proof that B2 is empty: I am still assuming that A1, A2, A3, B1, and C1 are all empty and that A4 and D1 are not knights. Assume that B2 is not empty. It cannot be a king. This it must be a knight. Thus A4, C4, D1, D3 must be filled, with A4 and D1 being kings, by assumption. However, that forces A5, B3, B4, B5 to be filled. Note B4 is touching five different squares that must be filled. Thus it is not a king. Say it is a knight, then B3 is a king, which is touching more than five squares that must be filled. C! Thus B2 must be empty.

Mike Harding - 3 years, 7 months ago

@Mike Harding – Proof that A1 and D4 must be empty:

 Assume that A1, A2, A3, B1, B2, and C1 must all be empty and A4 and D1 are not knights. Assume that they must be kings. Therefore A5, B3, B4, B5, C2, D2, E1, E2, must all be filled. 

 Observe the D2 square. Assume it is a king. It touches 4 places that must be filled. Thus C3, D3, and E3 must all be empty. Thus C2, which must be filled, cannot be a king, as it only touches 3 filled squares. Thus it must be a knight. This knight attacks A1, A3, B4, D4, E1, E3, so four of these squares must be filled. However, by assumption, A1 and A3 must be empty and we proved that E3 must be empty. C!

 Thus the D2 square must be a knight. Say B3 is a king. This forces C3 to be filled and C4 to be empty. Assume that C3 is a king, then it touches 3 knights. C! Thus C3 must be a knight. This implies that D5 and E4 must be empty. Observe the Knight on D2. It attacks 3 non-empty squares. C! Thus C3 must be empty. C! 

 Thus B3 must be a knight. This forces D4 and C5 to be filled. Note that B4 now touches five different squares that must he filled. Therefore, B4 must be a knight. Therefore, A5 and B5 must be kings. Since C5 must be filled, it is a knight, forcing A6, B6, and C6 to be empty. However, the king on A5 is only touching one knight. C! Therefore B3 must be empty. C! Thus A4 is not a king. Similar logic shows that D1 cannot be a king. QED.

Mike Harding - 3 years, 7 months ago

@Mike Harding – There is one situation that works if B3 is a king (that I haven't been able to disprove). Consider C3 is empty and C4 is not. https://imgur.com/a/xHeuF However, you are right that B3 cannot be a knight.

Marcus Luebke - 3 years, 7 months ago

@Marcus Luebke – Found a contradiction. Now, I have to work back through the grid of letters that I have to figure out how I can write it out and explain it. That will likely be tomorrow.

Mike Harding - 3 years, 7 months ago

@Mike Harding – Can you elaborate why you're so sure A4 and D1 can't be knights? Also, can you elaborate why near the end B4 can't have a knight?

Stefan van der Waal - 3 years, 7 months ago

@Stefan van der Waal – A4 and D1 - Marcus Proved it above, visually. B4- Fixed.

Mike Harding - 3 years, 7 months ago

@Mike Harding – Nice. I tried to prove it via brute force, but yours was much more elegant. :) I gave an explanation with credit to you.

Marcus Luebke - 3 years, 7 months ago

Advancing from that list of facts know about that board 3. Approaching each corner must be a piece who is the last (or possibly only in the case of a knight) piece on that edge. Given 3 and Stefan's Edge positions on the wiki page we have 7 cases for that last piece: King 7 with the black pawn continued down the left edge. 2 Variants of Knight 1, 2 of Knight 2, a Knight 3 and a Knight 4. If all these can be disproved, no finite board exists. King 8 and 16 are effectively specific variants of the knight positions, for last piece purposes, and Kings 1, 4, 12, 13 and 15 have been proven impossible by Stefan already. King 7 Knight 1a Knight 1b Knight 2a Knight 2b Knight 3 Knight 4

Given I've not weighed in on this before I'd like some feedback.

Theo Elliott - 3 years, 1 month ago

Could you add this to the wiki?

https://brilliant.org/wiki/open-problems-group-open-problem-1/

Jason Dyer Staff - 3 years, 1 month ago

@Jason Dyer – Added after the corner section (Slightly reworded for clarity)

Theo Elliott - 3 years, 1 month ago

Ok, here is my shoot on solving the following related problem. What are the configurations where all kings are attacking 2 other kings? We know that we can divide the board into 2x2 boards. All the possible configurations for Kings on 2x2 boards are shown below, ignoring rotations and reflections:

Now, we can discard the configuration 5 since all the kings are attacking 3 other kings. Configuration 4 is already complete by itself, all the kings are attacking 2 other kings, it is one solution as well as combining it with other solutions such that no king on this configuration attacks a king on the other solution is also a solution. Configuration 1 will only form a solution if connected with the others such that the king is adjacent to another king, which can be broken down on one of the other configurations as shown in the following image:

Configuration 1

The other two configurations, 2 and 3, are a bit more interesting. On both of them, there are 2 kings that each needs to attack 1 more king. One can concatenate another of those pieces to make it attack another of those kings, this will satisfy the conditions to one of the previous kings and one of the added kings, leaving us in the same situation as before. The only way to satisfy the conditions for all kings one a finite board then is if the added piece attacks the previous pieces on 2 different points closing a loop like the images shown here :

One condition I found is that for any 2x2 grid on your pattern, the configuration 4 cannot appear on the loop, for example, loop 1 is invalid.

loop

I don't know if my proof is rigorous enough, sorry, I'm not a mathematician but those are what I found, hopefully, it helps someone come up with a more rigorous proof. Here another more complicated pattern I created just following these rules.

pattern

João Areias - 3 years, 7 months ago

I don't think that's a proof, but I don't think that you're trying to prove anything. You're just exploring the question and came to some cool conclusions.

Mike Harding - 3 years, 7 months ago

Oh well, I was trying to find the ways one can find the patterns that where the kings attack only 2 other kings, hope it's something useful the conclusions I got to.

João Areias - 3 years, 7 months ago

I have put this data on a new wiki page dedicated the problem, which we can use to store such things: https://brilliant.org/wiki/open-problems-group-open-problem-1/

Jason Dyer Staff - 3 years, 7 months ago

If there were a solution to this, would it have more kings than knights, or more knights than kings?

Mike Harding - 3 years, 7 months ago

Good question! Maybe you can work on that? (They're certainly not necessarily equal - the kings-and-rooks case, for instance, is on a 4 by 4 board with 4 rooks and 8 kings.)

Jason Dyer Staff - 3 years, 7 months ago

Which one do you think is needed more? (Just to give me a place to start working.)

Mike Harding - 3 years, 7 months ago

@Mike Harding – I think something like these three questions:

If there were more kings than knights, what conditions must hold?

If there were more knights than kings, what conditions must hold?

If the number of kings and knights were equal, what conditions must hold?

Jason Dyer Staff - 3 years, 7 months ago

There would probably be more knights, as they can be more spread out. However, this is simply a conjecture.

Marcus Luebke - 3 years, 7 months ago

I'm inclined to think so too with about 80-20 confidence. The problem is to prove it!

Jason Dyer Staff - 3 years, 8 months ago

I think the answer is no.

Each king attacks 2 kings and 2 knights.
Each knight attacks exactly 2 kings and 2 knights.

Considering a $4 \times 4$ chessboard, where it doesn't satisfies the condition.

In other words, it could be possible for a certain number of knights and kings. But not possible for each knights and kings.

Munem Shahriar - 3 years, 8 months ago

This looks like a good start, but it doesn't exhaustively cover every single configuration of kings and knights. To begin with, you might want to think of what configurations with the kings will meet "every king must attack two other kings" condition before adding on the knights.

Jason Dyer Staff - 3 years, 8 months ago

@Jason Dyer – What is maximum size of configuration? $(\text{e.g} ~ 2 \times 4, 3 \times 2)$

Munem Shahriar - 3 years, 8 months ago

@Munem Shahriar – From the very start it mentions: On a chessboard of any size

Admittedly, one approach that might get some traction is to start with specific board sizes (that is, if you can eliminate 4x4 very thoroughly, then 5x5, that might be useful and suggest a general method).

Jason Dyer Staff - 3 years, 8 months ago

How about if we start with a much simplified version of the problem here?

And then attempt to solve the 4x4 case, 5x5, case, and work toward the general nxn solution (for just 2 kings)?

Geoff Pilling - 3 years, 7 months ago

Maybe this can help a little. 2x2 3x3 4x3 5x5 6x5 6x6 8x7

João Areias - 3 years, 7 months ago

Reducing down to the just-kings case is a great way to start. Will all king configurations look like this, though? (Is it possible to make a "winding snake" with a larger setup, that is? And if not, can you prove it?)

Jason Dyer Staff - 3 years, 7 months ago

Found a few more patterns with the kings, but I'm just getting a grasp of the problem right now. I'm not sure yet, but I think that if the king is not on the 2x2 pattern I showed, it will have to form a loop, I'll try to prove that and get from there.

5x3 6x3 7x3 8x3

João Areias - 3 years, 7 months ago

isn't 4x4 possible with kings on all edges

Mike Harding - 3 years, 7 months ago

True, like this right? 4x4

João Areias - 3 years, 7 months ago

@João Areias – yep.

Mike Harding - 3 years, 7 months ago

So, I found out that there are 21 different arrangement of pieces or lack thereof on a two by two grid. This is where I go before I call it a night.

Mike Harding - 3 years, 7 months ago

I am going to assume that we are overlooking the trivial case with 0 kings and 0 knight, right?

Mike Harding - 3 years, 7 months ago

Can we also reword the problem to exclude infinite cases? Otherwise, we're done.

Mike Harding - 3 years, 7 months ago

We aren't, because: (Sub-problem -- if it is possible, what's the smallest board needed?)

Jason Dyer Staff - 3 years, 7 months ago

I have found 2 more patterns for the infinite chessboard and added them to the wiki.

As for the finite cases, some restrictions could maybe help. Since all the pieces must attack exactly 4 out of 8 tiles we can conclude:

A king can never sit in a corner of the board
A knight can never sit in corners and in tiles that share a common edge with any of the corner tiles.

Having this in mind, we can see that there is no arrangement of kings and knights on a 4x4 board.

Novak Radivojević - 3 years, 7 months ago

3by3 board (A3+B3+B1+C1)"knights. "(A1+A2+C2+C3)"kings.

Mologic Starr - 3 years, 6 months ago

Looks like each knight is only attacking one other knight.

Jason Dyer Staff - 3 years, 6 months ago

Show where you're I'm confused because I see two knights attacking two knights.

Mologic Starr - 3 years, 6 months ago

@Mologic Starr – Each knight attacks both two kings and two knights.

That means if you have four knights, each of the four knights will attack 2 knights each, for a total of 8 knight-attacks.

Jason Dyer Staff - 3 years, 6 months ago

King on A1 touches only 1 Knight and 1 King. Each piece needs to attack two of each piece.

Mike Harding - 3 years, 6 months ago