The great Simon Singh tweeted this video! Here's the tweet: twitter.com/SLSingh/status/1021646697607426053 Simon Singh has written some of the best popular books on mathematics, including "Fermat's Enigma" and more recently "The Simpsons and Their Mathematical Secrets" (which I received as a birthday present, since my friends know I enjoy his books). Do check out his books!
If the chessboard was labeled so that the rows, from top to bottom, A-H and the columns were labeled, from left to right, 1-8, suppose Alice puts her knight on square C1. Bob would put his knight in square A2. Suppose Alice moves to square E2. Where would Bob move? Am I missing something?
The destroyer 94 If you didn’t already know, they’re both playing with the same night. Besides, even now when they are both playing with the same night Alice can’t move from either A2 or C1 to E2. Is there a possibility I missed something in your questions/statement (/Opposition)?
you can play the game here also another theory what is the highest posible score you can get by not moving over the already moved spaces but still complete the entire map
@Pulzanicus pulzanic take and take and take - free juicer - take. I blundered. Why am i so bad at Chess? Somehow he missed it too. Ok let's premove now.
@@aryankhullar7101 Of course he 'can', the point of the video is that he can always win when using the right strategy. But there is no guarantee that Bob will always use the right strategy, or even know it. If you didn't know the answer to this video, just as I didn't, then you wouldn't even be knowing what strategy to play in the first place and you would go back to square 1 and could as well just lose.
Alsp if alice starts she will win and if bon start he will wil since the amount of moves is odd the first to start is always the first to win if used the strategy
It's not like he is some kind of genius above us mortals, where if he couldn't figure it out, It means we can't figure out. I think you underestimate some people out there. Not everybody who watches these videos come to learn or see some problem that they wouldn't be able to figure out themselves. I'm sure there are people who watch these videos who can solve the problems he gives.
CTsilver _ no. This is just a true statement and also quite a useful piece of life information. There are some people who are familiar with these problems that know the solution but are curious if Presh has come across a new strategy. Presh is a very smart intellectual which cannot be denied but as shown, Sebastian helped him with the solution. A viewer similar to anyone of us provided the solution.
Second player will always win. 8x8=64. First player places piece which =63 squares left. Playing optimally will result in the second player taking the last available space. Dont know the reason for needing all the colours
SinfulMonk That approach assumes you can move from any square on the board to any other square on the board, but you can't. You can only use the knight's normal movement. That movement needs to be taken into account.
@Luke Dewhurst Due to how the knight moves, you need to come up with a strategy that works 100% of the time and explains how. You can't just say "theoretically he should win" you need to give the method of how he should win
Very clever solution. I had another way in my head about how Alice can only move to dark squares ever and Bob only to white and since it starts on a white tile then Alice would automatically run out first.
Julian Lapenna that's a correct way and will yield the same ans but you have to prove that Alice can't trap Bob before that and thus the videos strategy comes in
That's assuming that there are enough legal ways to move up until you clear every single tile, and that there's no strategy you could devise which would generate a win up until then.
OK, at first I didn't understand how this proves anything, but I think that is because you left out a step. Yes, Alice can return to one of the previous sections, but will always have to choose a different color square than when they were previously there. Since it is a new color, Bob will always have the matching one. So, the important part of the strategy is that Bob is always making sure that each pair is eliminated together in consecutive moves. This prevents Alice from ever returning to a block where the matching color was already used.
Oh ok so that's why i was suspecious of this strategy, i knew something wasn't right but he just didn't/forgot to mention that the horse (Alice's turn) can return to a visited region, but of course i didn't think all the way deep
@@guilhermecaiado5384 That's not an answer, that's a small part of an example of a winning strategy. You could play the same game and flip it into horizontal regions of 4x2 and it'll have the same result, naturally. I'm willing to bet there's other winning strategies, or other ways of framing the same winning strategy.
fantastic! its such an easy proof for a problem that seems mindbogglingly complex. This problem really shows the importance of breaking down problems into smaller pieces and then putting them back together. Kind of like a divide and conquer in algorithm design.
I didn't think the strategy out, but simply counting the possible moves gives the outcome away. In each square of the board, there's an even number of possible moves; the only squares where it's not true are the ones adjacent to the corners, because starting from there you have only 3 moves possible. However, there are 8 of such squares, and 8*3 = 24 possible moves. This method didn't take into account the fact that you can't return on the same square, but it doesn't matter: as long as the total of moves is even, Bob can always assure his win if he plays optimally, and if the total number of moves is odd then Alice can always assure her win. Think of it as trying to draw a sumple home without lifting the pencil: each vertex has either an even number of lines that depart from it, or there is an even number of vertexes (dunno if that's the right plural) that have an odd number of lines that depart from them. If this condition is satified, you can finish to draw the house, and the same principle applies to this problem, where each vertex (square) only has 2 lines (because no player can return on that square, so there's one line to get into the square and one line to move out from that square).
Before I see the complicated mathematical reasoning, I’m going to guess that player 2 always wins. My logic behind this guess: the knight switches color tiles each move, if we assume all tiles can be touched, player 1 will lose one pace before player 2.
I think it also might help to be familiar with other games (such as the "21 game" described on en.wikipedia.org/wiki/Nim ) in which the second player always has the chance to counter the first player's previous move in some way so as to "balance" it some way and keep a certain quantity within a certain state. The maintenance of the ability to balance it then implies the simpler condition of even being able to make a move in the first place, and thus not immediately lose the game. In the "21 game" player 2 is always able to keep the number modulo 4 equal to 0 by countering a 1 with a 3, a 2 with a 2, and a 3 with a 1, and thus force the number 20 to come up on player 1's turn. In this problem, a person who successfully came up with it might do so by looking for a condition player 2 could force to be balanced on every turn. Turns out that with the strategy found, this condition is "keep the number of visited squares of any knight-linked pair in any 4x2 region either 0 or 2". If Alice changes that quantity from 0 to 1, then Bob makes the moves that changes it to 2, from which it must remain the rest of the game.
Adam Pugh It was made clear that in the first move, alice places the Knight, then it'll be bob's turn and the moves will follow Knight movement patterns. Not really ambiguous
mrBorkD It was not clear, either that Alice can place the knight on any square, or that Bob moves it first. Neither was stated explicitly in the problem description.
Alice getting to choose the initial square or not is a moot point - if she can't win when she chooses the square, then she still can't win when she doesn't. That Bob takes the first move once the knight is on the board is clearly implicit from the explanation, but I agree it should have been explicit in the initial problem statement.
"Alice starts by placing a knight on the chessboard. Then they take turns moving the knight to a new square" while this doesn't explicitly make clear that after placing the knight, bob gets the next move, it does make clear that Alice gets to "place the knight" i.e. she can choose any square.
So basically, Alice puts a knight on a random tile. Thinking that, 4x2 regions will eventually pile up. Bob's only goal is to fill the only legal move for the knight in that 4x2 regions, and since Alice can't move it on the same tile where the knight has been, she is forced to move it on another 4x2 region. Bob then takes the legal move again and that leaves Alice to move into another region. Even if you encounter the same region, Bob always has the legal move since Alice will only move it to another. The whole chessboard, marking the 4x2 region system, leaves 4 moves for Bob and therefore, he can occupy the 32 squares since 4x2 regions are 8 in total. Removing the first position will only leave Alice in an odd possibility, specifically 31 since (64-1=63) then (63-32=31). Bob takes the first move and Alice will make another move so we can say that every turn leaves them at the same number of moves. (Every turn = 1 Bob, 1 Alice) and since Bob took the first turn, the 32nd tile he placed will leave the 32nd turn into 32 Bob, 31 Alice. This time, all squares are occupied, so the first position won't matter anyway
I wonder if this game will end in less than 64 moves, each time Bob will block a square Alice will find a way to escape until all 64 squares are occupied.
I think your answer need some corrections .if Bob At 4:50 stage .moves from bloc c7 to bloc f8 instead of moving to block d 5 then the. Game will turned of .such options will be available to him at each step
it's not though. if both players are playing optimally the first person to move would win. if bob placed the piece and alice went first, who was also playing optimally she would win. the problem assumes the winning player knows this solution.
I have played chess for a long time and the knight is my favorite. I also love math and I have been watching your videos for a long time. I did not manage to solve the puzzle but I had a thing through it and found some interesting ideas. Keep up the great work on these videos!
I've always thought standard chess theory is wrong in assigning approximately equal value to knights and bishops. It seems to me knights are much more valuable than bishops, as no other piece, including the queen, can jump over pieces, plus the fact bishops are permanently restricted from half the board. I think the advantage of being the only piece on the board that can jump over pieces is undervalued by most players. I always trade bishops for knights whenever possible.
Presh, you give us really good math questions. But when you say that you didn't figure it out by yourself, it really breaks my heart for some reason... 😳
there is 64 squares on a board if we do it in the equal amount it gives us 4*2 8 of them and seeing the pattern of the night for bob it always goes on black no matter what and for alice it goes on the white so by that were also able to calculate it
5:24 You mean the game has to end in 63 moves or fewer, since there are only 64 squares and Alice already occupied 1 of the at the start so 64-1= 63 possible squares left?
I think there needs to be more specification that "new square" means a square that you haven't landed on before. At first I assumed that they meant the first person who couldn't move the knight at all looses and I was like "umm... that's literally an impossible circumstance on an empty chess board..." lol
I immediately recognized that optimal play by both players would end with a full knight tour. Since there are 64 squares to visit, and Alice is filling the first square, then Bob will visit all even squares, including the last unvisited square.
Daniel Macculloch Any movement which is not part of a knight's tour will lead to a player losing in fewer moves than a knight's tour. But you are right, this is not enough; I still have to prove that if player 1 plays anything that will truncate the knight's tour, player 2 will still have the last move and win. And this is not obvious.
After working on it, I think that optimal play should result in a full knight tour save three corner squares. This comes from the fact that for 3 out of 4 corners, all squares within reach of corner squares are an even number of steps away from start but one of the three corners they are an odd number of steps away. This means that Alice will always be able to ovoid going to three of the corners reducing the visited squares to 61 and thus Alice can always win. Edit: 2 out of 4 squares within corner square are an even number of steps away so Bob will win (I confess this is after looking at the solution.)
Actually there's an easier solution that ends in the same answer. A very interesting property with chess knights is that they always move to a square with the other color. So if the knight is in a white square it can only move to a black square and viceversa. This means they won't get in each other's way. Also, when Alice places the knight she's taking up one square. When bob moves the knight, there will always be an even number of squares available. This means the 64th square will be taken up by bob. The only thing he has to make sure is to not get himself trapped without squares to move. With this information, you can deduct that bob can win, without the 4x2 rule.
Even if the properties of the board and game means that Bob always wins in the end, unless someone screws up before the last square is moved to, it is still possible for Bob to lose since he can also screw up. The solution in the video guarantees the win though, i.e. it guards against getting trapped. No matter what square Alice moves to, there will always be the other side of the "square pair" inside the region open for Bob. The terminology of saying "Bob can always win" is a bit misleading though.
That's not really a solution I'm afraid. It would be possible for Bob to have already blocked off the only squares available in some case, so though there are available spaces somewhere on the board he can't necessarily move to them if his strategy hasn't been correct. The solution given here is possibly slightly more complex than it needs to be however. The 4*2 blocks are helpful to demonstrate a system where Bob has a unique move he should choose from any position Alice leaves him. Importantly every spot Alice can finish has a unique followup move from Bob and every spot Bob can move to has a unique position on the board that he moves there from. What Alice does and which sector she is in is at that point irrelevant, he has a defined move available for any square she leaves him on and that move is always available since she can't have left him on the trigger square for that move previously, thus if she has a legal move he always has his follow up move pre-defined and always wins.
As presented, the proof that Bob can force a win is missing a step for completeness. The proof shows that Bob can force Alice to exit a 4x2 region, but does not examine what happens when an "Alice" move returns to a region in which Alice and Bob have already played. Since untouched regions and regions that have already seen paired Alice/Bob moves are not identical, the form of the proof requires an argument at the sub-region (graph color pair) level. Note first that: (1) Alice will always play on the same board color (black or white); (2) Bob will always play on the opposite board color (white or black); (3) each of the 4x2 regions contains four color pairs (green, teal, yellow, and purple); and (4) a color pair within each region includes one square of each board color (green in a 4x2 region is one black square and one white square, teal in a 4x2 region is one black square and one white square, etc.). Assuming Bob follows the strategy described, then for each 4x2 region, Alice might return up to three times. Each time Alice returns to a 4x2 region, she must play to a graph coloring pair (green, teal, purple, or yellow) that was not previously exhausted by an Alice/Bob move pair. When Alice does, Bob will always be able to play to the opposite board color (black/white) square of the same graph coloring color. That will both exhaust one of the graph coloring color pairs for the region and (returning us to the proof as presented) force Alice to move outside the 4x2 region on her next move.
Shawn Winnie going to a region they've already been doesn't change anything. Bob can do the exact same, going to the only possible spot in that 4x2, resulting in alice having the do the exact same thing, moving out of that 4x2?
Duck. I thought Alice always wins, but her putting the knight on the board is her first move. If the chest piece was already there (randomly) and THAN Alice's first move was to move it, than Alice would always win.
my first thought on the problem was that it was a flawed game, given that your dealing with even numbers it to me meant that the winner was predetermined by who went first or second, very cool video to see other peoples thought processes.
iCEW0LF Was thinking the same thing and started looking for others in the comments who had noticed that. He just got n+1 mixed up with n-1 :-) Thanks for confirming my suspicion.
Well, it depends on what we call a move. It should be 65, as Alice places the piece (move 1). Bob moves (move 2). At move 64 all squares have been visited once. Move 65 then results in Alice losing, as no free squares are left.
hi, I have a similar but much harder chess problem for you. you fold the chess board in half so you play on 4*8 squares. you put all 32 chess pieces on the board and start to capture the pieces with one knight(the only moving piece). the starting square of the playing knight should be randomly chosen. The target of the game is to capture all the chess pieces. You can only capture a piece, you are not aloud to move on a square were you already moved. so technically you should capture all the pieces in 31 moves. I would much apreciate an answer
Dude Alice's first move is placing the knight See it is simple 1)If alice moves the knight after placement means her squares get used later than Bob which according to theory means that alice wins 2)If you think that the placement sqaure is not booked then Bob can move back thus you contradict yourself(which i hope you don't (just to make sure u understand in the first go)) In your sense the first to move always wins The same thing
But if you take a 4x4 there can be executed up to 4 moves. Ex. (R4,C1)→ (R2,C2) (R2,C2)→(R3,C4) (R3,C4)→(R1,C3) (R1,C3)→(R2,C1) R=Row, C=Column So I dont know if this is the way to prove it. Also there is a thing called "Knights tour" where there a knight can go from any position and fill the entire board. Which means that there are 64 moves in including the act of putting the knight on the board. So without that there are 63 moves to be done so the one to go first always wins indeed.
Your post presents the following four moves: 1. (R4,C1) → (R2,C2) 2. (R2,C2) → (R3,C4) 3. (R3,C4) → (R1,C3) 4. (R1,C3) → (R2,C1) After those four moves, we can certainly do ten more moves: 5. (R2,C1) → (R4,C2) 6. (R4,C2) → (R2,C3) 7. (R2,C3) → (R1,C1) 8. (R1,C1) → (R3,C2) 9. (R3,C2) → (R2,C4) 10. (R2,C4) → (R4,C3) 11. (R4,C3) → (R3,C1) 12. (R3,C1) → (R1,C2) 13. (R1,C2) → (R3,C3) 14. (R3,C3) → (R1,C4) And now it's Bob's move, and since he can't move, he loses.
Took me 20 seconds to figure out, feels good man. in short: It is possible to divide the chessboard into pairs of squares, which are "L" apart. (trick that I've used in some other combinatorics problem, such as "how many knights can stand on the chessboard and not attack each other") Bob wins, because he always moves the knight to the second square from the pair, Alice just entered into, thus he always has a move and after his move, pair becomes unavailable.
That's a fun game and challenging problem. I didn't solve it even though I knew about the "knight's tour". What this video lacked was a discussion of how one might come to the idea of breaking the board into 2x4 regions.
it's the only way to split the board in equal portions to which this rule of unique pairs applies. (of course you can swap 4x2 and 2x4). The rule also applies to 3x2 but you can't split the board into only 3x2s.
Bradley Hudson i think if alice go 1st and stayed on the 4x2 box. bob can win if he makes it to vertical box (2x4). haven't fully confirmed this. can anyone confirm?
I came up with the right answer, but with much less formal reasoning (but did not come up with an optimal strategy.) There are an even number of squares that can be occupied. The first player takes odd moves, the second player takes even moves. It's possible to occupy every space on the board. Bob wins by forcing an even move victory. Alice wins by forcing an odd move victory. There are more even move solutions than odd move solutions. Since, there is no backtracking, Bob has more control over the sequence the knight proceeds through the board. All Bob needs to do is prevent leaving the Knight in a location that leads to an odd turn victory. The caveat is that I'm not 100% sure I've proven the board starts in an even turn victory solution. It makes intuitive sense to me, and I find it difficult to imagine it could be wrong. But I'm unsatisfied with just "the longest game is this way, so it must be the default." But ultimately, as long as that assumption is correct, the concept of Bob being able to maintain advantage should hold true.
Well, it's same problem i did solved a 2 week ago from my math teacher. :) You did another way to solved mine was different. Keep learning, keep making this video!
seems like a more accessible illustration of how the second person always gets to take the last square on the board since there is an even number of them
Two things that do need to be kept in mind here is that it is relevant who actually makes the first knight move, as well as the fact that a knight's tour is possible. The knight's tour probably becomes less relevant if not irrelevant if the 4x2 theory is applied by both players, since I am unsure if knight's tours can be completed taking into consideration this condition.
Hey Presh, you inspire me to do a lot of things and I really enjoy every single video you upload. I’m a junior in high school and have never gotten less than an A in any subject on report cards and I really appreciate math (algebra and trigonometry so far, taking calculus next year) and I wanted to ask if you had any suggestions for becoming a mathematician or something like that. I’m not sure if you can contact me or anything but with your input I think I can get into an excellent college and be want I want to be.
I echo what Scott said. Khan Academy is a great resource if you are a visual/auditory learner. As a student and Teacher, I've utilized Khan Academy to much benefit. You should also check out the free coursework offered by MIT. They literally have entire courses (lectures and exams) for you to use at your disposal.
JuditeTormentor any suggestions on “getting my name out there?” What should I do while I’m taking my last year in high school to try and make it to the college that I want? Is it strictly gpa and sat scores that let me go to a top college?
What I would like to know, is how would one come up with this type of proof? What made you/someone try to limit themselves to 4x2 squares and why? I don't feel like I ever get any better at solving these types of riddles due to only receiving explanations rather than methods of analyzation. One thing is to know the conclusion (that bob would win since the knight can go anywhere on the board), another is to be able to prove it.
A 4x2 (or 2x4) is selected because the chessboard can be divided into it equally, and because within a 4x2 for any square there is exactly one and only one other square in the same 4x2 section a knight can legally move to.
Languste Well it's basically an easy to remember way of turning 64 squares into 32 pairs. And that ia what matters, the pair. As long as you have 32 pairs you can constantly pick the other of the pair and it will be imposible for A to find a square that does not have its pair left, because when it is A's turn, there are always only two option, either both of the pair are free, or neighter are free. This way B always has a move. It's a very elegant solution to the problem. The entire box thing is just an easy way for humans to remember, but any solution in which there are 32 pairs it would work.
It's probably easier to come up with the solution if you consider the 4x4 version of the chess board. If Bob doesn't stay on the same side, Bob can lose.
There's another cool puzzle that has a proof that similarly made me think "Wow, that's really neat but how did someone think of it?" in a numberphile video about pebbling a chessboard and freeing clones: th-cam.com/video/lFQGSGsXbXE/w-d-xo.html
Nice logic!! My logic was that as there are only 64 squares and assuming both of them are playing optimally they will eventually run out of squares thus the one who is starting first will always lose.
there is a neat little trick/puzzle where you have to visit each and every square once and not more with a knight and if you know the moves it does not matter where the knight starts
Actually, no. When Bob (the player who moves second, after Alice has placed the knight somewhere on the board as her first move) has made his first move and his first move doesn't correspond to the winning strategy in the video, then Bob can (and will) still win because he will still have many alternative winning strategies with which he can force a win. Alice still cannot force a win when Bob's first move deviates from the video's winning strategy.
I had solved a variant of this problem. It asked if a knight on the chessboard can cover the entire chessboard in a series of moves. It was a programming question and the answer is yes. I have been since wondering if one can analytically prove that a solution exists and it is unique. The video helps orients me to think in graph theory terms. Thanks.
The principal: if Alice is able to move the knight to ANY of the 8 regions, Bob will always have a square in THAT region to move the knight to. This is because of the strategy Bob uses. Alice places the knight = first move. Bob does the even moves and wins because there are 64 moves/squares.
Another thing that I wanna point out (this is unrelated to the puzzle) is that the colors match perfectly despite one seemingly lighter than the other. It is but another illusion.
You should clarify that the first square (the one alice places the knight on) can be revisited, as that changes the result. I for example, thought the winner would be alice because the starting square is "one it has been on before".
I did not find a solution, but as Alice will always move to (or start at) white squares (and Bob will always move to black squares), I guessed Bob would win since Alice will run out of white squares before Bob runs out of black ones.
You should have mentioned that the example at 1:21 and that at 4:03 are different examples and that both move the same knight, because I had to explain both of these facts so many times in the comments section. It appears that John Allen Paulos is right when he speaks about the spread of innumeracy in his book "Innumeracy".
I don't think anything needs to be changed for the audio part. The explanation is crystal clear and surprisingly simple. However I am not a fan of slides showing every spoken word. I'd rather see interesting visual designs, such as chess pieces, boards or anything relevant to the topic.
Maybe i'm wrong (or i missed something) but you left out some info, that the original square the knight starts on can be visited again as you do that in the example. For me "you can't visite a square again" implies the first position before people do a move is also one (which would implie the oposite result)
OK , it was an attempt at humor .... " playing with myself " is a metaphor for masturbation in English , I don't know if English is a second language for You ( if so , You speak it well ) or if You are "playing" with Me now but either way have a great life ..... ( and get a Girlfriend )
Okay, I have a big question. Suppose, Bob doesn't know this trick and he takes it to a random square. Alice plays another move and Bob again takes the knight to a random square. Now is there any possible way for Alice to ensure that she wins the game? And, if there is, what are the first two pairs of moves (or N pairs of moves if it cannot be confirmed after only 2 pairs of moves)? And, obviously, what is the strategy?
You're overanalyzing. Each move goes from either white to black, or black to white. If the Knights initial placement counts as a square that can't be landed on again, and if both players are playing optimally, the best strategy is to go first.
Presh forgot to expand out on what happens if Alice moves to a different 4x2 rectangle on her move, after moving out of the initial 4x2 rectangle. Alice could move in a few different directions on her second move. Bob can still win if he sees what Alice is up to, though.
I just figured that there were an equal number of black and white tiles. That's 2*32. The knight can only move from one color to the other. That creates either a black-white or a white-black sequence that can be repeated up to 32 times. Even if, theoretically, the knight could move to every tile, the person to finish the 32nd sequence would be the winner, as there is no 65th tile to move the knight to. This would only prove that Bob wins though, didn't exactly provide a strategy for him.
This is a special case of a harder problem, where you have a graph G and players move to vertices and the player who traps the other wins. Turns out the second player has a winning strategy if and only if the graph has a perfect matching, and it’s easy to check the knight’s graph has one.
The problem with this solution is that a knight doesn't have to move 2 squares first then one square. The knight can move 1 square then 2 squares. So using the grid from above the knight can move one square up to purple for example and then over 2 squares landed in another grid also putting the knight in a color square it didn't start in. I don't know if the outcome would be different as you can still use all the squares in the grid this way but after 2 turns Bob would be locked out of using the same color squares method cause he couldn't move back to yellow.
You can go through each region multiple times. Each time you eliminate another pair of squares. This happens until Alice gets blocked by adjacent regions that are saturated.
Because this is a new square in an old region, the matching square in the same region for Bob to move to is still available. Let's call each pair of similarly-coloured squares a Bob-pair; these are connected by a Bob-move as Presh described. Before each of Alice's turns (including the initial placement of the knight), all of the Bob-pairs are either both-free or both-visited. Alice can't place/move the knight to a visited square, so she must put the knight on one square of a Bob-pair which has both squares free. This assures that Bob has a move (to the other square of the Bob-pair). Once Bob has moved the board is back in the state of having only both-free or both-visited Bob-pairs, so Alice is back where she started. Eventually at Alice's turn all the Bob-pairs are both-visited so Alice has no moves. The game could end early by someone only having visited squares to move to, but since Bob always has a move, only Alice can be trapped.
The pairs of similarly coloured tiles GUARANTEES that Bob will always have a legal move. No matter what, Alice loses, as she will at some point not be able to.
Here is a counter example Alice starts A8, bob counters B6, Alice is forced to the adjacent region C7, so bob counters D5, now Alice goes back to the first region B5. Bob can no longer reach the same “colored” square that Alice is on.
I don't understand how you get Alice moving from B6 to C7 or D5 to B5, as neither of those are legal knight moves. Nevertheless this does not matter, the solution still works even if Alice can place the knight on any new square one each of her turns! So you say Alice goes to B5. Well then Bob goes to A7, his matching square in the same rectangle. Now it is Alice's turn again. Where's the "counter" part of this counterexample?
The great Simon Singh tweeted this video! Here's the tweet: twitter.com/SLSingh/status/1021646697607426053
Simon Singh has written some of the best popular books on mathematics, including "Fermat's Enigma" and more recently "The Simpsons and Their Mathematical Secrets" (which I received as a birthday present, since my friends know I enjoy his books). Do check out his books!
Proof is incomplete. The statement “Bob will always have a move” (whenever a 4x2 region is revisited) is nontrivial.
If the chessboard was labeled so that the rows, from top to bottom, A-H and the columns were labeled, from left to right, 1-8, suppose Alice puts her knight on square C1. Bob would put his knight in square A2. Suppose Alice moves to square E2. Where would Bob move? Am I missing something?
The destroyer 94
If you didn’t already know, they’re both playing with the same night.
Besides, even now when they are both playing with the same night
Alice can’t move from either A2 or C1 to E2.
Is there a possibility I missed something in your questions/statement (/Opposition)?
you can play the game here
also another theory what is the highest posible score you can get by not moving over the already moved spaces but still complete the entire map
It’s just a theory a GAME THEORY
ofcourse bob will win his last name is fischer
Only chess players will understand this!
@@raghav4866 I understood it and I don't play chess. Hence, your premise is falsw
@@raghav4866 ok gatekeeper
Booby fisher
No, Bob will win cause he is man...
Math Olympiad: *Sweats*
Chess Grand master: *Laughs*
It might be tough for a chess grandmaster as well
@Pulzanicus pulzanic 5 minutes? Give Hikaru 30 seconds before he starts calling it easy
@Pulzanicus pulzanic take and take and take - free juicer - take.
I blundered. Why am i so bad at Chess? Somehow he missed it too. Ok let's premove now.
@@InternetMadnez chat chat i dont get it chat why are you laughing chat
Yeah lol. I am a chess player and I solved this.
"Did you figure it out?"
yea i just whipped up my handy coloring graphs and chessboard png i always have those for random youtube videos
@@aftabkhan-EAEB imagine having such an attitude towards math
@@aftabkhan-EAEB I am in 9th grade and the book is still colorful, but yeah they aren't as big as 3rd grade
@@aftabkhan-EAEB well then clearly they don't know game theory. It's not like that's a bad thing
@@aftabkhan-EAEB You be calling everyone a handicap child lmao
@@pyro1694 he wants to feel special by calling everyone else special lol
So basically, if Bob loses he has no excuse
He cannot technically
@@aryankhullar7101 Of course he 'can', the point of the video is that he can always win when using the right strategy. But there is no guarantee that Bob will always use the right strategy, or even know it. If you didn't know the answer to this video, just as I didn't, then you wouldn't even be knowing what strategy to play in the first place and you would go back to square 1 and could as well just lose.
But Alice said she'll play Smash Ultimate with him if he loses.
Alsp if alice starts she will win and if bon start he will wil since the amount of moves is odd the first to start is always the first to win if used the strategy
No body wins, No kings are in the game lol
"I couldn't figure it out, CAN YOU FIGURE IT OUT"
It's not like he is some kind of genius above us mortals, where if he couldn't figure it out, It means we can't figure out. I think you underestimate some people out there.
Not everybody who watches these videos come to learn or see some problem that they wouldn't be able to figure out themselves. I'm sure there are people who watch these videos who can solve the problems he gives.
Diamond Bolt r/iamverysmart
CTsilver _ no. This is just a true statement and also quite a useful piece of life information. There are some people who are familiar with these problems that know the solution but are curious if Presh has come across a new strategy. Presh is a very smart intellectual which cannot be denied but as shown, Sebastian helped him with the solution. A viewer similar to anyone of us provided the solution.
AlexD r/nobodygivesafuck
jerckï72 Dora the explorer reference?
What if Alice knows this as well, and insists that you go first?
😂, good one
Second player will always win. 8x8=64. First player places piece which =63 squares left. Playing optimally will result in the second player taking the last available space.
Dont know the reason for needing all the colours
SinfulMonk That approach assumes you can move from any square on the board to any other square on the board, but you can't. You can only use the knight's normal movement. That movement needs to be taken into account.
@족발러버 if there are 2 squares ledt lent of course player 2 wins.... player 1 plays now there is 1 square left. Not too hard to get that is it?
@Luke Dewhurst
Due to how the knight moves, you need to come up with a strategy that works 100% of the time and explains how. You can't just say "theoretically he should win" you need to give the method of how he should win
Very clever solution. I had another way in my head about how Alice can only move to dark squares ever and Bob only to white and since it starts on a white tile then Alice would automatically run out first.
Julian Lapenna that's a correct way and will yield the same ans but you have to prove that Alice can't trap Bob before that and thus the videos strategy comes in
I had the same thing in my mind.It's not a proof, but it's a good intuition to decide who will win.
same here it took me 2 sec to do it... too lazy to really solve it
That's assuming that there are enough legal ways to move up until you clear every single tile, and that there's no strategy you could devise which would generate a win up until then.
Phil Hutchinson that's a very good point thank you I didn't think of that!
OK, at first I didn't understand how this proves anything, but I think that is because you left out a step. Yes, Alice can return to one of the previous sections, but will always have to choose a different color square than when they were previously there. Since it is a new color, Bob will always have the matching one.
So, the important part of the strategy is that Bob is always making sure that each pair is eliminated together in consecutive moves. This prevents Alice from ever returning to a block where the matching color was already used.
This formation also gives Bob a square to move each time.
If u start on a yellow, It’s impossible to end up on another color if u put that 4*2 color pattern throughout the board
@@hassankassem2858 nope, it's not
Oh ok so that's why i was suspecious of this strategy, i knew something wasn't right but he just didn't/forgot to mention that the horse (Alice's turn) can return to a visited region, but of course i didn't think all the way deep
I don't think he had to mention something that obvious...
When he say "game theory", i felt it.
But that's just a theory... A GAME THEORY
That’s just what they call it
Game theory first term
A beautifully simple solution to what I see as a very hard puzzle
Yes
The answer is 2x4.
He literally gave the answer at the start of the explanation, but didnt explained how he got to that number.
@@guilhermecaiado5384 That's not an answer, that's a small part of an example of a winning strategy.
You could play the same game and flip it into horizontal regions of 4x2 and it'll have the same result, naturally.
I'm willing to bet there's other winning strategies, or other ways of framing the same winning strategy.
@@tomdekler9280 No, im talking about maths to prove it.
fantastic!
its such an easy proof for a problem that seems mindbogglingly complex.
This problem really shows the importance of breaking down problems into smaller pieces and then putting them back together. Kind of like a divide and conquer in algorithm design.
In this essay I will...
I didn't think the strategy out, but simply counting the possible moves gives the outcome away. In each square of the board, there's an even number of possible moves; the only squares where it's not true are the ones adjacent to the corners, because starting from there you have only 3 moves possible. However, there are 8 of such squares, and 8*3 = 24 possible moves. This method didn't take into account the fact that you can't return on the same square, but it doesn't matter: as long as the total of moves is even, Bob can always assure his win if he plays optimally, and if the total number of moves is odd then Alice can always assure her win.
Think of it as trying to draw a sumple home without lifting the pencil: each vertex has either an even number of lines that depart from it, or there is an even number of vertexes (dunno if that's the right plural) that have an odd number of lines that depart from them. If this condition is satified, you can finish to draw the house, and the same principle applies to this problem, where each vertex (square) only has 2 lines (because no player can return on that square, so there's one line to get into the square and one line to move out from that square).
you just described "analysis"
Before I see the complicated mathematical reasoning, I’m going to guess that player 2 always wins. My logic behind this guess: the knight switches color tiles each move, if we assume all tiles can be touched, player 1 will lose one pace before player 2.
Yep, that's a good intuitive place to start, looking for the possibility of a Bob-favoring strategy rather than an Alice-favoring one.
I think it also might help to be familiar with other games (such as the "21 game" described on en.wikipedia.org/wiki/Nim ) in which the second player always has the chance to counter the first player's previous move in some way so as to "balance" it some way and keep a certain quantity within a certain state. The maintenance of the ability to balance it then implies the simpler condition of even being able to make a move in the first place, and thus not immediately lose the game.
In the "21 game" player 2 is always able to keep the number modulo 4 equal to 0 by countering a 1 with a 3, a 2 with a 2, and a 3 with a 1, and thus force the number 20 to come up on player 1's turn.
In this problem, a person who successfully came up with it might do so by looking for a condition player 2 could force to be balanced on every turn. Turns out that with the strategy found, this condition is "keep the number of visited squares of any knight-linked pair in any 4x2 region either 0 or 2". If Alice changes that quantity from 0 to 1, then Bob makes the moves that changes it to 2, from which it must remain the rest of the game.
Wow, the solution is so simple once it’s explained, even though the question itself seems so difficult to prove
"Brother and sisters I have non, but that man's father, is my fathers son." Solution: That man is my son. Simple once you know the solution.
You need to clarify that Alice can choose any square, and then Bob makes the first move.
Adam Pugh It was made clear that in the first move, alice places the Knight, then it'll be bob's turn and the moves will follow Knight movement patterns. Not really ambiguous
mrBorkD It was not clear, either that Alice can place the knight on any square, or that Bob moves it first. Neither was stated explicitly in the problem description.
Alice getting to choose the initial square or not is a moot point - if she can't win when she chooses the square, then she still can't win when she doesn't.
That Bob takes the first move once the knight is on the board is clearly implicit from the explanation, but I agree it should have been explicit in the initial problem statement.
"Alice starts by placing a knight on the chessboard. Then they take turns moving the knight to a new square" while this doesn't explicitly make clear that after placing the knight, bob gets the next move, it does make clear that Alice gets to "place the knight" i.e. she can choose any square.
So basically, Alice puts a knight on a random tile. Thinking that, 4x2 regions will eventually pile up. Bob's only goal is to fill the only legal move for the knight in that 4x2 regions, and since Alice can't move it on the same tile where the knight has been, she is forced to move it on another 4x2 region. Bob then takes the legal move again and that leaves Alice to move into another region. Even if you encounter the same region, Bob always has the legal move since Alice will only move it to another. The whole chessboard, marking the 4x2 region system, leaves 4 moves for Bob and therefore, he can occupy the 32 squares since 4x2 regions are 8 in total. Removing the first position will only leave Alice in an odd possibility, specifically 31 since (64-1=63) then (63-32=31). Bob takes the first move and Alice will make another move so we can say that every turn leaves them at the same number of moves. (Every turn = 1 Bob, 1 Alice) and since Bob took the first turn, the 32nd tile he placed will leave the 32nd turn into 32 Bob, 31 Alice. This time, all squares are occupied, so the first position won't matter anyway
I wonder if this game will end in less than 64 moves, each time Bob will block a square Alice will find a way to escape until all 64 squares are occupied.
if both players play optimally, no
@@jiogcyihsugyiocjfdoivhphvw6821 Proof?
I think your answer need some corrections .if Bob At 4:50 stage .moves from bloc c7 to bloc f8 instead of moving to block d 5 then the. Game will turned of .such options will be available to him at each step
Presh That was brilliant. I'm reasonably good at maths, and love your videos, but some go over my head.But you explained this one beautifully. :)
But that's just a theory,
*A GAME THEORY*
it's not though. if both players are playing optimally the first person to move would win. if bob placed the piece and alice went first, who was also playing optimally she would win. the problem assumes the winning player knows this solution.
chazm00 he made a joke. Don’t over analyse it. (Which I guess is kinda ironic)
chazm00 1:41 cmon man it's a joke
dont tell me what and what not to do sir/madam!
chazm00 whooosh
I have played chess for a long time and the knight is my favorite. I also love math and I have been watching your videos for a long time. I did not manage to solve the puzzle but I had a thing through it and found some interesting ideas. Keep up the great work on these videos!
I've always thought standard chess theory is wrong in assigning approximately equal value to knights and bishops. It seems to me knights are much more valuable than bishops, as no other piece, including the queen, can jump over pieces, plus the fact bishops are permanently restricted from half the board. I think the advantage of being the only piece on the board that can jump over pieces is undervalued by most players. I always trade bishops for knights whenever possible.
@@strideman1680 knights are often better when there are a lot of pieces on the board. However in endgame bishops are usually better.
Wow. Such a simple answer from what seemed to be such a complex question. That's what I like to see, Presh!
*Knights tour was a java coding project we did in class...its pretty fun!*
You go around the edges then slowly come back to the middle.
1:40 But it’s just a theory. A GAME THEORY!!
Thank you for watching
Presh, you give us really good math questions. But when you say that you didn't figure it out by yourself, it really breaks my heart for some reason... 😳
but how do we get the solution that we need to select a 4*2 region?
there is 64 squares on a board if we do it in the equal amount it gives us 4*2 8 of them and seeing the pattern of the night for bob it always goes on black no matter what and for alice it goes on the white so by that were also able to calculate it
5:24 You mean the game has to end in 63 moves or fewer, since there are only 64 squares and Alice already occupied 1 of the at the start so 64-1= 63 possible squares left?
The starting square counts as a move
@@waffleuser so we're at 64 Moves
...what's the 65th?
It is difficult but you have made it easy to follow. Such an amazing work. Thank you!
I didn't figure out this one. So wonderful and clever solution! Thanks for sharing it.
I think there needs to be more specification that "new square" means a square that you haven't landed on before. At first I assumed that they meant the first person who couldn't move the knight at all looses and I was like "umm... that's literally an impossible circumstance on an empty chess board..." lol
I immediately recognized that optimal play by both players would end with a full knight tour. Since there are 64 squares to visit, and Alice is filling the first square, then Bob will visit all even squares, including the last unvisited square.
Why does optimal play result in a knight tour? Maybe one player has a strategy that will cause them to win earlier.
Daniel Macculloch Any movement which is not part of a knight's tour will lead to a player losing in fewer moves than a knight's tour. But you are right, this is not enough; I still have to prove that if player 1 plays anything that will truncate the knight's tour, player 2 will still have the last move and win. And this is not obvious.
flamewing I thought that too at first, but quickly rejected the idea due to the logical flaws listed above
flamewing wrong, you did not
After working on it, I think that optimal play should result in a full knight tour save three corner squares. This comes from the fact that for 3 out of 4 corners, all squares within reach of corner squares are an even number of steps away from start but one of the three corners they are an odd number of steps away. This means that Alice will always be able to ovoid going to three of the corners reducing the visited squares to 61 and thus Alice can always win.
Edit: 2 out of 4 squares within corner square are an even number of steps away so Bob will win (I confess this is after looking at the solution.)
Seems I missed this one when it was posted. Very good.
That end art where the letters rearrange themselves is so cool
Actually there's an easier solution that ends in the same answer.
A very interesting property with chess knights is that they always move to a square with the other color. So if the knight is in a white square it can only move to a black square and viceversa. This means they won't get in each other's way. Also, when Alice places the knight she's taking up one square. When bob moves the knight, there will always be an even number of squares available. This means the 64th square will be taken up by bob. The only thing he has to make sure is to not get himself trapped without squares to move. With this information, you can deduct that bob can win, without the 4x2 rule.
I think this explanation is clearer biut less coloured..😂
are you kidding me you said my comment 10 months before mine XDDDD very nice thinking man i grant you 200 iq XD
Even if the properties of the board and game means that Bob always wins in the end, unless someone screws up before the last square is moved to, it is still possible for Bob to lose since he can also screw up. The solution in the video guarantees the win though, i.e. it guards against getting trapped. No matter what square Alice moves to, there will always be the other side of the "square pair" inside the region open for Bob. The terminology of saying "Bob can always win" is a bit misleading though.
“The only thing he has to make sure is to not get himself trapped without squares to move”. Yes, that is what the 4x2 method is for
That's not really a solution I'm afraid. It would be possible for Bob to have already blocked off the only squares available in some case, so though there are available spaces somewhere on the board he can't necessarily move to them if his strategy hasn't been correct.
The solution given here is possibly slightly more complex than it needs to be however. The 4*2 blocks are helpful to demonstrate a system where Bob has a unique move he should choose from any position Alice leaves him. Importantly every spot Alice can finish has a unique followup move from Bob and every spot Bob can move to has a unique position on the board that he moves there from. What Alice does and which sector she is in is at that point irrelevant, he has a defined move available for any square she leaves him on and that move is always available since she can't have left him on the trigger square for that move previously, thus if she has a legal move he always has his follow up move pre-defined and always wins.
I didn’t work out the 2x4 I just figured it would always be the second person winning because it would ultimately be an odd number of moves.
That is truly clever. I definitely wouldn’t have thought of that.
As presented, the proof that Bob can force a win is missing a step for completeness. The proof shows that Bob can force Alice to exit a 4x2 region, but does not examine what happens when an "Alice" move returns to a region in which Alice and Bob have already played. Since untouched regions and regions that have already seen paired Alice/Bob moves are not identical, the form of the proof requires an argument at the sub-region (graph color pair) level.
Note first that:
(1) Alice will always play on the same board color (black or white);
(2) Bob will always play on the opposite board color (white or black);
(3) each of the 4x2 regions contains four color pairs (green, teal, yellow, and purple); and
(4) a color pair within each region includes one square of each board color (green in a 4x2 region is one black square and one white square, teal in a 4x2 region is one black square and one white square, etc.).
Assuming Bob follows the strategy described, then for each 4x2 region, Alice might return up to three times.
Each time Alice returns to a 4x2 region, she must play to a graph coloring pair (green, teal, purple, or yellow) that was not previously exhausted by an Alice/Bob move pair.
When Alice does, Bob will always be able to play to the opposite board color (black/white) square of the same graph coloring color. That will both exhaust one of the graph coloring color pairs for the region and (returning us to the proof as presented) force Alice to move outside the 4x2 region on her next move.
Shawn Winnie going to a region they've already been doesn't change anything. Bob can do the exact same, going to the only possible spot in that 4x2, resulting in alice having the do the exact same thing, moving out of that 4x2?
Yoy are right someone with little knowlege in math like me might not understand the video but with your explanation everything is crystal clear thans!
No missing step , You just said it in a much more verbose fashion .......
I didn't reed
Very interesting and well explained, but good luck keeping track of which squares have already been used and which haven't.
This was interesting
Your videos have been so helpful to me and these are much manifest to resist in any way so easy peasy.
Duck. I thought Alice always wins, but her putting the knight on the board is her first move. If the chest piece was already there (randomly) and THAN Alice's first move was to move it, than Alice would always win.
yeah whoever goes first wins that’s it
my first thought on the problem was that it was a flawed game, given that your dealing with even numbers it to me meant that the winner was predetermined by who went first or second, very cool video to see other peoples thought processes.
I missed this guy.. idk y TH-cam stopped recommending him
Itachi best brother
Subscribe
I love you math problem videos, but I love your game theory videos a ton more!
Are there other channels that have game theory puzzles?
in the first move, 2 squares are covered so this means there can't be more than 63 moves, not 65 like you said at the end of the video
iCEW0LF Was thinking the same thing and started looking for others in the comments who had noticed that. He just got n+1 mixed up with n-1 :-) Thanks for confirming my suspicion.
The first move is placing the knight, so 1 square. Then each subsequent move adds 1 more square. You can do 64 legal moves. The 65th ends the game.
iCEW0LF both are moving the same knight
Alex Burns Oh, ok, gotcha; yeah, makes sense now
Well, it depends on what we call a move. It should be 65, as Alice places the piece (move 1). Bob moves (move 2). At move 64 all squares have been visited once. Move 65 then results in Alice losing, as no free squares are left.
hi, I have a similar but much harder chess problem for you. you fold the chess board in half so you play on 4*8 squares. you put all 32 chess pieces on the board and start to capture the pieces with one knight(the only moving piece). the starting square of the playing knight should be randomly chosen. The target of the game is to capture all the chess pieces. You can only capture a piece, you are not aloud to move on a square were you already moved. so technically you should capture all the pieces in 31 moves. I would much apreciate an answer
what if when the knight is placed allice moves it in the second square of that region
Dude Alice's first move is placing the knight
See it is simple
1)If alice moves the knight after placement means her squares get used later than Bob which according to theory means that alice wins
2)If you think that the placement sqaure is not booked then Bob can move back thus you contradict yourself(which i hope you don't (just to make sure u understand in the first go))
In your sense the first to move always wins
The same thing
How can you move 65 times when theres only 64 squares. It should be 63 moves, as the knight starts at a square and is not considered a move
But if you take a 4x4 there can be executed up to 4 moves. Ex.
(R4,C1)→ (R2,C2)
(R2,C2)→(R3,C4)
(R3,C4)→(R1,C3)
(R1,C3)→(R2,C1)
R=Row, C=Column
So I dont know if this is the way to prove it.
Also there is a thing called "Knights tour" where there a knight can go from any position and fill the entire board. Which means that there are 64 moves in including the act of putting the knight on the board. So without that there are 63 moves to be done so the one to go first always wins indeed.
Your post presents the following four moves:
1. (R4,C1) → (R2,C2)
2. (R2,C2) → (R3,C4)
3. (R3,C4) → (R1,C3)
4. (R1,C3) → (R2,C1)
After those four moves, we can certainly do ten more moves:
5. (R2,C1) → (R4,C2)
6. (R4,C2) → (R2,C3)
7. (R2,C3) → (R1,C1)
8. (R1,C1) → (R3,C2)
9. (R3,C2) → (R2,C4)
10. (R2,C4) → (R4,C3)
11. (R4,C3) → (R3,C1)
12. (R3,C1) → (R1,C2)
13. (R1,C2) → (R3,C3)
14. (R3,C3) → (R1,C4)
And now it's Bob's move, and since he can't move, he loses.
A lot of these older MYD videos are more like "check out this hard puzzle and watch the clever solution," rather than "solve this cool puzzle."
Bruuuuuh...
The add I just got...
*BRUUUUUUHHHH!!!*
*[COMMOOOON MY PEEEERIIOOOOOOOD!!!!]*
Took me 20 seconds to figure out, feels good man.
in short:
It is possible to divide the chessboard into pairs of squares, which are "L" apart. (trick that I've used in some other combinatorics problem, such as "how many knights can stand on the chessboard and not attack each other") Bob wins, because he always moves the knight to the second square from the pair, Alice just entered into, thus he always has a move and after his move, pair becomes unavailable.
After learning this, I am the new Bob in the town 😎
😂👍
*KING BOB!!!*
That's a fun game and challenging problem. I didn't solve it even though I knew about the "knight's tour". What this video lacked was a discussion of how one might come to the idea of breaking the board into 2x4 regions.
it's the only way to split the board in equal portions to which this rule of unique pairs applies. (of course you can swap 4x2 and 2x4). The rule also applies to 3x2 but you can't split the board into only 3x2s.
@@poro3246 there's no matching pair for the middle two squares of a 3x2 region.
Doesn’t this only take into account a game where bob goes first?
Bradley Hudson i think if alice go 1st and stayed on the 4x2 box. bob can win if he makes it to vertical box (2x4). haven't fully confirmed this. can anyone confirm?
I came up with the right answer, but with much less formal reasoning (but did not come up with an optimal strategy.)
There are an even number of squares that can be occupied.
The first player takes odd moves, the second player takes even moves.
It's possible to occupy every space on the board.
Bob wins by forcing an even move victory. Alice wins by forcing an odd move victory. There are more even move solutions than odd move solutions.
Since, there is no backtracking, Bob has more control over the sequence the knight proceeds through the board.
All Bob needs to do is prevent leaving the Knight in a location that leads to an odd turn victory.
The caveat is that I'm not 100% sure I've proven the board starts in an even turn victory solution.
It makes intuitive sense to me, and I find it difficult to imagine it could be wrong. But I'm unsatisfied with just "the longest game is this way, so it must be the default."
But ultimately, as long as that assumption is correct, the concept of Bob being able to maintain advantage should hold true.
Oh, this is a variation of the Knight's Tour, isn't it?
It's really not
Excellent explanation 👍😊🙏🏻
Thanks for your videos, Fresh Towel Locker.
I’m impressed that someone managed to get that into an email, that alone would stump me.
MY G I JUST GOT A 105 MINUTE LONG LEGO TRAILER ON THIS VIDEO WHAT THE ACTUAL HECK
Lego is love, lego is life
Well, it's same problem i did solved a 2 week ago from my math teacher. :) You did another way to solved mine was different. Keep learning, keep making this video!
Plz share your solution
In a video or something and send the link
Btw I think that bob losses if he choses to go to a différent 4x2 region
seems like a more accessible illustration of how the second person always gets to take the last square on the board since there is an even number of them
There's a similar problem with Queens instead of the Knights.
The 8-queen problem, did my final year project on a related problem.
Two things that do need to be kept in mind here is that it is relevant who actually makes the first knight move, as well as the fact that a knight's tour is possible. The knight's tour probably becomes less relevant if not irrelevant if the 4x2 theory is applied by both players, since I am unsure if knight's tours can be completed taking into consideration this condition.
Yes, there exists at least one tiling for which there exists at least one (open) Knight's Tour for which each even-numbered square lies in the same 4x2 region (or 2x4 region) as the previous odd-numbered square.
The tiling for which I found a solution is not the same tiling as in the video, though. Consider the following tiling (each tile given by two diagonally opposed "corner" squares):
[ A1/B4 ], [ A5/B8 ],
[ C1/F2 ], [ C3/D6 ], [ E3/F6 ], [ C7/F8 ]
[ G1/H4 ], [ G5/H8 ]
For this tiling, here is a Knight's Tour that also satisfies the algorithm that each pair of squares { #(2k-1), #(2k) } are in the same 4x2 tile (or 2x4 tile):
A8, B6, A5, B2, D1, F2, H1, G3, H5, G7, E8, C7, D5, C3, E4, F6,
H7, G5, H3, G1, E2, C1, A2, B4, A6, B8, D7, F8, E6, F4, D3, C5,
B7, A5, B3, A1, C2, E1, G2, H4, G6, H8, F7, D8, C6, D4, F3, E5,
G4, H2, F1, D2, B1, A3, B5, A7, C8, E7, G8, H6, F5, E3, C4, D6.
Here are the steps given in an 8-by-8 diagram (square #1 at A8, square #64 at D6):
+----+-----+-----+----+-----+-----+----+-----+
| 01 | 26 | 57 | 44 | 11 | 28 | 59 | 42 |
| 56 | 33 | 12 | 27 | 58 | 43 | 10 | 17 |
| 25 | 02 | 45 | 64 | 29 | 16 | 41 | 60 |
| 34 | 55 | 32 | 13 | 48 | 61 | 18 | 09 |
| 03 | 24 | 63 | 46 | 15 | 30 | 49 | 40 |
| 54 | 35 | 14 | 31 | 62 | 47 | 08 | 19 |
| 23 | 04 | 37 | 52 | 21 | 06 | 39 | 50 |
| 36 | 53 | 22 | 05 | 38 | 51 | 20 | 07 |
+----+-----+-----+----+-----+-----+----+-----+
I hope that helps.
Hey Presh, you inspire me to do a lot of things and I really enjoy every single video you upload. I’m a junior in high school and have never gotten less than an A in any subject on report cards and I really appreciate math (algebra and trigonometry so far, taking calculus next year) and I wanted to ask if you had any suggestions for becoming a mathematician or something like that. I’m not sure if you can contact me or anything but with your input I think I can get into an excellent college and be want I want to be.
Tyler Cenko look up khan academy on the we website/TH-cam. They teach a tonne of math topics
I echo what Scott said. Khan Academy is a great resource if you are a visual/auditory learner. As a student and Teacher, I've utilized Khan Academy to much benefit. You should also check out the free coursework offered by MIT. They literally have entire courses (lectures and exams) for you to use at your disposal.
JuditeTormentor any suggestions on “getting my name out there?” What should I do while I’m taking my last year in high school to try and make it to the college that I want? Is it strictly gpa and sat scores that let me go to a top college?
Tyler Cenko Send him an email, he will reply. I know because he replied to me within 48 hours. And I wish you good luck in math 😊
Along with Khan Academy, I recommend the 3blue1brown's and Eddie Woo's youtube channels.
What I would like to know, is how would one come up with this type of proof? What made you/someone try to limit themselves to 4x2 squares and why? I don't feel like I ever get any better at solving these types of riddles due to only receiving explanations rather than methods of analyzation.
One thing is to know the conclusion (that bob would win since the knight can go anywhere on the board), another is to be able to prove it.
A 4x2 (or 2x4) is selected because the chessboard can be divided into it equally, and because within a 4x2 for any square there is exactly one and only one other square in the same 4x2 section a knight can legally move to.
How do you come to solving the problem in that way? :O Who came up with that? ^^ And especially how?
Languste Well it's basically an easy to remember way of turning 64 squares into 32 pairs. And that ia what matters, the pair. As long as you have 32 pairs you can constantly pick the other of the pair and it will be imposible for A to find a square that does not have its pair left, because when it is A's turn, there are always only two option, either both of the pair are free, or neighter are free. This way B always has a move. It's a very elegant solution to the problem. The entire box thing is just an easy way for humans to remember, but any solution in which there are 32 pairs it would work.
It's probably easier to come up with the solution if you consider the 4x4 version of the chess board. If Bob doesn't stay on the same side, Bob can lose.
There's another cool puzzle that has a proof that similarly made me think "Wow, that's really neat but how did someone think of it?" in a numberphile video about pebbling a chessboard and freeing clones:
th-cam.com/video/lFQGSGsXbXE/w-d-xo.html
If you know about gametheory and nim then you will automatically try to reduce it to that.
Nice logic!!
My logic was that as there are only 64 squares and assuming both of them are playing optimally they will eventually run out of squares thus the one who is starting first will always lose.
Now that's what we call a math riddle, not things such as 2 + 2 * 2 = 8, nice video :)
2 + 2 * 2 = 6
no, it's 8, because 2+2 = 4 and times 2 = 8 :)
just trolling, after 5 years of math studies let's assume i know how it works :)
Which is why infix notation sucks and it should be written *,+,2,2,2 (or 2,2,2,+,*)
Pedmas rules. Multiplication comes before addition therefore making 6.
+Super Destroyer
If you apply the multiplication first, then you get 2+(2*2) -> 2+4 which is 6, not 8.
there is a neat little trick/puzzle where you have to visit each and every square once and not more with a knight and if you know the moves it does not matter where the knight starts
1:45 And that’s just a theory, a game theory.
Matthew Morcos lol
@MindYourDecisions Does the player who moves first have a winning strategy if the player who moves second makes a mistake on their first move ?
Yes
Actually, no. When Bob (the player who moves second, after Alice has placed the knight somewhere on the board as her first move) has made his first move and his first move doesn't correspond to the winning strategy in the video, then Bob can (and will) still win because he will still have many alternative winning strategies with which he can force a win.
Alice still cannot force a win when Bob's first move deviates from the video's winning strategy.
Great solution tricky question
what will happen if Bob moves the knight to new 4*2 region??
Then it's blunder
I had solved a variant of this problem. It asked if a knight on the chessboard can cover the entire chessboard in a series of moves. It was a programming question and the answer is yes. I have been since wondering if one can analytically prove that a solution exists and it is unique. The video helps orients me to think in graph theory terms. Thanks.
The principal: if Alice is able to move the knight to ANY of the 8 regions, Bob will always have a square in THAT region to move the knight to. This is because of the strategy Bob uses.
Alice places the knight = first move. Bob does the even moves and wins because there are 64 moves/squares.
Another thing that I wanna point out (this is unrelated to the puzzle) is that the colors match perfectly despite one seemingly lighter than the other. It is but another illusion.
I felt the no game no life vibes
You should clarify that the first square (the one alice places the knight on) can be revisited, as that changes the result. I for example, thought the winner would be alice because the starting square is "one it has been on before".
Me? I'm just here searching answers
I did not find a solution, but as Alice will always move to (or start at) white squares (and Bob will always move to black squares), I guessed Bob would win since Alice will run out of white squares before Bob runs out of black ones.
*Very good*
Very pretty .....
You should have mentioned that the example at 1:21 and that at 4:03 are different examples and that both move the same knight, because I had to explain both of these facts so many times in the comments section. It appears that John Allen Paulos is right when he speaks about the spread of innumeracy in his book "Innumeracy".
I don't think anything needs to be changed for the audio part. The explanation is crystal clear and surprisingly simple. However I am not a fan of slides showing every spoken word. I'd rather see interesting visual designs, such as chess pieces, boards or anything relevant to the topic.
For us that try to solve the problems it is alot easier to have the the rules showing in the slides.
Alfred Kjeller Sure, I definitely agree with you about that. The rules usually take a few words if you look at earlier videos.
Not everyone learns the same way you do sir.
Not all of us have audio turned on... I often listen to music while "reading videos".
Well Mr Pictor, some of us are Wordors.
Maybe i'm wrong (or i missed something) but you left out some info, that the original square the knight starts on can be visited again as you do that in the example.
For me "you can't visite a square again" implies the first position before people do a move is also one (which would implie the oposite result)
Not clear enough; bob cant trap alice, only visit all squares (optimaly), bob always wins
IU ER I guess the person who makes the first move always loses?
I played this game by moving both players myself and I managed to trap Alice in just 13 moves by each player.
Stop playing with Yourself and then touch the chess pieces .... You are gross .....
No, I played with a chessboard designed in the Paint of the Windows. I didn't touch any pieces. And why am I gross???
OK , it was an attempt at humor .... " playing with myself " is a metaphor for masturbation in English , I don't know if English is a second language for You ( if so , You speak it well ) or if You are "playing" with Me now but either way have a great life ..... ( and get a Girlfriend )
Okay, I have a big question.
Suppose, Bob doesn't know this trick and he takes it to a random square.
Alice plays another move and Bob again takes the knight to a random square.
Now is there any possible way for Alice to ensure that she wins the game? And, if there is, what are the first two pairs of moves (or N pairs of moves if it cannot be confirmed after only 2 pairs of moves)? And, obviously, what is the strategy?
You're overanalyzing.
Each move goes from either white to black, or black to white. If the Knights initial placement counts as a square that can't be landed on again, and if both players are playing optimally, the best strategy is to go first.
@@arthurmp3243 🤣🤣🤣👍
Presh forgot to expand out on what happens if Alice moves to a different 4x2 rectangle on her move, after moving out of the initial 4x2 rectangle. Alice could move in a few different directions on her second move. Bob can still win if he sees what Alice is up to, though.
he did explain that
*_BUT HEY, THATS JUST A THEORY, A GAME THEORY!_*
I just figured that there were an equal number of black and white tiles. That's 2*32. The knight can only move from one color to the other. That creates either a black-white or a white-black sequence that can be repeated up to 32 times. Even if, theoretically, the knight could move to every tile, the person to finish the 32nd sequence would be the winner, as there is no 65th tile to move the knight to.
This would only prove that Bob wins though, didn't exactly provide a strategy for him.
but you didn't consider Alice could win in less than 32 moves
Simple. The solution is to finish the video and re watch it with the solution in mind. Boom. Case closed.
Damn...that's smart. Never would have thought it in a million years
Mega FacePalm to this trick.... 😫😫😫😫😫😫😫😫
This is a special case of a harder problem, where you have a graph G and players move to vertices and the player who traps the other wins. Turns out the second player has a winning strategy if and only if the graph has a perfect matching, and it’s easy to check the knight’s graph has one.
Hello intellectuals how be ye
יוחנן דוד pretty good matey how bout t'you?
I'm doin swell!
מאה אחוז
The problem with this solution is that a knight doesn't have to move 2 squares first then one square. The knight can move 1 square then 2 squares. So using the grid from above the knight can move one square up to purple for example and then over 2 squares landed in another grid also putting the knight in a color square it didn't start in. I don't know if the outcome would be different as you can still use all the squares in the grid this way but after 2 turns Bob would be locked out of using the same color squares method cause he couldn't move back to yellow.
No no no no no. This is not a solution. You can move back into an old region and into a new square in that region from the adjacent region.
You can go through each region multiple times. Each time you eliminate another pair of squares. This happens until Alice gets blocked by adjacent regions that are saturated.
Because this is a new square in an old region, the matching square in the same region for Bob to move to is still available.
Let's call each pair of similarly-coloured squares a Bob-pair; these are connected by a Bob-move as Presh described. Before each of Alice's turns (including the initial placement of the knight), all of the Bob-pairs are either both-free or both-visited. Alice can't place/move the knight to a visited square, so she must put the knight on one square of a Bob-pair which has both squares free. This assures that Bob has a move (to the other square of the Bob-pair). Once Bob has moved the board is back in the state of having only both-free or both-visited Bob-pairs, so Alice is back where she started.
Eventually at Alice's turn all the Bob-pairs are both-visited so Alice has no moves. The game could end early by someone only having visited squares to move to, but since Bob always has a move, only Alice can be trapped.
The pairs of similarly coloured tiles GUARANTEES that Bob will always have a legal move. No matter what, Alice loses, as she will at some point not be able to.
Here is a counter example
Alice starts A8, bob counters B6, Alice is forced to the adjacent region C7, so bob counters D5, now Alice goes back to the first region B5.
Bob can no longer reach the same “colored” square that Alice is on.
I don't understand how you get Alice moving from B6 to C7 or D5 to B5, as neither of those are legal knight moves. Nevertheless this does not matter, the solution still works even if Alice can place the knight on any new square one each of her turns!
So you say Alice goes to B5. Well then Bob goes to A7, his matching square in the same rectangle. Now it is Alice's turn again. Where's the "counter" part of this counterexample?
Can we just appreciate this guy for emailing him that he likes his vid and telling a riddle