The maximum number of appearances of a word in a grid

DOI10.1080/00029890.2022.2040319zbMATH Open1487.05037arXiv2207.11273OpenAlexW4223919281MaRDI QIDQ5075871FDOQ5075871

Sam Spiro, Gregory Patchell

Publication date: 12 May 2022

Published in: The American Mathematical Monthly (Search for Journal in Brave)

Abstract: How can you fill a $3imes3$ grid with the letters A and M so that the word ``AMM appears as many times as possible in the grid? More generally, given a word $w$ of length $n$, how can you fill an $nimesn$ grid so that $w$ appears as many times as possible? We solve this problem exactly for several families of words, and we asymptotically solve this problem in higher-dimensional grids.

Full work available at URL: https://arxiv.org/abs/2207.11273

Recommendations

• scientific article; zbMATH DE number 7132810
• REPETITIONS, FULLNESS, AND UNIFORMITY IN TWO-DIMENSIONAL WORDS
• On the maximum number of cubic subwords in a word
• On the maximal number of cubic subwords in a string
• scientific article; zbMATH DE number 736284

zbMATH Keywords

diagonal Latin square

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Extremal combinatorics (05D99)

Cites Work

• Combinatorial Games
• A Census of Small Latin Hypercubes
• Packing lines in a hypercube
• Enumeration formulas for latin and frequency squares
• Has Every Latin Square of Order n a Partial Latin Transversal of Size n - 1?
• Title not available (Why is that?)
• The Hales-Jewett number is exponential: game-theoretic consequences

Cited In (2)

• Title not available (Why is that?)
• Cats in cubes

Uses Software

• OEIS

This page was built for publication: The maximum number of appearances of a word in a grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075871)