Mdthbs

Loss of power when I remove item from the outlet

Dates on degrees don’t make sense – will people care?

Hot coffee brewing solutions for deep woods camping

What are Elsa's reasons for selecting the Holy Grail on behalf of Donovan?

How did Gollum enter Moria?

Boss wants someone else to lead a project based on the idea I presented to him

Concurrent normals conjecture

Can Ogre clerics use Purify Food and Drink on humanoid characters?

DBCC checkdb on tempdb

Understanding the reasoning of the woman who agreed with Shlomo to "cut the baby in half"

Why don't countries like Japan just print more money?

Why didn't the Cardassians take Terok Nor (Deep Space 9) with them when withdrawing from Bajor?

What's currently blocking the construction of the wall between Mexico and the US?

How does a blind passenger not die, if driver becomes unconscious

Did the CIA blow up a Siberian pipeline in 1982?

Why is it recommended to mix yogurt starter with a small amount of milk before adding to the entire batch?

RandomInteger with equal number of 1 and -1

Where's this swanky house and vineyard near a mountain?

How to remove this component from PCB

UK - Working without a contract. I resign and guy wants to sue me

Am I legally required to provide a (GPL licensed) source code even after a project is abandoned?

Is declining an undergraduate award which causes me discomfort appropriate?

Is there any difference between Т34ВМ1 and КМ1858ВМ1/3?

Is a single radon daughter atom in air a solid?

Walk a Crooked Path

Moving a pawn around on a chessboardThe Erasmus rook tourTwo rooks for Bobby FischerBlock the snakeCheckers with the devilExplore the square with 100 hopsCheckerboard tourHnefatafl - a lost ArtWarehouse Maximum CapacityColoring the Chess Board

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}

3

$begingroup$

Here is a $7times7$ board with three squares removed.

You walk a path from square to square (adjacent horizontally or vertically), without visiting any square more than once. What is the most crooked path you could walk?

• You may start on any square and end on any square.


• You do not need to visit every square.


• Find a path that has as many quarter turns as possible.

Here is a short example path:

This path has $7$ turns in it.

optimization checkerboard

share|improve this question

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

$endgroup$

add a comment | 

3

$begingroup$

Here is a $7times7$ board with three squares removed.

You walk a path from square to square (adjacent horizontally or vertically), without visiting any square more than once. What is the most crooked path you could walk?

• You may start on any square and end on any square.


• You do not need to visit every square.


• Find a path that has as many quarter turns as possible.

Here is a short example path:

This path has $7$ turns in it.

optimization checkerboard

share|improve this question

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

$endgroup$

add a comment | 

$begingroup$

Here is a $7times7$ board with three squares removed.

You walk a path from square to square (adjacent horizontally or vertically), without visiting any square more than once. What is the most crooked path you could walk?

• You may start on any square and end on any square.


• You do not need to visit every square.


• Find a path that has as many quarter turns as possible.

Here is a short example path:

This path has $7$ turns in it.

optimization checkerboard

share|improve this question

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

$endgroup$

share|improve this question

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

share|improve this question

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

asked 8 hours ago

Jaap ScherphuisJaap Scherphuis

17.6k13277

2 Answers
2

active

oldest

votes

2

$begingroup$

I will start the ball rolling with 36 corners

share|improve this answer

answered 8 hours ago

PenguinoPenguino

7,4022269

$endgroup$

add a comment | 

2

$begingroup$

I will immediately stop the ball rolling with this solution, and a proof of its optimality:

This solution has 37 turns.

First, an important fact:

Any row, or section of a row that is blocked on both sides, with an odd number of cells must have at least one non-turn. This is because every cell with a turn has exactly one horizontal (and one vertical) half-segment, but every horizontal half-segment connects to a partner in the same row.


This also shows that every row must have an even number of "turns plus horizontal endpoints". And of course, the same argument applies to columns, but replacing 'horizontal' with 'vertical'.

Now, analysing the grid:

The grid has 46 cells in it. I've marked four regions in different colors.


The blue cells cannot have turns in them; there are 2 of those.


There must be at least 1 non-turn in the red cells. (The only way to get both of the left ones to turn is to make a C shape, but then if the right ones both turn you've formed a tiny loop.)


The 1 yellow column, and each of the 4 purple columns, must each have at least one non-turn, by the "important fact" above.

This gives an upper bound of

46 - (2+1+1+4), or 38 cells. Is this achievable? If it is, all gray cells must be turns, and we must have 3 turns in the red region and 2 in the yellow. So that gives this:



The second through fifth rows of the purple region can be analysed as before: each must have at least one non-turn. And the top right cell in it must also be a non-turn. So 38 is not possible.

share|improve this answer

edited 3 hours ago

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  38 is possible. Your proof is correct until a mistake in constructing the last picture.
  $endgroup$
  – Jaap Scherphuis
  13 mins ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f85231%2fwalk-a-crooked-path%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

I will start the ball rolling with 36 corners

share|improve this answer

answered 8 hours ago

PenguinoPenguino

7,4022269

$endgroup$

add a comment | 

2

$begingroup$

I will start the ball rolling with 36 corners

share|improve this answer

answered 8 hours ago

PenguinoPenguino

7,4022269

$endgroup$

add a comment | 

$begingroup$

I will start the ball rolling with 36 corners

share|improve this answer

answered 8 hours ago

PenguinoPenguino

7,4022269

$endgroup$

share|improve this answer

answered 8 hours ago

PenguinoPenguino

7,4022269

answered 8 hours ago

PenguinoPenguino

7,4022269

answered 8 hours ago

PenguinoPenguino

7,4022269

2

$begingroup$

I will immediately stop the ball rolling with this solution, and a proof of its optimality:

This solution has 37 turns.

First, an important fact:

Any row, or section of a row that is blocked on both sides, with an odd number of cells must have at least one non-turn. This is because every cell with a turn has exactly one horizontal (and one vertical) half-segment, but every horizontal half-segment connects to a partner in the same row.


This also shows that every row must have an even number of "turns plus horizontal endpoints". And of course, the same argument applies to columns, but replacing 'horizontal' with 'vertical'.

Now, analysing the grid:

The grid has 46 cells in it. I've marked four regions in different colors.


The blue cells cannot have turns in them; there are 2 of those.


There must be at least 1 non-turn in the red cells. (The only way to get both of the left ones to turn is to make a C shape, but then if the right ones both turn you've formed a tiny loop.)


The 1 yellow column, and each of the 4 purple columns, must each have at least one non-turn, by the "important fact" above.

This gives an upper bound of

46 - (2+1+1+4), or 38 cells. Is this achievable? If it is, all gray cells must be turns, and we must have 3 turns in the red region and 2 in the yellow. So that gives this:



The second through fifth rows of the purple region can be analysed as before: each must have at least one non-turn. And the top right cell in it must also be a non-turn. So 38 is not possible.

share|improve this answer

edited 3 hours ago

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  38 is possible. Your proof is correct until a mistake in constructing the last picture.
  $endgroup$
  – Jaap Scherphuis
  13 mins ago
  

  
  
  
  

add a comment | 

2

$begingroup$

I will immediately stop the ball rolling with this solution, and a proof of its optimality:

This solution has 37 turns.

First, an important fact:

Any row, or section of a row that is blocked on both sides, with an odd number of cells must have at least one non-turn. This is because every cell with a turn has exactly one horizontal (and one vertical) half-segment, but every horizontal half-segment connects to a partner in the same row.


This also shows that every row must have an even number of "turns plus horizontal endpoints". And of course, the same argument applies to columns, but replacing 'horizontal' with 'vertical'.

Now, analysing the grid:

The grid has 46 cells in it. I've marked four regions in different colors.


The blue cells cannot have turns in them; there are 2 of those.


There must be at least 1 non-turn in the red cells. (The only way to get both of the left ones to turn is to make a C shape, but then if the right ones both turn you've formed a tiny loop.)


The 1 yellow column, and each of the 4 purple columns, must each have at least one non-turn, by the "important fact" above.

This gives an upper bound of

46 - (2+1+1+4), or 38 cells. Is this achievable? If it is, all gray cells must be turns, and we must have 3 turns in the red region and 2 in the yellow. So that gives this:



The second through fifth rows of the purple region can be analysed as before: each must have at least one non-turn. And the top right cell in it must also be a non-turn. So 38 is not possible.

share|improve this answer

edited 3 hours ago

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  38 is possible. Your proof is correct until a mistake in constructing the last picture.
  $endgroup$
  – Jaap Scherphuis
  13 mins ago
  

  
  
  
  

add a comment | 

$begingroup$

I will immediately stop the ball rolling with this solution, and a proof of its optimality:

This solution has 37 turns.

First, an important fact:

Any row, or section of a row that is blocked on both sides, with an odd number of cells must have at least one non-turn. This is because every cell with a turn has exactly one horizontal (and one vertical) half-segment, but every horizontal half-segment connects to a partner in the same row.


This also shows that every row must have an even number of "turns plus horizontal endpoints". And of course, the same argument applies to columns, but replacing 'horizontal' with 'vertical'.

Now, analysing the grid:

The grid has 46 cells in it. I've marked four regions in different colors.


The blue cells cannot have turns in them; there are 2 of those.


There must be at least 1 non-turn in the red cells. (The only way to get both of the left ones to turn is to make a C shape, but then if the right ones both turn you've formed a tiny loop.)


The 1 yellow column, and each of the 4 purple columns, must each have at least one non-turn, by the "important fact" above.

This gives an upper bound of

46 - (2+1+1+4), or 38 cells. Is this achievable? If it is, all gray cells must be turns, and we must have 3 turns in the red region and 2 in the yellow. So that gives this:



The second through fifth rows of the purple region can be analysed as before: each must have at least one non-turn. And the top right cell in it must also be a non-turn. So 38 is not possible.

share|improve this answer

edited 3 hours ago

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293

$endgroup$

share|improve this answer

edited 3 hours ago

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293

answered 3 hours ago

Deusovi♦Deusovi

67.2k7232293