Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

June 2022 - Challenge

<< May July >>


Counting odd polyominoes


A polyomino is a generalization of dominoes and Tetris shapes: a connected set of cells on the 2D grid. Dominoes consist of two cells while Tetris shapes consist of four; a general polyomino has n cells.
We consider two polyominoes to be distinct even if they can be rotated/reflected into one another. In this approach, there are 2 distinct domino shapes and 19 distinct Tetris shapes:

It is easy to check that the sequence of the number of polyominoes of size n is 1, 2, 6, 19, 63, 216, 760, 2725, 9910, 36446, 135268,... (sometimes polyominoes counted this way are called fixed to differentiate from cases where symmetry is taken into account).

Since polyominoes are sets of 2D grid elements, we can associate a coordinate (a,b) with every cell, and we can use this to define order on cells. We define two such orders:

  1. ("left-right and then down-up"): (a,b) \le_1 (c,d) \Leftrightarrow a<c \vee (a=c \wedge b\le d)

  2. ("down-up and then right-left"): (a,b) \le_2 (c,d) \Leftrightarrow b<d \vee (b=d \wedge a\ge c)

Given a polyomino, we can sort its cells according to one of the orders and number them accordingly. Define a function \pi(i)=j such that cell number i in the first numbering is number j in the second numbering.

For example:


It is easy to see that \pi is a permutation. Recall that permutations can be either odd or even, according to the number of 2-cycles in a 2-cycle decomposition of the permutation.

If we count only polyominoes giving rise to odd permutations, we can see the resulting sequence starts with 0, 1, 3, 11, 35, 108, 380, 1348, 5014, 18223,....

Your goal: Find the above sequence of odd polyominoes up to n=18.

A bonus "*" will be given for finding the sequence up to n=20 (or even larger values of n - and tell me how you did it!).


We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

 

Challenge: 01/06/2022 @ 11:30:00 AM EST
Solution: 04/07/2022 @ 12:00 PM EST
List Updated: 01/06/2022 @ 11:30 AM EST

People who answered correctly:

Paul Revenant (1/6/2022 7:56 PM IDT)
*Bert Dobbelaere (2/6/2022 7:13 AM IDT)
*Gareth Ma (2/6/2022 12:21 PM IDT)
*Uoti Urpala (2/6/2022 4:18 PM IDT)
*Phil Proudman (2/6/2022 9:39 PM IDT)
*Sanandan Swaminathan (3/6/2022 6:05 AM IDT)
*Dominik Reichl (3/6/2022 3:36 PM IDT)
*Vladimir Volevich (4/6/2022 12:12 AM IDT)
*Anders Kaseorg (4/6/2022 9:32 AM IDT)
Gary M. Gerken (4/6/2022 3:03 PM IDT)
*Andreas Stiller (4/6/2022 5:27 PM IDT)
*Alper Halbutogullari (4/6/2022 7:55 PM IDT)
*David Greer (4/6/2022 11:32 PM IDT)
*Lawrence Au (5/6/2022 7:23 AM IDT)
*John Tromp (5/6/2022 9:49 AM IDT)
*Bertram Felgenhauer (6/6/2022 12:29 AM IDT)
Lorenz Reichel (7/6/2022 7:18 AM IDT)
*Vladimir Volevich (7/6/2022 10:40 AM IDT)
*Paul Revenant (7/6/2022 12:57 PM IDT)
Franciraldo Cavalcante (9/6/2022 11:30 PM IDT)
*Daniel Chong Jyh Tar (10/6/2022 2:44 AM IDT)
Balakrishnan V (10/6/2022 7:43 AM IDT)
*Harald Bögeholz (12/6/2022 4:57 AM IDT)
Daniel Bitin (12/6/2022 11:50 AM IDT)
Ali Gurel (12/6/2022 4:43 PM IDT)
*Latchezar Christov (13/6/2022 11:50 AM IDT)
Reda Kebbaj (13/6/2022 8:20 PM IDT)
Graham Hemsley (15/6/2022 9:31 AM IDT)
*Dieter Beckerle (15/6/2022 1:55 PM IDT)
Daniel Johnson-Chyzhykov (24/6/2022 3:32 AM IDT)
Tim Walters (25/6/2022 2:43 AM IDT)
*Nyles Heise (27/6/2022 5:06 AM IDT)