Problem of the Month (March 2015)

Consider putting the letters A and B on a square grid so that each A is adjacent to exactly m B's, and each B is adjacent to exactly n A's. ("Adjacent" means horizontally, vertically, or diagonally adjacent.) What are the smallest arrangements that work, for various values of m and n? ("Smallest" means smallest number of letters, or in the smallest bounding box.) We can extend this problem to A's touching m B's, B's touching n C's, and C's touching p A's, or to even more letters.

We can also use other definitions of adjacent. Instead of king moves, we could use moves of another piece with 8 symmetric moves: a knight, congo elephant (which moves 1 or 2 squares horizontally or vertically), phoenix (which moves 1 square horizontally or vertically or 2 squares diagonally), frog (which moves 3 squares horizontally or vertically or 1 square diagonally), or zebra (which moves 2 squares horizontally or vertically, and 3 squares in a perpendicular direction).

ANSWERS

Contributors this month include Bryce Herdt, Maurizio Morandi, Joe DeVincentis, George Sicherman, and Johannes Waldmann.

The smallest known configurations are shown below.

2 Letters, King Adjacency
m → n12345678
1
AB
ABA
AB
AA
ABA
AA
ABA
AAA
A
ABA
AAA
AA
ABA
AAA
AAA
ABA
AAA
2
AB
AB
ABA
AB
ABA
ABA
A
ABABA
BAAAB
AAA AAA
BAAAB
ABABA
A
(Joe DeVincentis)
(Joe DeVincentis)
3
ABAB
BB ABA
AA B
B AA
ABA BB
BABA
(George Sicherman)
ABA
BABAB
AA AA
BB BB
AA AA
BABAB
ABA

(Joe DeVincentis)
(Joe DeVincentis)
4
(Joe DeVincentis)
(Joe DeVincentis)
(Joe DeVincentis)

3 Letters, King Adjacency
1 → m → n1234567
1
AC
B
AB
AC
AB
ACA
ABA
ACA
AAA
BCCB
AAA
(George Sicherman)
AAAA
BCCB
AAAA
(George Sicherman)
ABAAA
ACACB
AAAAAA
BCACA
AAABA
(George Sicherman)
2
C
ABA
C
(George Sicherman)
AC
ABA
CA
ACA
ABA
ACA
AAAA
ABCCBA
ACAACA
ACAACA
ABCCBA
AAAA
shown here
(Johannes Waldmann)
(Joe DeVincentis)
3
ACA
CBC
A
A
CBCAA
AACBC
A
(George Sicherman)
AAA
CBCAA
AACBC
AAA
(George Sicherman) 		shown here
(Johannes Waldmann) 		?
(Joe DeVincentis)
4
ACA
CBC
ACA
CA
ABA
ACCC
CBCABA
AACCC
ABA
CA
(Johannes Waldmann)
(Johannes Waldmann) 		?
(Joe DeVincentis)
(Joe DeVincentis)
5
ACCCCA
CBAABC
ACCCCA
(George Sicherman) 		shown here
(Johannes Waldmann) 		2 → m → n234
6
CAC CAC
ABCACBA
CCCBCCC
ABCACBA
CAC CAC
(Johannes Waldmann) 		? 2
CAC
BAB
CAC
ACACA
BBABB
ACACA
ABBA
BCACACB
ACABACA
BCABCAB
ACABACA
BCACACB
ABBA
(Johannes Waldmann)
7
(Joe DeVincentis)
(Joe DeVincentis) 		3
A B A B C B C
C B C C A C A A A
A A C B A C C B C B
C B A A B C A C C A
A C C A A C B A A B C
B C B C C A B C A A
A A B C A C C B C
A B A B A
C A C
(Johannes Waldmann) 		?

Maurizio Morandi pointed out that the 2 letter knight adjacency problem had been studied in the February 2007 Math Magic problem, though there the point was the smallest box, not the smallest number of pieces.

2 Letters, Knight Adjacency
m → n12345678
1
A
B
A
B
A
B
A
A A
B
A A
A A
A
B
A A
A A
A A
B
A A
A A
A
A A
B
A A
A A
A A
A A
B
A A
A A
2
A
B B
A
A
ABA
B BA
ABA
A A
A
B B B
A
A A
(George Sicherman)
A A
ABA
AB BA
ABA
A A
A A A
ABA
AB BA
ABA
A A A
?
3
A
B B
AB
A A
B
A A
ABA
B B B B
ABA
A A
shown here
(Johannes Waldmann) 		?
4
B
A A
ABA
B B B B
ABA
A A
B
shown here
(Johannes Waldmann)

3 Letters, Knight Adjacency
1 → m → n1234567
1
BB
AA
CC
AA
BB
CC
AA
(George Sicherman)
AB BA
CC
AB BA
AA
(George Sicherman)
BB
AA AA
CC
AA AA
BB
BBBB
AAAA
AACCAA
AACCAA
AAAA
BBBB
BBBB
AAAAAA
AACCAA
AACCAA
AAAAAA
BBBB
?
2
AC
AA CA
BB
AC AA
CA
(George Sicherman)
A A
C C
B A C C A B
A C C A
A B B A
A A A A
C C
(Johannes Waldmann)
A
A A A B
A A C C
A A B B C A A
A A C B B A A
C C A A
B A A A
A
(Johannes Waldmann)
(Johannes Waldmann) 		? ?
3
AA
CC CC
BB
AA AA
CC
(George Sicherman)
A A
A A A A
C C C B C
B C A B B C
A B B A C A A
A A C C C B A
C A A C A B
B B C A B A
A C C
A A A A
(Johannes Waldmann)
(Johannes Waldmann) 		? ? ?
4
A A C
C A C C
A A B B A A
A C B B C A
C C A C C C
A A C
(Johannes Waldmann)
(Johannes Waldmann) 		2 → m → n234
5
(Johannes Waldmann) 		? 2
A A
B A A B
B C C B
A B C C B A
B C C B
B A A B
A A
(Johannes Waldmann)
AA A
A CCC
BBBBAB
BAAAAB
AACCBCC
AACCBCC
BAAAAB
BBBBAB
A CCC
AA A
(Johannes Waldmann)
(Johannes Waldmann)

2 Letters, Phoenix Adjacency
m → n12345678
1
AB
ABA
ABA
A
A
ABA
A
ABA
A
A A
A
ABA
A
A A
A
A
ABA
A
A A
A A
A
ABA
A
A A
2
AB
BA
BAAB
A A
BAAB
(George Sicherman)
A A
BAAB
ABBA
AA
(George Sicherman)
A
ABABA
BAAAB
AAA AAA
BAAAB
ABABA
A
(Joe DeVincentis)
(Johannes Waldmann)
(Joe DeVincentis)
3
BA
AB
AB
BA
A
BA
BA BA
AB AB
AB
A
? ?
(Joe DeVincentis)
4
AB
BA
BA BA
AB AB
AB
BA
(Joe DeVincentis) 		?
(Joe DeVincentis)
(Joe DeVincentis)

3 Letters, Phoenix Adjacency
1 → m → n123456
1
ABC
CBA
(Bryce Herdt)
ABCA
 
ABCA
(George Sicherman)
AA
AACBA
BC
AACB
(George Sicherman)
A A
AB BA
AC CA
ACA
ABA
(George Sicherman)
A A
ABBBA
ACACA
ACACA
ABAA
A B
(George Sicherman)
(Johannes Waldmann)
2
ABCA
CAAB
BAAC
ACBA
(Bryce Herdt)
(Johannes Waldmann)
(Johannes Waldmann)
(Johannes Waldmann) 		?
3
AACAA
CBCBC
BCBCB
AAAAA
(George Sicherman)
(Johannes Waldmann) 		shown here
(Johannes Waldmann) 		? ?
4
(Johannes Waldmann)
(Johannes Waldmann) 		2 → m → n23
5
(Johannes Waldmann) 		? 2
(Johannes Waldmann)
(Johannes Waldmann)

2 Letters, Frog Adjacency
m → n12345678
1
A
B
A A
B
A
B
A A
A A
B
A A
A A
B A
A A
A A
A B A
A A
A
 
A A
A B A
A A
A
 
A A
A B A
A A
 
A
2
B
A A
B
ABABA
ABABA
(George Sicherman)
A
ABABA
ABABA
A
(George Sicherman)
(Johannes Waldmann)
(Johannes Waldmann)
(Joe DeVincentis)
3
B A
A AB B
B A
A
A AB B
B A
A B
B BA A
A

(Johannes Waldmann) 		?
(Joe DeVincentis)
4
B A
A AB B
B A
A B
B BA A
A B

(Johannes Waldmann)
(Joe DeVincentis)
(Joe DeVincentis)

3 Letters, Frog Adjacency
1 → m → n1234567
1
A B
CC
B A
(Bryce Herdt)
A A
B CC B
A A
A B
A C B
A B
B A
B C A
B A
(George Sicherman)
A AB 
 CABA
 CA A
A AC 
AB CA
 BA A
(George Sicherman)
(Johannes Waldmann)
(Johannes Waldmann) 		?
2
A A
C AB A
B C
B C
A CA B
A A
(George Sicherman)
(Johannes Waldmann)
(Johannes Waldmann) 		? ? ?
3
(Johannes Waldmann)
(Johannes Waldmann) 		? ? ? ?
4
(Johannes Waldmann) 		? 2 → m → n234
5 ? ? 2
(Johannes Waldmann)
(Johannes Waldmann) 		shown here
(Johannes Waldmann)

2 Letters, Congo Elephant Adjacency
m → n12345678
1
AB
ABA
ABAA
AABAA
AABAA
A
A
AABAA
A
A
AABAA
A
A
A
A
AABAA
A
A
2
AB
BA
ABABA
BAAAB
(George Sicherman)
AAB
ABA
BAA

(Johannes Waldmann)
AABAABAA
ABAAAABA
BAAAAAAB
AAABBAAA
AAABBAAA
BAAAAAAB
ABAAAABA
AABAABAA
(George Sicherman)
3
BAAB
ABBA
(George Sicherman)
BAA
ABBA
ABBA
AAB
?
(Joe DeVincentis)
4
BAAB
ABBA
ABBA
BAAB

(Joe DeVincentis)
(Joe DeVincentis)

3 Letters, Congo Elephant Adjacency
1 → m → n1234567
1
ABC
ABCA
A
B
ABCA
A
B
ABCA
A
A B
AACBA
ABCAA
B A
(George Sicherman)
A
A B
AACBA
ABCAA
B A
A
(George Sicherman) 		?
2
A
ABCA
C
A
(George Sicherman)
ACBA
ABCA
AA
AA
ACBA
ABCA
AA

(Johannes Waldmann) 		? ?
3
ACBCA
AA
ACBCA
(George Sicherman)
 AA 
ABCA
ACBA
ACBA
ABCA
 AA 
(George Sicherman)
(Johannes Waldmann) 		? ? ?
4
CBAC
ACCB
BCCA
CABC
(Bryce Herdt)
(Johannes Waldmann) 		2 → m → n234
5
(Johannes Waldmann) 		shown here
(Johannes Waldmann) 		2
CAB
ABC
BCA
(Bryce Herdt)
 ABCA
ABCAB
BCA C
CA  A
ABCAB
(George Sicherman)
(Johannes Waldmann)
6 shown here
(Johannes Waldmann) 		? 3
(Johannes Waldmann) 		?

2 Letters, Zebra Adjacency
m → n12345678
1
A
 
B
A
A
 
B
A A
A
 
B
A A
A A
 
B
A A
A A
 
B
 
A
A A
A A
 
B
 
A A
A A
A A
 
B
 
A A
A
A A
A A
 
B
 
A A
A A
2
A
 
B B
 
A
A
A A
B
B B
B
A A
A
(Bryce Herdt)
A A
A A
B
B B
B
A A
A A
(Bryce Herdt)
A A A A
A
B B
B B
A A A A
A A
A A A A
B B
B B
A
A A A A
(Johannes Waldmann)
A
A A A A
A
B B
B B
A A A A
A A A A
A A A A
B B
B B
A
A A A A
A
(Johannes Waldmann) 		?
3
A
 
B B
B
  A
A A
 
B
(Bryce Herdt)
A A
  A A
B
B B B B
B
  A A
A A
(Bryce Herdt) 		shown here
(Johannes Waldmann) 		?
4
B
 
A A
  A A
B
B B B B
B
  A A
A A
 
B
(Bryce Herdt) 		shown here
(Johannes Waldmann)

3 Letters, Zebra Adjacency
1 → m → n12345
1
B C
A
A
C B
(Bryce Herdt)
A
 
B C
A
A
C B
 
A
BB
B
AA
AC
 
CA
AA
B
BB
(George Sicherman)
A A
A A
AAB
A AAC B B
AA A CA
B C CBA
B BCA
A C A A
A A AA
A B A
(Johannes Waldmann)
A A A A
A A
A B B B
A A A A C C A
A A A A B B A
B A B C C A A B A
C B B B A
A B A C C A A B
A A A B A A
A A A A A
A A
(Johannes Waldmann)
2
C
 
B A
A
A C
A A B
 
C C A
A C C
 
B A A
C A
A
A B
 
C
A C
A A A C A A
A A A A B A
A B C C A A
C A C B C B A C
A A B B C C A
A A B C B B B A
A B C B C A
A C C A A A
B A A A A
A C A A
(Johannes Waldmann)
(Johannes Waldmann) 		?
3
C A A
AC
A B A A A
AC B C
CAC BAC C A
CA A CCB
C CB CA
ABA C B A
A C AA
A AAC
CC
(Johannes Waldmann)
(Johannes Waldmann) 		2 → m → n2
4
(Johannes Waldmann) 		? 2
(Johannes Waldmann)

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 3/1/15.