Prime

Need a clarification. Are we allowed to escape by capturing? E.g., if there is a knight which is attaked by only one other knight, then that other knight escapes "check" by capturing the former.

Someone check my math and reasoning please. I'm sorry if the explanations are a little convoluted. I just woke up. The part of filling out the infinite sheet is nicely done. As far as the proof, my attention span is not good for more than 10 lines of text. But I happened to notice that your proof also relies on your particular method of filling out the sheet.

Ah... I remember now. That has a touch of nostalgia. I used to know those things. Long time ago, I wouldn't believe, I'd forget what it is. The O() we used to call "Order of". And binary search... I shall post an old nice programming puzzle for all computer programmers on the forum. If I find a simple way to formulate it. And if I can figure out myself, how to solve it.

That is a particlular method. Part (1) of the problem calls for a method of filling out the infinite sheet. Part (2) implies that we don't know how the infinie sheet was filled, what it started with, or if there was any sequence at all. For all we know, higher infinity forces were at work there, and all natural numbers were placed on the sheet at the same instant randomly. Among all those infinite arrangements, could there be one where difference between any 2 neighboring squares would not exceed some number "m"? Unless I misunderstood, the proof that you offer relies on ...

As far as Queen with Rooks, or Bishops -- there are several similar placements for the queen, giving the same result. Think of the postion in terms of lines and diagonals. With Queen and Knights, I can see only one other such placement -- Queen in the opposite corner. (Or you could put knights on the white squares and Queen at the end of black diagonal.) Either way, all those are symmetrical variations.

As far as Queen co-existing peacefully with other pieces: To sum up: 7 Rooks, 13 Bishops, 22 Knights.

Now, that knight placement is going to be hard to imporve upon! There I go making algorithms when it was as simple as:

I think I can improve the numbers just a bit. And offer an algorithm.

The one I haven't seen here yet:

1. I'm not sure what the notation O(n2) means. 2. The proof implies some method of filling out the infinite sheet, stating that there are no alternatives. What if the infinite sheet was already filled and we don't know how and in what sequence it was done?

I see that you see why statement (2) in the OP is true, and yet... I'm sorry for being picky, but I don't see where you have shown formally, that the arrangement you use for the proof is the minimal/maximal and no better can be found. Maybe, you have the proof, but I'm still going to check this topic for other formulations thereof. Until we get more efficient formulation, we shall consider your post#7 the proof as close as we can get.

I can see your reasoning with respect to the overall area, but I did not understand how the conclusion about neighboring squares followed. Note, changing directions as you move along the grid, does not have to break the "neighbor" relationship. Neighbors could be up, down, left, right. Although, I think your reasoning is in the very neighborhood of the solution/proof.

As I already stipulated (see post #5), "m" does not refer to any particular square. "m" is just randomly selected natural number. Sorry about misunderstanding. The statement of the problem in Russian was somewhat ambiguous, and I translated it as is.

Upon further reflection, I do see the proof. Here is an example of how the "procedure" increased number of intersecting lines: Suppose we had a set of (n-1) points, which was ordered in a non-intersecting way. Add two new points Bn and Gn. Connect them with a straight line. That line may intersect a number of segments. After just two steps of applying the procedure: 1) connecting B1-Gn and Bn-G1; 2) connecting B2-Gn and B1-G2; we created higher complexity of intersecting lines including the intersection of Bn-G1 and B1-G2. Nonetheless, THE TOTAL LENGTH OF ALL SEGMENTS HAS DECREASED. Another example, where applying the "procedure" does not create the minimal total segment length. It comes to the arrangement (2) on the picture, whereas minimal arrangement would be as shown in (3). Still, it does eliminate all intersections.

I'm afraid, I don't understand the proof. Especially the part where "every set of pairings can be shortenned". Was it proved? Consider: Where is the proof that after repeatedly applying the procedure as prescribed, we don't end up with different longer sets of crossed lines. Furthermore, why the points that we start with when applying the procedure can't come into cross-lined arrangements later on?

OK, I understand, we view Bug's advancement as a percentage of the total length of the string it traversed. Let's agree on the nomenclature. We'll use some of it as Foolonthehill suggested, except I want to change “d” (initial distance) to H (head start), so that I don't confuse it with “delta”: A = speed of the scooter. B = speed of the bug. H = initial distance of the scooter from the wall t = time elapsed. Your theory is that instantaneous speed of the bug in terms of ratio (percentage) of the string is B/(At+H), or slightly modified B/A(1/(t+H/A). (That is ratio of the bug's speed to the total length of the rubber band at time t). An integral of an instantaneous speed is the function for the distance traveled. Integrating, we obtain: B/A * ln(t+H/A) + C Now, plugging in the initial condition for the bug to be at zero point at t=0, we have: B/A * ln(H/A) + C = 0 and then C = B/A * ln(A/H) In that way our formula for the bug's distance in terms of the ratio (percentage) of the rubber band traversed becomes: B/A * ln(t+H/A) + B/A * ln(A/H). Simplifying: B/A * ln(t*A/H + 1) As we look for the total ratio of the string traversed equal to 1 (the whole string) then we solve the equation: B/A * ln(t*A/H + 1) = 1 Yielding: t = H/A * (e^(A/B) - 1) That is identical to what FonH had found, but the differential equation is simpler. Interesting point here: I thought I was joking when suggested that Bug could simply hang on to the rear fender if we didn't give Prof. T some headstart. But it turns out to be the case. If there was no head start, then it is impossible to decide which point of the rubber band the bug is initially on. So we should not give Prof. T such a huge handicap in the beginning. Give him something like 10^(-33) meters, and the bug will catch up in a matter of just few years.

Suppose, it is so. However, then you say: So you proved it for that specific arrangement. I don't see how that particular arrangement can be viewed as all possible arrangements. Your method of proof should go something like: "Suppose we had such an arrangement (without specifying what it was). Then this and that does not agree with that proposition which we hold true..." I am not sure that would be an easiest method of proof in this problem, but it would be interesting to see.

Technical correction: Any prime number, but 3 -- that is. For 3 we have to check separately: 32 + 26 = 35 -- not a prime. Everyting else is divisible by 3.

Well, I see that others have chimed in while I was typing. I'll submit anyway, but I think it's mostly covered. I accept your example of filling the infinite sheet. It will fill the entire sheet, all natural numbers will be used, and each number will occur just once. I am not so sure about your proof though... Seems like you picked a specific method for filling the sheet again, and proved that there can't be "maximum difference" for that particular arrangement.

This could be another application for Bayes’ Distribution, which Chuck Rampart used for a variation on Monty Hall problem. Anyway, my calculation from the total number of variations is as following:

I think, you misunderstood the question (2) . I admit, it is kind of ambiguous. I believe, what was meant there that you cannot have the "largest" finite difference between two neighboring squares. It means, pick any number as big as you want, and you can always find two adjacent squares, difference between which is equal, or bigger than that number.

What was part b? Very good thoughts, indeed! And amazing reaction time. Now a bit of CLARIFICATION: 1. Assume, you cannot see any edges of the infinite sheet. (It looks like you started filling numbers in the corner.) 2. Proof for the second part should be general -- not just for the specific arrangement that you found.

While organizing my bookshelf, I found an old issue of "Kvant" – a popular Russian science magazine. It has a regular section with entertaining math and physics problems for school students. I post here the part "a" of one problem that I liked: Each square of an infinite square-ruled sheet has a natural number written in it. a) Every number appears exactly once. 1) Show an example of such arrangement. 2) Prove that for any number m, there is always at least one pair of neighboring squares (sharing a side) such that the difference of their numbers is not less than m. The part "b" of the problem is marked with an "*" meaning it is of higher difficulty. So I am not going to show it here just yet. Unfortunately, I don't have the issue with the answer to this problem.

I did not understand the reasoning with respect to "So we can throw the bug's movement due to the rubber band's expansion out the window". If it were true, the bug wouldn't catch up to the scooter, and we already proved that it does. (See my post 15). The math appears incorrect. I don't see how the integral of 0.01/(t+1) is 0.01*log(t+1) + C. To verify the result of your integration, take a derivative of the resulting function: (0.01*log(t+1) +C)' = 0.01/((t+1)*ln10) -- not the same as your original function. However, the idea of MEASURING BUG'S MOVEMENT IN TERMS OF THE PERCENTAGE OF THE STRING TRAVERSED is very interesting. That may be the way to solve the problem without use of differential equations. Although, you still end up deriving a series approximating natural logarithm.

Sorry, I stumbled upon this one so late. Here is a SIMPLE PROOF: Any prime number P may be expressed as P=3*n + 1 or P=3*n+2. (Another way of saying prime gives a remainder of 2 or 1, when divided by 3). Thus P2 + 26 can be expressed as 9n2+6n+27 or 9n2+12n+30. Both expressions are wholly divisible by 3. Therefore, P2 + 26 is always divisible by 3. QED