Riddles, brain puzzles and mathematical problems

[Romulator]

I thought I had the answer, but if he can only make one cut, then I don't think I am correct.

Spoiler below!

We have a seven link chain - numbered 1 to 7.
We divide it into three groups, A, B and C.

Suppose the innkeeper will accept change.

On Day 1, Peter gives him Link 1 (Group A).
On Day 2, Peter gives him Links 2 and 3 (Group B).
But this would mean Peter's paying in advance and violating the rule of one link per day.
So he takes Link 1 back off the innkeeper.

Now Peter has five links and the innkeeper has two.

On Day 3, Peter gives him Link 1 (Group A) again.
On Day 4, Peter gives him Links 4 - 7 (Group C).
Once again, this would violate paying in advance and one link per day.
So he takes Groups A and B back (Links 1 - 3).

Now Peter has three links and the innkeeper has four.

On Day 5, Peter gives him Link 1 (Group A) again.
On Day 6, Peter gives him Links 2 - 3 (Group B).
Once again, this would violate paying in advance and one link per day.
So he takes Link 1 back off the innkeeper.

Now Peter has one link and the innkeeper has six.

So on Day 7, Peter just has to give the first link.

He minimises the damage done by making three cuts.
He gives one each day, and compensates by taking the required change back.
He does not pay in advance, nor late.
The innkeeper is happy. Peter is happy.
Peter can go home without paying money for a chain that probably costs $x*7.

[BAndrew]

A link can be both horizontal and vertical. The chain in this image has 7 links (not counting the two at the edge of the picture).

---

@Romulator
You are almost there! Peter can receive change as long as the inn keeper has enough links to give him. That doesn't count as paying in advance.

In fact you solved it. But he doesn't need to make three cuts to achieve this strategy. Figured out why?

PS: By one cut I mean one removal of a link.

[BAndrew]

By cutting/removing the third link then you have three parts A,B,C:
A: 1 link (the one you removed)
B: 2 links (on the left)
C: 4 links (on the right)

[BAndrew]

I know it is a long time, but I've got two new problems if anyone is interested.

Problem 1:
Consider this a game.
Starting from the square on the top left corner (marked as green) you must end up in the bottom right square (marked as red). The rules you must follow are the following:

• You can only move up, left, down or right.
  
• The number on the square is the exact number of moves you can make each time before stoping on a square. For example from the start you can go two steps on the right an land on the 3. From there you can go two steps down and one right and land on the 1, and so on.
  

Can you find a solution? What is the best solution? Or equivalently what is the route with the minimum number of steps?
If you feel like it, write an algorithm or a computer program that finds the best possible route (or routes).

Problem 2 (This actually is hard)

What is the average of the number of ways you can express a positive integer as the sum of the squares of two integers.

In other words: Let s>0 be an integer. In average, how many times will it satisfy:
n² + m² = s (where n,m are integers)

For example, if s = 2 we have:

1² + 1² = 2
(-1)² + (-1)² = 2
1² + (-1)² = 2
(-1)² + 1² = 2

So there are 4 ways for number 2.

[Romulator]

Problem 1:
Consider this a game.
Starting from the square on the top left corner (marked as green) you must end up in the bottom right square (marked as red). The rules you must follow are the following:

• You can only move up, left, down or right.
  
• The number on the square is the exact number of moves you can make each time before stoping on a square. For example from the start you can go two steps on the right an land on the 3. From there you can go two steps down and one right and land on the 1, and so on.
  

Can you find a solution? What is the best solution? Or equivalently what is the route with the minimum number of steps?
If you feel like it, write an algorithm or a computer program that finds the best possible route (or routes).

Probably a faster way, but in five minutes, I deduced;

Spoiler below!

2 right (land on 3)
3 down (land on 3)
2 right + 1 down (land on 4)
3 right + 1 down (land on 4)
4 right (land in red square)
Total: 16

2 minutes later, found;
2 right (land on 3)
3 right (land on 4)
1 left + 2 down + 1 right (land on 3)
3 down (land in red square)
Total: 12

First way I found, in prepping for Sociology class.

[BAndrew]

That's right, good job.
There is a "better" way though.

EDIT: Just noticed on your first solution, you go "outside" the table and circle back in (on step #4). I forgot to say that this is not allowed. If that were the case you would only need 6 steps:
1 up and 1 right (land in 4)
4 right (land in red square)

Your second solution is solid.

[FlawlessHappiness]

Spoiler below!

10

[BAndrew]

Congratulations @Flawless!

That is a possible solution with the least number of steps!

[Froge]

[BAndrew]

Let x be the number of rooks on the board.

If x = 0, then the claim is true trivially

If x > 0, then we are going to show that the claim is also true.

Let S be the largest possible set of mutually non-attacking rooks.
or S = {R1, R2, ..., Rk} where Ri (1≤i≤k) is a rook on the board.

The rooks selected are mutually non-attacking. The order the rooks are selected is random. Also, R1 ≠ R2 ≠ ... ≠ Rk.

|S| = k and this is the largest number of mutually non-attacking rooks.

We choose the rows/columns where these rooks ∈ S are located. By this choice we are going to show that all the rooks on the board are contained.

Assume to the contrary that there exists a rook (let it be r) on the board that isn't contained with the choice we made. Then this rook is by definition mutually non-attacking with every other rook ∈ S. That implies that S isn't the largest possible set of mutually attacking rooks, because by adding r to S , we get a new set U = {R1, R2, ..., Rk, r} where |U| = k+1 > k.
Contradiction!
Therefore, all the rooks are contained by this choice.
That completes the proof.