Logic contest Ending

The problem can be solved by a study of parity showing it is impossible to construct a knight tour for even mxm , followed by a construction argument showing it can be done for odd m.

I will devise the problem for simplicity and if you were disapoitned you didn't sovle it , don't be anyway because there is really no reason , being n ufnair problem even at IMO I think.

As you will see the problem is very complicated in the solution and you need to be attentive and next time anyway when I will recommend a problem I'll think twice before recommending it taking the writing of this very large proof anyway as sort of punishment for recommending such hard and annoying problem anyway haha.

I rushed my solution at the end , in part II. Basically you have to consider 2 cases and show a procedure of constructing and generating all tours anyway but it's a little complciated.

To solve this problem let's first use Sharky's observation to partially answer the problem for some of the cases.

Observe that the knight starts from a square of some color and then alternates the color of the squares on which it is passing in a sequence of colors for any number of moves. For purposes of rigor let's name a square which has the sum of it's columns and row on which it stands odd an odd square and similarly the squares which have the sum of the columns and rows on which it stands an even square. Observe that all black squares are even squares and all white squares are odd squares. Then taking an mxm chessboard with m being even the knight should travel between squares of the same parity meaning it requires an even number of steps to travel between those squares which since the length of the knight's tour including all squares without the initial one should be m^2-1 which is odd. Therefore this is leading to a contradiction and makes impossible to have a knight tour for even m anyway.

For odd m firstly let's consider the same parity test as it was used for any even m anyway. The 2 squares used by the knight for starting and ending the tour have the same parity so theoretically it should be possible. But just showing theoretically that this is satisfied is not enough as there could be also some other conditions which can make it impossible and more likely can't be all covered and synthesized in some abstract predication which because it proves itself as abstract doesn't cover the whole relevant information to use anyway. Therefore it can be said that what the test provided was a checking of a necessary but not sufficient condition and moreover that trying to obtain an understand just under the very use and guidance of reasoning by abstract terms is not sufficient , a better approach being therefore to try to solve this problem constructively i.e finding concrete working configuration.

Now that we have identified the flaw of the approach or at least it's main precarity ,it's being unsuitable for the purpose at hand , which btw is a general available precarity in many discrete mathematics problems and can be observed easily once remarked , let's try to apply that constructive approach anyway.

Firstly anyway what will be done will be to split the even cases into 2 separate cases for which we provide a construction procedure or algorithm that works for any case generally.

I. Proof of the first part , the existence of 4n+1 knight tours anyway.

I 1. Preliminary remarks.

Therefore let's prove constructively the existence of at least a knight tour for chessboards of the form 4n+1 firstly as this can be done easier.

To do this we will try to prove that from a square of size 4n+1 it can always be generated a square of size 4n+5 but this requires some preliminary remarks and terms.

For the purposes of the problem let's name a position (a,b) as stating the coordinates depending on anyway so to say the columns a and rows b anyway.

Now we will use a smart remark. This remark comes from asking the always asked constructive question so to say anyway of how to make such a tour which will take as you will see the form of a nice recursive algorithm that is will be found some procedure which can be applied and re-applied. But enough with such reflexive notes , the remark to be done is that for any 4k+1 chessboard whit the knight standing on the upper square and walking along the "border" of width of 2 squares the knight has a tour which covers all the squares of the "border".

A border of width 2 if you have trouble imagining is simply made from the first 2 layers of squares.

So you have something like the following border for m = 9 anyway.

1 30 17 44 3 32 19 46 5

56 43 2 31 18 45 4 33 20

29 16 6 47

42 55 21 34

15 28 48 7

54 41 35 22

27 14 8 49

40 53 12 25 38 51 10 23 36

13 26 39 52 11 24 37 50 9

This is sufficient to make the first observation of our generating procedure of chessboard which have a knight tour. Anyway observe that the tour ends in positions (1,2) haha.

Now , observe that in any such 4m+1 square the remaining square after the border anyway is completed or after the knight makes it's tour is a square of the form 4m-3. At the end of the knight's tour on the border of width 2 the knight will get to the first square of the square 4m-3 and as such , for any square of the form 4m+1 you can always create a "chain" of squares with will end in the next square of dimension 4m+1 - 2n for some n anyway.

So the chain will be that you start on the first square of the chessboard , complete the borderline , move on the first upper square of the next 4m+1-2 square and so on anyway. This applied procedure will end up with a chain which ends in the middle of the square considered but is important for our proof anyway.

Now , let's denote a square knight tour which ends on a square on the corners , (a , a) as anyway a type 1 square and a knight tour which ends on a (a-2 , a) square a type 2 square.

I 2. The proof of the first part anyway.

We will use induction to prove that we can always generate using the terms of borders , type 1 and type 2 square a 4n+5 square from a 4n+1 one anyway starting from m=5 anyway.

Before this let's show that there is possible to have a m = 5 type 1 square , which is what anyway we are looking for , a square which ends in the bottom corner anyway.

1s16 21 10 3

6 11 2 15 20

17 22 7 4 9

12 5 24 19 14

23 18 13 8 25 e

Anyway , now back to the proof.

For using induction start from the case of an m=5 type 2 square.

1 14 9 20 3

22 19 2 15 10

13 8 21 4 25 e

18 23 6 11 16

7 12 17 24 5m

Now , to construct the square of type 1 9x9 chessboard from the type 2 5x5 anyway chessboard let the type 2 chessboard be introduced in the 9x9 chessboard in center anyway.

1 30 17 44 3 32 19 46 5

56 43 2 31 18 45 4 33 20

29 16 -57 70 65 76 59- 6 47

42 55 -78 75 58 71 66- 21 34s

15 28 -69 64 77 60 81- 48 7

54 41 -74 79 62 67 72- 35 22

27 14 -63 68 73 80 61- 8 49

40 53 12 25 38 51 10 23 36

13 26 39 52 11 24 37 50 9

By the notion of the knight tour on the border it is known that there is a way to arrive at the 5x5 chessboard starting from the first square of the 9x9 chessboard.

Observe that because the ending of the 5x5 chessboard is at 81 and it is a direct path from the ending of the knight tour at 81 and the corner of 9x9 chessboard at 9 that path can be inverted without affecting the rest of the path until square 9 such that the ending square anyway will be on the bottom corner which is of interest for us anyway.

So again , I inverse the path the knight travells in the initial configuration upper starting from 9 such that the bottom corner will be on 81 and 9 on the place of 81 anyway.

This thing is possible becuse there is a direct link between squares 81 and 9 by square 8 in the first so to say configuration.

The resulting configuration applying the inversion is the following anyway.

1 60 73 46 3 58 71 44 5

34 47 2 59 72 45 4 57 70

61 74 33 20 25 14 31 6 43

48 35 12 15 32 19 24 69 56

75 62 21 26 13 30 9 42 7s

36 49 16 11 28 23 18 55 68

63 76 27 22 17 10 29 8 41

50 37 78 65 52 39 80 67 54

77 64 51 38 79 66 53 40 81

By induction the following procedure of making a a square of 4m+1 , isnerting a square of 4m+1-2 n the initial square , making a board width knight tour which will have the enxt move after it is finished on the corner of the 4m+1-2 type 2 square , inverting the path on which the knight lands on it's move with the corner works for all 4n+1 anyway.

So it has been proved right now that 4m+1 square work.

hat about the other case of 4m+3 anyway ?

II The second part of the proof for the cases 4m+3 anyway.

Before , here is also a special case namely m =7 so show it's possible to have a knight tour for a simple cute 7x7 chessboard anyway. Actually I let that to you haha.

The procedure used for obtaining all the 4m+3 is soemwhat similar but uses some other stuff such as rectangles anyway.

Observe that a rectangle of 4x3 contains a knight tour with extremites on diagonal , and the same way a knight tour for rectangles of the form 8x3 anyway.

Combining the 2 rectangles you can obtain any 4kx3 rectangles with knigh tours.

This fact gives therefore the conclusion that for any 4m+3 there can be cosntructed a border of width 3 made from such 4kx3 rectangles which have a knight tour.

Place also for the procedure of generating one type1 square of dimension 4m+1. Anyway invert as the next step the counting of the knight's tour.

So , by magic you obtain a 4m+3 and any 4m+3 whatsoever knight tour path anyway.

By proving 4n+1 , 4n+3 can be generated by the above procedure finally it was proved that the problem can be solved anyway.

Anyway.

@Prince Loomba Is the answer to problem 60 Infinite? I think any point from which u could go one mile south take a circle round the earth and come back u would come at same point

The north pole is one such place.

However consider the points LaTeX: $1+ \frac{1}{2\pi}$ away from the South Pole. Let any of those points be A and then go a mile south to a point B. When you go a mile east, you end up back at point B (you travelled once through every line of longitude). A mile north then brings you back to point A.

There are points still closer to the south pole such that going a mile east brings you through each line of longitude exactly twice, three times, or as many times as you want. Thus we have an LaTeX: $\text{infinite}$ number of concentric rings of LaTeX: $infinite$ numbers of points, and we can start a mile north of any of them.

the answer to question 60 is infinite!

Yes, it is worth buying, but it will take ages before it is worth it. Here is my argument:

First suppose that we only have $3$ boxes and they contain $n,0,1$ respectively. We claim that we can generate the contents $0,5·2^{n-2},0$, for $n ≥ 2$. We do this by the sequence

$\begin{array}{c c c c} n & 0 & 1 & \\ n-1 & 2 & 1 & A\\ n-1 & 0 & 5 & AA\\ n-2 & 5 & 0 & B\\ n-2 & 0 & 10 & AAAAA\\ n-3 & 10 & 0 & B \end{array}$

and so on. In addition we need the moves

$1 \, 1 \overset{A}{\to} 0 \, 3 \text{ and } 3 \, 1 \, 1 \overset{A}{\to} 2 \, 3 \, 1 \overset{AAA}{\to} 2 \, 0 \, 7 \overset{B}{\to} 1 \, 7 \, 0 \overset{AAAAAAA}{\to} 1 \, 0 \, 14 \overset{B}{\to} 0 \, 14 \, 0$

With this in mind we can generate

$\begin{array}{c c c c c c} 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 3 & 1 & 1 & 1 & 1\\ 0 & 0 & 14 & 0 & 1 & 1\\ 0 & 0 & 0 & 20480 & 0 & 1\\ 0 & 0 & 0 & 0 & 5 \cdot 2^{20478} & 0 \end{array}$

Which we can sell of for over a trillion.

The only way to make it worth it is to hook up this machine to a robot that presses the correct buttons every nanosecond (a billionth of a second). This way, the production of a trillion dollars would be done in under 20 minutes.

@Prince Loomba Answer to problem 57-Answer Is yes.it is a common puzzle I did before Go here for solution https://www.cs.cmu.edu/puzzle/solution20.pdf

@Prince Loomba Check out the Wikipedia article on knight tours for Problem 58.

Yes. It is possible.

Firstly, note that diagonals on a chessboard are the same colour. This means that a knight's move alternates between white and black. This means that it requires an even number of moves to stay on the same colour square as the original. But if $m$ is even, then this is not possible since there are only $m^2-1$ moves, which is odd. Thus, $m$ is not even.

I'll be working more on it but this is what I have so far.

I think its not possible.Of courese m cant be even.If m is odd then M^2-1 Will be number of squares left And then M^2-1/2 will be square he covers of opposite colour. And M^2+1/2 of same color Since both colours should be equal it isnt possible.

July 16.

Sept 14 Is the answer I suppose on which Cheryl has her birthday

And is date david was given june 20?

@Prince Loomba AM I RIGHT?

Am I right?

there are no such points as after travelling one mile south, then one mile east, then one mile north,you will be one mille away[east] in every case.

solution to prob 59- This is going to be a long explanation as the question is a difficult one. Forgive me if I get a little long winded at times. I just need to ensure that everyone can follow the logic and not lose track of any detail in this puzzle.

Bear these 3 things in mind:

1. Albert knew only the month of her birthday.

2. Bernard knew only the day of her birthday.

3. David was given one particular date from the list and all 3 of them knew this date has a different day and month from her birthday.

Let us analyse in order each statement that was made by Albert, Bernard and David. We will see how each sentence allows us to eliminate certain dates off the list until we are left with the correct one.

“Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know too.”

The first part of the sentence is of course unnecessary. We know that all Albert knows is the month of her birthday and there is more than one possible date for each month.

Now let’s look at the second part “…but I know that Bernard does not know too.” First we ask ourselves how Bernard can know the exact date of Cheryl’s birthday from just the day of her birthday. This is only possible if the day of Cheryl’s birthday has only one corresponding possible date from the list. It is easy to see that there are two dates in the list which corresponds to this: June 18 and May 19. If Cheryl’s birthday is one of these dates, Bernard would have gotten 18 or 19 as the day and he would know Cheryl’s birthday immediately because there is only one date in the list with 18 (or 19) as the day.

Albert can only be sure that “Bernard does not know Cheryl’s birthday too” if he was sure that the date is definitely not June 18 or May 19. How could he be so sure? He knows her birthday must definitely not be in May or June. In other words, Albert definitely must not have gotten the months May or June. So we eliminate all the dates corresponding to these two months.

Now we are left with: “Bernard: I did not know when Cheryl’s birthday is, and now I still don’t.”

Bernard would have deduced all the above and eliminated May and June off his list as well. However, despite having this new list, he still does not know Cheryl’s birthday. Following the same reasoning given earlier, there is only one possibility in the list below corresponding to each of the days 15, 17, and 22. If Cheryl’s birthday falls on any of the dates Jul 15, Aug 22 or Sep 17, Bernard would have gotten the days 15, 22 or 17 and would know for sure what her birthday was. Since he still didn’t know her birthday, we eliminate these dates off the list. Now left with- Albert: I still don’t know when Cheryl’s birthday is. Having said that, I am sure David still does not know too.”

Albert updated his list accordingly.

From the first part of the sentence, he still does not know when Cheryl’s birthday is. If Cheryl’s birthday falls on Jul 16. Albert would have gotten July as the month and because there is only one possible date corresponding to the month July in this updated list (see below) he would have known her birthday immediately. Since he still doesn’t know her birthday, we proceed to eliminate Jul 16 off the list as well.Now let’s look at the second part of Albert’s sentence, things get a little tricky here.

“Albert: …….. Having said that, I am sure David still does not know too.”

Let’s look at the updated list above, remember David updates the list to this one as well. Let us consider all the scenarios in which David would be able to know Cheryl’s birthday for sure:

1. David gets the date Sep 14 and since the only date in the list which has both a different month and day from Sep 14 is Aug 20, he knows Cheryl’s birthday is Aug 20.

2. David gets the date Sep 20 and since the only date in the list which has both a different month and day from Sep 20 is Aug 14, he knows Cheryl’s birthday is Aug 14.

If David has gotten any other date he would not have known what Cheryl’s birthday was. For example if he has gotten the date Aug 14, Cheryl’s birthday could have been on Sep 16 or Sep 20 and he could not have known for sure which one.

For Albert to be so sure that David still does not know Cheryl’s birthday. Albert must have known that David could not have gotten the date Sep 14 or Sep 20. How can he be so sure? Because Albert got the month September, this is Cheryl’s birth month and since the date given to David must have a different month from the actual birthday, the date that David was given could not have been in September.

Now we know that Albert must have gotten the month September and the birth month is definitely in September. “David: I knew neither the day nor the month right before Albert said his last sentence1, but after he did, now I know what month it is.”

Now let us go back to the list before Albert said his last sentence: David said that he did not know the month right before Albert said his last sentence, i.e. when his updated list looks like this one above. If David had gotten the month August in the date that Cheryl has given to him, he would be able to eliminate this month from the above list (since his date must have a different month from Cheryl’s birthday) and concluded that Cheryl’s birthday is in September. (even before listening to David’s last sentence)

Hence the date given to David must not be in August. Keep this in mind for now.

The second part of his sentence “…but after he did, now I know what month it is.” is redundant because as explained earlier, everyone was able to deduce after Albert’s last sentence that her birth month must be in September.

“Bernard: I did not know when Cheryl’s birthday is right before Albert said his last sentence, but after he did, now I know when Cheryl’s birthday is.”

Again we go back to the list before Albert said his last sentence: Following the same logic as explained in the first part of the solution, in the list above there is only one possible date corresponding to the day 16. If Cheryl’s birthday were in Sep 16, Bernard would have gotten the day 16 and would have known Cheryl’s birthday. However, he said that he still doesn’t know. So we eliminate this date off the list.

Together with the fact that we know Cheryl’s birthday must be in September. We are now only left with two possible dates for her birthday, as shown below.

Let’s look at the second part of the above sentence “…but after he did, now I know when Cheryl’s birthday is.” This sentence is redundant. Since Bernard can now narrow the birth month to September, he could of course use the day that Cheryl has given him to deduce the exact date of her birthday.

“David: Then I also know when Cheryl’s birthday is.”

David updates his list and now he is also only left with the two dates: Sep 14 and Sep 20. From these two dates he was able to eliminate one of them. This means that the day of the date Cheryl has given him must have been either a 14 (so he could eliminate Sep 20) or 20 (so he could eliminate Sep 14).

Recall that earlier I told you to keep in mind that the date given to David must not be in August.

Of course the date given to David must not be in September as well, since this is Cheryl’s birth month.

We conclude that the date given to David must have been in either May, June or July, and it must lie on either the day 14 or the day 20.

From the list (below), the only possible date that David must have gotten is Jun 20, after which he proceeds to eliminate Sep 20 from the list and concludes that Cheryl’s birthday is on Sep 14! So the answer is As I said

what is question 61?

The answer to question 57 is yes

the answer to 58 is yes it is possible for the knight to do it