Peaceable Queens - Numberphile
Вставка
- Опубліковано 27 тра 2024
- Neil Sloane discusses peaceable queens and chess. Check out Brilliant (get 20% off their premium service): brilliant.org/numberphile (sponsor)
More links & stuff in full description below ↓↓↓
Learn more at the OEIS entry (loads of links): oeis.org/A250000
References:
Ainley, Stephen. Mathematical Puzzles. London: G Bell & Sons, 1977.
Yukun Yao and Doron Zeilberger, Numerical and Symbolic Studies of the Peaceable Queens Problem, arxiv.org/abs/1902.05886
Other notable work by Michael De Vlieger, Benoit Jubin, Peter Karpov, Don Knuth, Rob Pratt, Bob Selcoe, Paul Tabatabai.
More Numberphile videos with Neil Sloane: bit.ly/Sloane_Numberphile
More chess-related videos: bit.ly/chess_numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from Math For America - www.mathforamerica.org/
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Наука та технологія
Maybe it's just me, but to me it sounds like if I went and talked to this guy he'd give me a quest.
I think that's a mid-Atlantic accent he has that creates that effect. I'd been thinking about the accent and wondering why he would naturally have that. Then I looked him up and found out he's British-American. Makes sense...
And it'd be an unsolved mathematical puzzle
He did. Complete this sequence. :)
You have to retrieve a 30×30 chessboard from the cave of 28 queens
I feel the exact same way lol
Wow! This is the founder of OEIS !! Thank you a lot!
I can't believe I've only just learned this now!
I know, I was like dang the OG himself.
with the voice like butta
I was looking at the books behind him and thought "huh, he has a whole row of books by the OEIS guy" -- only to later realise that I had been looking at the author himself :-)
Suddenly every numberphile video with him in makes sense. They're all about pointless sequences. There could be a "Sloane's sequence" on OEIS. Pick a number in every sequence on OEIS and call it a sequence known up to 250,000. It would be as suitably pointless as any.
0:06 I've been moving my queen wrong all this time!
how else you can move it , weirdo?
isn't it in FIDE rules 2019?
It's a difficult move to pull off and it's very risky . If your rating is over 2500 you can start thinking about doing flips with your queen, before that, I'd stick to sliding
@@TheLetterJ10 no
@@TheLetterJ10 he was joke too so you deserved the r/woosh lol
@@Sciencedoneright what
Wait HE'S the integer sequence database guy? I never knew!
Wow... Also kinda makes sense why he's friends with Don Knuth.
@@gpk6458 They even almost look the same.
Right? Just humblebrag about knowing Knuth. Like you aren't already a total badass.
@@sirdiealot7805 it's the T-shirts
Yes - it struck me to :) and it has been already founded in 1964? Has there been the VT100 or VT1 :) protocol to be able to access remote systems already? I remember his name from previous N-P videos but went to the description to make me sure i remember it correctly but did not found the name in the description :).... Numberphile... NP ? wow :)
Mathematicians just like to make up strange problems for fun, don't they?
We call that process 'mathematics'.
@@koseq7 And lots of times a mathematician found and solved a problem just for fun. On the other hand, an engineer has got a real life problem that could elegantly be solved with the mathematician's work. However, since this engineer has never heard of said work, he never thinks of using it.
They earned it
everything has an appliance
@@koseq7 Have any real life examples? I'd honestly like to hear, especially any parts about how they manage to get matched up.
Brady's gettin' all fancy with the graphics now. lol
I kinda prefer the watercolour ones
He took a class on computer graphics at Brilliant.
@@mattk8440 I like to mix it up
And now his videos are taking longer :/
@@andermium :) it's a shame I don't get a special icon / emoji or something
The way he explains it makes it way more interesting
lumberjack
Your observation made this video even more enjoyable for me
@@69Cil your expression of enjoyment made this more interesting
false.
Neil is just the best free time math professor. Fun, odd problems explained in a calm, collected yet confident voice. He's the David Attenborough of Mathematics.
No, he is the Neil Sloane of mathematics
I just love that, on top of this, OEIS A250001 was ‘randomly’ chosen as his overlapping-circles integer sequence that was recently covered
I also note that OEIS was already beyond A260000 when this video was being made.
??.
My immediate thought upon hearing this problem is knight moves. One knight move away is the closest opposite queens can be without attaching each other.
The difficulty there is as it grows. Remember same color can be adjacent no problem.
@@ZachGatesHere Yes, but interestingly the big clusters at the end there are a close resemblence to very big knight moves.
My immediate thought was Old Time Rock and Roll.
David Ryder do you mean old time rook and roll? lol
@@IwanttoliveinParis I think Sloane might be a Deadhead (like yourself perhaps). His t-shirts provide a clue.
This man has literally the most relaxing voice on Earth. I'm more interested in this than I've been in anything for years, and I'm falling asleep because of his voice.
6:12 you can simplify the problem by noticing that if the King was a Queen, only the spaces which that Queen can attack would threaten the King. So you just have to place the King somewhere that the number of squares that he threatens if he becomes a Queen is minimised i.e. in the corner of the board, where he threatens 21 squares and occupies another, leaving 42 squares free and safe. For a formula for the number of safe squares of an n x m grid where n is greater than or equal to m, consider that the King reduces the grid to dimensions (n-1) x (m-1) by removing the non-diagonal dangerous squares, and an extra m-1 squares because the diagonal removes one square from each of the remaining rows. This leaves n*m - n - 2m + 2 squares, which simplifies to (n-2) x (m-1), which agrees with the earlier answer of 42 Queens for an 8x8 board. In fact, placing the King anywhere on the shortest edge of the board (or anywhere on any edge when n=m) would yield this answer since moving the King along that side would reduce the number of dangerous squares 'below' the King by two and increase the number of dangerous squares 'above' the King by two, leaving the total unchanged (this is much easier to understand using a diagram).
I saw this as well, nice explanation
This was also my reasoning, though I suspected I was wrong and had missed something. Glad to see that was just paranoia.
I was taking a similar approach. However if you only consider square boards, you realise that the king in the corner leaves two triangular wedges with a length of n-2. This means the free spaces are 2*1/2*(n-2)((n-2)+1), and it reminded me of the visual derivation of the formula for triangular numbers.
I'm aware I'm not really adding much to the discussion, I just thought that connection was nice :)
@@loek5886I also have attempted to solve the problem, so I've decided to look at the comments in order to find out if I think correctly. It turns out I did. Really happy about it. 😃
@@andymcl92 that was actually my initial thought too! Great minds think alike I see ;)
Upper bound is n²/2. Where's my Fields medal?
Haha thanks for the insight lol
n²/2 = ⌊q⌋ ?
Holy shit he's actually wearing the same t-shirt as Knuth in the cut-away 0:40
Maybe Knuth is his Tony Clifton to his Andy Kaufman
either that or he is wearing a different but isomorphic t-shirt, at least for the top half of the front of both t-shirts.
Can anyone tell me what's the logo of this T-shirt?
Maybe these are conference-specific t-shirts, and Sloane wears it in the main video because of the memory value.
deepfake?
This is maths ASMR
Agreed lol😂
@@Sciencedoneright you again
I think my solution for the King and Lots of Queens puzzle is (n*n)-((n*3)-2) and by placing the king in one of the corners. Basically treat the king as a queen and minimize the amount of spaces it can move to in one turn. Then fill the rest with white queens. Looking into it a little further I think it'll work with the king anywhere touching the edges of the board.
For the final brilliant puzzle, the max is [(m*n) - 2m - n + 2] where m < n. With the king in the corner, take out each edge and the diagonal, and then add 2 for the overlap.
aka (m-1)(n-2).. always simplify :)
Why would that queen capture it was guarded by the pawn
Math.
We are mathematicians here, not GM :v
What if you have a chessboard of n*n tiles, and m different colors of queens?
I'm not sure what the problem is properly called but this is a known problem, above a certain number (4 I believe) all nxn chess boards can contain n queens without them attacking one another; having said that they are hard to find and it can be an enjoyable puzzle
@@JohnMcFee1 I can't find the problem. Reply if you remember how is it called.
@Alzblb Wikipedia calls it the n queens problem
@Winston Mcgee Except that wasn't the problem described; or more specifically, it's the problem described for the specific case m=n. The problem as described by the video is m=2; but what about the generalized case where m is between 2 and n?
And how about p dimensions?
"Chess Queens are a trained warrior. They are trained to attack."
*sees queen captured by other queen*
I love these kind of combinatorics. Very intuitive to a lay audience and equally mysterious to all.
I pronounce it "Twenty Eight" instead of "Twenty Eight"
Whoa man... that's rather rude don't you think?
@@Gimpy2K5 woosh
i thought it's twenty eight
@@therflashwoosh?
Two ten eight, in Chinese format.
6:25 It is easy to solve that problem. You can generalize it for a board m*n this way. If m>n, then the number of queens you can place down is n^2 - m - 2n - 2. If m=n then the number is n^2 - 3n - 2
I adore OEIS! Thank you for your work!
This is pretty neat timing, I just learned about the similar n-queens problem for my Algorithms class!
Great video, as always.
i love the sound design in this video
Real life plot twists: this random guy you recognise runs the OEIS
I'm also fairly certain his quest would be a puzzle solve, fellow person who thinks he sounds like a quest NPC
Maximum number of queens is 42 for Numberphile's problem at the end, obviously, with the black king in a corner. And what generalization do you want? If n
Wow this is another level of animation. Good job!
I love all the numberphilers, but I think I love Neil Sloan the most. He just has such evident love and appreciation for this stuff. And such a kind and generous demeanor.
I got my A250001 4 circles poster today and went to OEIS to look at A250000. Imagine my surprise when this is today's video!
I love Neil's vids. They define recreational math, lateral thinking, and are just plain interesting.
Kudos for the animation!
Question at the end:
42. You can rephrase the question to given a square on an 8 by 8 grid how many of the remaining 63 squares are not on the same row, column or diagonal and which starting square positions maximise this number?
There will always be 14 in the same row and column but the diagonals are variable. Anywhere on the edge will have 7 on the diagonal but moving away from the edge will increase this number keep the king on the edge. 63 - 7 - 7- 7 = 42.
This problem actually relates nicely to matter anti-matter pairs in crystalline structures
any links we could check out to learn more about that? sounds really interesting
@@gammazzz3894 I tried to send you a couple but they annihilated each other.
@@TheRealChristopherD damn and u just annihilated me
Speaking as "The Peaceable Kingdom," how can I not love this problem?
Now I have a Rush song stuck in my head
@@andrerenault Lol! 😂 I had forgotten about that!
(no relation)
Wonderful stuff!
This was an unusually beautiful presentation.
Thank you for the OEIS database
0:07 ..Qxb6?? blunder!
I spent the morning watching old Numberphile videos about chess. A few hours later this shows up in my subscriptions feed...
his studio room is utterly fabulous.
What a delightful video!
The book set on the back side of the interviewee is just perfect!
I just saw this problem the other day, it was the entry right before the overlapping circles entry :O
Beautiful problem, sounds like the kind which leads to awesome new theories with greater reaches than the problem itself
I think an interesting variation of this would include some 'range' term for the queens. That is to say, they can only attack an opposing queen if it is within 'k' squares. So on very large boards ( n >> k), what becomes the highest possible 'density' of queens per region? (spends the rest of the morning fiddling with paper and python....)
I read the comments before the video was finished to see if my answer (42) was right, and was amazed that everyone seemed to think it was only 28
Pretty sure it's 42 yeah. 64-8-7-7.
i also counted 42, just place king in corner and subtract 3 beams of 7 and 1 of his own tile, everything rest can be queen
@@manowartank8784 I think it's independent of where you put the king.
@@alephnull4044 It shouldn't be. The last sentence of the prompt is "You can place the king wherever you think is more profitable."
@@ArmadilloAl Oh sorry I mean independent given that he's one of the edges.
Peaceable Voice
The answer to the problem with the black king is 42 (as always).
View from the King's spot: which tiles can he be beaten from? - There's 7 horizontally and verticall each. The number of diagonal tiles he can be beaten from varies depending on his position, but is smallest when he is on the edge, then it's 7 diagonally as well. Finally, the tile of the King can not be inhabited by a queen. All other tiles can have a queen, giving us 64-7-7-2-1 = 42.
For a board of size nxn in general it's n²-3n-1 by the same method.
I collected the votes. I made my cantidate win. Luv this guy!!
More Neil Sloane videos please! Not only is here the founder of the OEIS, but he also has a lovely relaxing voice :)
I always wondered why the power settings on our AEG induction hob were 0,1,3,5,8,10,14.
But thanks to OEIS I now know that it's Sum_{k=1..n} floor(n/k)
So YOU run this online encyclopedia of integer Sequences?
Wow!
I simply love the site!
The combination of his voice with this music was almost eerie; I loved it! The problem described was also loads of fun.
Is there any way to find the song used in this video?
He runs the OEIS?!?! oh my gosh i had no idea I tell everyone about that site!!
Respect for Numberphile to show the one who hosts OEIS. 🙏🏼🙏🏼
i'd like to know why some arrangements don't follow the four clump distribution, and what, if anything, is special about these board sizes
king and a lot of queens my solution: we solve this problem by filling the entire board with queens except for the spaces that would attack the king, so how many spaces can attack the king? (this question is equivalent to: if a queen stood in the kings space, how many spaces would it be able to move to?)
well for an MxN board, there are M-1 vertically aligned spaces and N-1 horizontally aligned spaces to the kings space. the king should optimally be placed either in a corner or on the shorter edge, in both cases there would be exactly MIN(M,N) -1 diagonally aligned spaces to the kings space (from here we will assume that M>=N, this does not change the problem and lets us express MIN(M,N) as simply N) and finally a queen cannot be placed in the kings space, therefore, since an MxN board has M*N total spaces, the general solution is: M*N-(M-1)-(N-1)-(N-1)-1 = M*N-M+1-2(N-1)-1 =
M*(N-1)-2(N-1) = (M-2)*(N-1)
Any video featuring Neil Sloane is always a pleasure to watch.
The moment you bring out a chess board for a problem, the answer before you even start speaking is always going to involve the Knight move, just because it's the only movement no other piece can replicate in one turn.
superb - thanks
The animation is great in this episode
These are super basic assumptions I created to find some permutations..although these are 100% wonky
1. We require for n amounts of Queens to be placed on the board, but there must n amounts of spaces left over.
2. We can cut down the brute force by saying if(there is a queen on each row){go onto the next sequence}
3. Of course, we will save that sequence in case it becomes a Parent sequence to sequences with higher N's. For instance, we might use N = 24 for an 18x18. But after we compute that, we go onto N=25 and happen to find a sequence that matches a sequence in N=24.
4. We can cut it down even more by saying if(there is a queen on each column){go onto next sequence}
5. We can cut it down even more by saying if(there is a queen on a whole diagonal){go onto next sequence}; although, we can generalize this even more by saying if(there is a queen on half or greater than half of the BOTH diagonals){go onto next sequence}
6. We can cut it down even more by saying if(queens >= area of chessboard){Next chessboard size}
Literally any chess piece: *exists
Queen: "Get nae-nae'd"
Neil is a true treasure!
There is an error at 2:50. 6x6 is supposed to be 5, not 6.
Re: the problem from Brilliant posed at the end
To solve the problem, you must flip your thinking around. Instead of asking how many queens can you place to not check an opposing king, ask "where can I place a king such that the fewest possible spaces exist from which a queen can attack it?" If I'm not mistaken, the answer (for a square board, at any rate) works out to be "anywhere along the border of the board", where the number of spaces from which the king is vulnerable equals *3n - 2* , where n is the length of one side of the board. This would let you place *n^2 - 3n + 2* queens.
P.S.
A bonus challenge, for those interested. This equation should be provable through induction. However, even though this equation is true starting from n=1, you will likely want to use n=3 as your base case. Don't hurt yourself.
Bonus puzzle solution:
The top-left corner (works for any corner) can be attacked from any queens in the colunm, row, and diagonal of the king, and placing the queens at the other spots leaves 1 king, 21 empty spots and 42 (wow) queens.
For an n x n board, just put it in the corner and do the Sam thing as an 8 x 8 board
Give it in an IMO paper. You'll get it solved in a day.
True
It's nice to see how the label those books writing the subject with a pen in the base of all the pages.
The thumbnail is really cool!
For his problem at the end:
You could put the king in the corner, then put Queens everywhere except the vertical line, the horizontal line, and the diagonal line that intersect the king. That would be n^2 - (3n - 2) queens. That is n^2 being every spot on the board, and 3n - 2 being the 3 lines that intersect the king (the minus 2 is because you'll have counted the spot the king is on 3 times). You also slide the king along the border to get the same result. This equation only starts giving positive results when n is 4 or more since you can't have any Queens on a smaller board with a King.
42
for m x n, m
I had the same answer, but I only solved it for n=m. This is a better generalization than what I wrote.
Только на днях столкнулась с этим вопросом и заинтересовалась им. А сегодня вышла серия, посвященная данной проблеме. Теперь сижу и думаю, кто, чьи мысли прочитал... Only the other day I faced this question and became interested in it. And today there was a series devoted to this problem. Now sit and think, who, whose thought have read...
I think the answer to the problem at the end is n^2-3n+2. That's all the squares on an n×n board, minus one row, 1 column, and 1 diagonal (adding back in the king's square twice, since it is triple counted), which is what you get if you put the king along an edge.
What about making n go to infinite? Try to have 2 subsets of [0,1]^2 S and S' such that no 2 points of those sets would be sharing a vertical/horizontal/diagonal line.
Would continuity make that easier to study? Would we see the same shapes again?
Solution to that Brilliant puzzle at the end:
Best king position is along an edge because it eliminates a diagonal:
K - - - - - - -
- - Q Q Q Q Q Q
- Q - Q Q Q Q Q
- Q Q - Q Q Q Q
- Q Q Q - Q Q Q
- Q Q Q Q - Q Q
- Q Q Q Q Q - Q
- Q Q Q Q Q Q -
For 8×8: 64 total tiles - 7 tiles on the king’s row - 7 tiles on the king’s column - 7 tiles on the king’s diagonal - the king’s tile = 42 queens
For m×n: mn total tiles - (m - 1) tiles on the king’s row - (n - 1) tiles on the king’s column - (min{m, n} - 1) tiles on king’s diagonal - the king’s tile = m n - m - n - min{m, n} + 2 queens
i think i've found a solution to the puzzle regarding the maximum number of queens so that a king is not under attack. the part about the attacked piece being a king is extra information one can think of it this way: how many squares are _not_ a queen's move away from a singular square? if a queen is not on one of those squares, then it will thus be unable to attack the king. we then need to figure out where to place the king such that the least number of squares are of this type, which is the corner. why the corner is best is left as an exercise to the reader. thus, the answer will be 64-7-7-7-1=42 queens
edit: for an mxn chessboard, the number will be m*n-((m-1)+(n-1)+(min(m,n)-1)+1)
Honestly, the idea of the Peacable Queens is interesting. Also, im going to get a chess board and go crazy solving this. 2 *8*
They don't give you more than 2 queens for a regular chessboard. You can assume all the pieces as queens.
@@randomdude9135 that is true. You could probably order a bunch of queens on Amazon or something.
idk why you'd do it manually. That would literally take forever. Much better to just make a simple program to figure it out for you.
2:18 overwhelmingly nice
The credits puzzle is easy, you just stick the King in a corner and put Queens on every available space. That's 42 Queens. Or, more generally on a n*n board, n^2-3n+2 (since the Queens form two triangles of length n-2, which can be fit together as a (n-1)(n-2) rectangle).
3:28 the answer for 14*14 is 28. 3:38 he wrote that the answer is 27.
This is a lot more interesting than the classic eight queens problem I brute forced a couple years ago (finding all the positions for eight queens on a standard chessboard where no queen is attacking another). I guess mathematicians really like to generalize.
Never knew he founded oeis, one of my most favourite websites for sure.
When I studied domination in Graph Theory, I learnt the queen problem, but never tought of this problems.
For the King and a Lot of Queens puzzle, I think the answer for most queens with a safe king on a chessboard is 42.
To generalize it, I would say, for an m x n board, with m >= n, the solution will be (m-2) x (n-1).
Numberphilia is a sexual orientation i was not yet aware of. thanks for educating.
I was hoping this problem wouldn't have faded into obscurity by now. I know the 8 queen puzzle is more popular, but I was hoping with all the computing power currently, we'd have at least seen an update on this problem. I like these sorts of puzzles.
Hey fellow numberphile's. I'm looking for some advice on how to account for practicing a skill (changing probabilities). Like if I was practicing playing guitar hero and I hit the right note 40% of the time when I first started. The probability of hitting the right note is 40%, but if I keep practicing that number goes up. Which the typical binomial distribution doesn't account for. I wanna know, if I start out at 40% (or x%) what is the minimum & maximum time i can expect to be at z% chance of success given that I practice at some constant period.
The way this man talks about this with so much passion, he sounds like he's narrating a nature documentary
What's the background music from? Did you cite it and I just missed it?
The king + queens problem seems super obvious to me... Choose the position of the king first. The number of queens you can place is equal to the number of spaces on the board (64) minus the number of squares on rows, columns and diagonals that hit that square, since you can place a queen on everything except such squares. Every square has 15 squares on rows and columns hitting that square. It's easy to check that you get at least another 7 from diagonals, minimised by placing the king on the edge of the board. So the answer is 64-15-7 =
:O
Oh dang, this is the OEIS guy! Too cool!
Neil Sloane has to be one of my top 5 favorite living mathematicians, right up there with Conway and Baez
Oh no, not more celebrity worship.
The more queens there are, the harder it is for us to find peace.
Logan McCarthy - absolutely brilliant observation
James Grime did a similar video, interesting to see how different it is with different colours
Love this guy, he reminds me of the professor from Futurama
You could also think about what happens when there are more than two colors of queens, or higher dimensional chess boards while maintaining the rule that there must be the same number of queens of each color and no two queens of different colors can attack each other.
Thanks. Neil Sloane for a perfect Peaceable Queens' NUMBERPHILE 's 6th, 7mins.