Re: [math-fun] RE : RE : King walk on a square grid to write 0 to 100
On Wed, Jul 21, 2010 at 6:20 PM, Eric Angelini <Eric.Angelini@kntv.be>wrote:
I have 20 cells: 29378 78154 60291 54360 This might be improved, I guess.
Well, each digit must appear twice (because it all nine other digits as neighbors, and a single location has only eight neighbors). So there's no way to use fewer than 20 cells. The 4x5 rectangle has 4*4 + 3*5 + 4*6 = 55 neighboring pairs, and you need 45 of them. So it's possible that another arrangement of 20 cells could solve the puzzle with fewer than ten unneeded pairings, I suppose... --Michael
Best, E.
-------- Message d'origine-------- De: math-fun-bounces@mailman.xmission.com de la part de Robert Munafo Date: jeu. 22/07/2010 02:02 À: math-fun Objet : Re: [math-fun] RE : King walk on a square grid to write 0 to 100
Thanks for the clarification Eric. So it's a word search puzzle where you need to find the 10 single digits, plus 45 two-digit pairs where the two digits differ. The need for 45 pairs places a lower limit on the size of the grid, since each vertical, horizontal and diagonal line is one unique pair.
I thought about it for a bit, and I didn't improve on the 4x8 grid size but at least found a more orderly pattern. Here I have deliberately left redundant digits in (such as the upper-left 1) to show the pattern. Using a mono-space font, the lines represent pairs of adjacent digits:
1-2-3-4-5-6-7-8 |x|x|x|x|x|x|x| 4-5-6-7-8-9-0-1 |x|x|x|x|x|x|x| 8-9-0-1-2-3-4-5 |x|x|x|x|x|x|x| 1-2-3-4-5-6-7-8
On Wed, Jul 21, 2010 at 19:24, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Robert, sorry to be unclear, the "words" alone have to be found, not the path linking them. So you can find "0", of course, "1", "2", etc. And "10", "11", "12"... But for "19" (in my example) you have to add an extra digit "1"... Hope I'm more clear now, E.
What would be a "minimal king's-tour spelling matrix" showing all integers from 0 to 100?
Double digits can be accomodated by the rule that a cell may be counted twice.
The attempt below is for sure not minimal (minimal = quantity of cells
=
24, here):
9 2 3 4 7 8 9 4 7 8 0 5 3 . 0 6 1 2 9 1 . . 5 4 3 6 4 .
-- Robert Munafo -- mrob.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
I agree with Michael, I think you've got it. And your 4x5 grid is the most "compact" arrangement of 20 cells. Eight pairs of digits occur twice (01, 06, 15, 28, 29, 39, 45, 78) and the pair 19 occurs three times. I'd declare this solution to be at least as good as any other, unless we want to add some new criterion to rank one 20-cell solution against another. On Wed, Jul 21, 2010 at 21:20, Eric Angelini <Eric.Angelini@kntv.be> wrote:
I have 20 cells: 29378 78154 60291 54360 This might be improved, I guess. Best, E. [...]
On Wed, Jul 21, 2010 at 19:24, Eric Angelini <Eric.Angelini@kntv.be> wrote:
[...] the "words" alone have to be found, not the path linking them. So you can find "0", of course, "1", "2", etc. And "10", "11", "12"... But for "19" (in my example) you have to add an extra digit "1"...
What would be a "minimal king's-tour spelling matrix" showing all integers from 0 to 100?
Double digits can be accomodated by the rule that a cell may be counted twice.
The attempt below is for sure not minimal (minimal = quantity of cells 24, here):
9 2 3 4 7 8 9 4 7 8 0 5 3 . 0 6 1 2 9 1 . . 5 4 3 6 4 .
-- Robert Munafo -- mrob.com
Thanks, Michael, Robert and Seb for your remarks; two things: - a puzzle: the herunder "20-box" contains substrings from 0 to 126. Is there another such "20-box" con- taining more substrings? - what about a seq. for the OEIS in which we would have a(n) = "smallest quantity of cells such that the substrings from 0 (or 1?) to n are 'king-walk visible'" Best, E. -------- Message d'origine-------- De: math-fun-bounces@mailman.xmission.com de la part de Michael Kleber Date: jeu. 22/07/2010 03:43 À: math-fun Objet : Re: [math-fun] RE : RE : King walk on a square grid to write 0 to100 On Wed, Jul 21, 2010 at 6:20 PM, Eric Angelini <Eric.Angelini@kntv.be>wrote:
I have 20 cells: 29378 78154 60291 54360 This might be improved, I guess.
Well, each digit must appear twice (because it all nine other digits as neighbors, and a single location has only eight neighbors). So there's no way to use fewer than 20 cells. The 4x5 rectangle has 4*4 + 3*5 + 4*6 = 55 neighboring pairs, and you need 45 of them. So it's possible that another arrangement of 20 cells could solve the puzzle with fewer than ten unneeded pairings, I suppose... --Michael
Best, E.
-------- Message d'origine-------- De: math-fun-bounces@mailman.xmission.com de la part de Robert Munafo Date: jeu. 22/07/2010 02:02 À: math-fun Objet : Re: [math-fun] RE : King walk on a square grid to write 0 to 100
Thanks for the clarification Eric. So it's a word search puzzle where you need to find the 10 single digits, plus 45 two-digit pairs where the two digits differ. The need for 45 pairs places a lower limit on the size of the grid, since each vertical, horizontal and diagonal line is one unique pair.
I thought about it for a bit, and I didn't improve on the 4x8 grid size but at least found a more orderly pattern. Here I have deliberately left redundant digits in (such as the upper-left 1) to show the pattern. Using a mono-space font, the lines represent pairs of adjacent digits:
1-2-3-4-5-6-7-8 |x|x|x|x|x|x|x| 4-5-6-7-8-9-0-1 |x|x|x|x|x|x|x| 8-9-0-1-2-3-4-5 |x|x|x|x|x|x|x| 1-2-3-4-5-6-7-8
On Wed, Jul 21, 2010 at 19:24, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Robert, sorry to be unclear, the "words" alone have to be found, not the path linking them. So you can find "0", of course, "1", "2", etc. And "10", "11", "12"... But for "19" (in my example) you have to add an extra digit "1"... Hope I'm more clear now, E.
What would be a "minimal king's-tour spelling matrix" showing all integers from 0 to 100?
Double digits can be accomodated by the rule that a cell may be counted twice.
The attempt below is for sure not minimal (minimal = quantity of cells
=
24, here):
9 2 3 4 7 8 9 4 7 8 0 5 3 . 0 6 1 2 9 1 . . 5 4 3 6 4 .
-- Robert Munafo -- mrob.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Eric Angelini -
Michael Kleber -
Robert Munafo -
Xeipon