Waste less time on Facebook — follow Brilliant.
×

===Open Problem #1=== (1st Update Post)

I'm going to start doing updates of our project weekly. This will allow me to summarize what we've learned so far and suggest which avenues of research are most useful. Also, please put new general discussion as responses to this post, rather than the first one; that way the discussion thread doesn't get too long.


To reiterate, here is our open question. There is currently no known answer in the finite case.

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? Also, 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.


We've had a great start to the group! Some highlights include:

Novak Radivojević pointing out right away there was a solution on an infinite board. He wrote a problem to go with this insight that we've featured as a Problem of the Week.

Lots of great discussion from Mike Harding, João Areias, Marcus Luebke, Stefan Van der Waal, and others.

A long post by Stefan Van der Waal springing from the discussion which explores the problem at the edge of the board.

Please note the new wiki page dedicated to this problem. Feel free to add results there!

Based on the discussions, these seem the most promising areas of study:

A complete description of all possible king configurations on a finite board. The current data is on the wiki here.

Studying restrictions to configurations when they are on the side of the board or in the corner of the board.

We could use a more systematic description of the infinite cases. Is there a specific way to describe all infinite board solutions? Does anything from an infinite board solution suggest why the problem might not be solvable on a finite board?

This may not be the complete list though - feel free to go in an entirely different direction!

One question people might be wondering is: how long will this open question last for before we go on to another one? I'm not sure on the timing yet (this is the first time we've done this!) but I expect we will likely switch to a new question every month. You are very welcome to post in the thread suggesting open problems.

Also note: I have turned off moderation for new questions / posts - I haven't seen any issues, so any new posts you make to the feed will now show up immediately.

Note by Jason Dyer
3 weeks, 4 days ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

Sort by:

Top Newest

I made a Program for 5x5 In Prolog that given the first column which is constructed by variations with repetitions of 3 elements (king (r), knight (c) and empty cell (v)) it will build the rest of the board by checking how many chess pieces are needed for each piece to satisfy the conditions and then putting them into the board in a way there are no conflicts with each other until completing the board, pieces can only be put at right and down so that the verification is easier - if pieces could have been up and left backtracking would have given them since the relation between two pieces is a two ways relation.

Imagine a robotic arm in front a chessboard putting pieces in it.

I always start from the first column because the chessboarb is invariable to symmetries and rotations.

I did 5x5 to 10x10 chessboard, and there was no results, If someone wants to go further, only tweaking a few numbers is needed.

Here is a simpler version, with only kings, that I ran as a test, It gave all the combinations for kings being able to attack 2 other kings. Kings only test, In the case of a 5x5 board for kings only, example

edit: i forgot something in the program and completed it.

edit2: just tried for 15*15 with the program, the execution takes hours, this isn't doable :(

Ahmed Amrani - 2 weeks, 1 day ago

Log in to reply

Can you add to the problem statement that there must be at least 1 king so that there isn't a trivial solution?

Alex Li - 2 weeks, 5 days ago

Log in to reply

An empty board does not constitute "a configuration of kings and knights". (And you can't have just knights, because each knight needs to attack 2 kings in addition to attack 2 knights.)

Jason Dyer Staff - 2 weeks, 5 days ago

Log in to reply

Corner problem: We were trying to prove that A4 and D1 were unable to be filled. We have one case that we can't disprove yet: https://imgur.com/a/xHeuF Link wasn't mine originally. It was Marcus's.

Mike Harding - 3 weeks, 3 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...