[OT] One for the weekend. (Updated: Answer posted!)

[BrowserUk]

Whilst waiting for my tea to brew, and thinking about my latest programming problem, I found myself 'walking the diagonals' on my tiled kitchen floor.

Walking the diagonals means starting in one corner of the rectangle and walking away at 45 degrees:

+---+---+---
| \ |   |
+---+---+---
|   | \ |
+---+---+---
|   |   | \

And when you hit the opposite edge, 'reflect' back in the other direction:

   | \ |   |   | / |
---+---+---+---+---+
   |   | \ | / |   |
   +---+---+---+---+---

Ditto at the ends:

|   | / |
+---+---+---
| / |   | / 
+---+---+---+
| \ | / |
+---+---+---+

The walk ends when you arrive directly into a corner. See the first diagram, but going the other way.

What I noticed was that starting in one corner, and continuing until I encountered another corner, I found myself in the diagonally opposite corner. When I drew a diagram on a post-it, I discovered that I had walked on every tile exactly once.

This was interesting, because I've been doing this 'walking the diagonals' when deep in thought -- a mindless repetitious activity that frees the mind for deeper things -- and recalled that in my old house kitchen, where the rectangle was the same width, but 2 tiles shorter, the tour also ended up in the opposite diagonal; also covered every tile exactly once and was 14 10 steps smaller.

How big is the rectangle in my current kitchen? Answer: 13 x 5.

(Other answers are possible, particularly 5x9 solution; but most of them would either have required me to use one of the terms: 'kitchenette' or 'galley' (as in train or ship) rather than kitchen :)

I was going to post code, but choroba's is much prettier; especially if you a) stop it considering even numbers; b) add a system 'cls'; or equivalent into the redraw loop; c) reduce the sleep time after the for loop to 1/10th second. Quite hypnotic once the sizes get up a bit (I start it at 21 and inc by 2).

Solution:

Old: 5x11

s/\/\/\/\/\
/\/\/\/\/\/ 
\/\/\/\/\/\  
/\/\/\/\/\/  
\/\/\/\/\/e  

New: 5x13

s/\/\/\/\/\/\
/\/\/\/\/\/\/
\/\/\/\/\/\/\
/\/\/\/\/\/\/
\/\/\/\/\/\/e

[choroba]

Before I went to bed, I only had a guess. I started with a pen and paper, and some maths:

              w * h = (w - 2) * h + 10
w * h - (w - 2) - h = 10
    h * (w - w + 2) = 10
                 2h = 10
                  h = 5

Now, we need to find the width. To be able to step on every tile, it must be coprime with the height, and moreover, width - 2 must be coprime with the height as well. I drew the simplest cases and extrapolated the observation to the following sequence: 3, 9, 11, 13, 19, 21, 23...

And when I got up, I verifyied the results with a Perl program. Specify a true command line argument to see the paths:

Read more... (2 kB)
Update: Spoiler tag removed.

[hdb]

<Reveal this spoiler or all in this thread>

[Anonymous Monk]

I opted for the "abuse regex" approach (because it's fun, and you can do it incrementally one s/// at a time until it works):

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1121552

use strict;
use warnings;

for my $y ( 1..25 )
  {
  local $_ = tile(5,$y);
  /1$/ and !/-/ and print "success  5,$y\n";
  }

sub tile
  {
  my ($w, $h) = @_;
  my $wm1 = $w - 1;
  local $_ = ( '-' x $w . "\n" ) x $h;
  s/-/1/;
  1 while  # print("$_\n"),
    s/1..{$w}\K-/1/s ||
    s/1\n.*\K-(?=\n)/2/ ||
    s/1(?=.*$)\K-/4/ ||
    s/2.{$wm1}\K-/2/s ||
    s/2.{$wm1}\n\K-/1/ ||
    s/-(?=2.*$)/3/ ||
    s/-(?=..{$w}3)/3/s ||
    s/^.*\K-(?=3)/2/ ||
    s/-(?=.{$wm1}\n3)/4/ ||
    s/-(?=.{$wm1}4)/4/s ||
    s/^.*4\K-/1/ ||
    s/-(?=.{$w}4\n)/3/s;

  return $_;
  }

which prints

success  5,1
success  5,3
success  5,7
success  5,9
success  5,11
success  5,13
success  5,17
success  5,19
success  5,21
success  5,23

Sure looks like multiple solutions exist.

[BrowserUk]

Just an attention getter: the answer has been posted.

[hdb]

Out of curiosity: what size are your tiles? Square or rectangular? If rectangular, which orientation?

[BrowserUk]

30 cm² which for the SI challenged is 3/16" under a foot.

[hdb]

Do you mean (30 cm)^2 or 5cm x 6cm?