The CT scan puzzle
Tonight's idea
A CT scanner sends thin X-ray beams straight through you, from hundreds of directions. Each beam is weakened by everything on its line, so it reports, roughly, one total for the whole line. From a great many of these totals, a computer rebuilds a picture of the inside.
Tonight's toy model is a small grid of hidden whole numbers, each 0 or more. You are told only totals along lines: rows, columns and diagonals. Going forwards is easy: given the grid, add up. Going backwards, from the totals to the grid, is called an inverse problem.
An inverse problem asks: from the measurements, what was the hidden cause? Two things can go wrong. Different grids can give the same totals, and one wrong reading can spoil several squares.
Watch one: six grids, one answer
A 2 by 2 grid hides four numbers. Row totals: 5 (top), 9 (bottom). Column totals: 6 (left), 8 (right).
Try a top-left number, say 0. The top row forces top-right to be 5. The left column forces bottom-left to be 6. The bottom row then forces bottom-right to be 3, and the right column agrees: \(5 + 3 = 8\). The top-left number can be 0, 1, 2, 3, 4 or 5, and each choice forces the other three squares in the same way.
So rows and columns leave six possible grids. Step from any grid to the next: the squares change by \(+1, -1\) on top and \(-1, +1\) below. Every row and every column gets one \(+1\) and one \(-1\), so no row or column total moves. Call this the hidden swap.
Now add one more beam: the diagonal from top-left to bottom-right has total 7. The six grids have diagonal totals 3, 5, 7, 9, 11 and 13, all different. Only the third grid fits: 2, 3 on top and 4, 5 below.
Your turn
- A 2 by 2 grid of whole numbers, each 0 or more, has row totals 7 (top) and 3 (bottom), and column totals 4 (left) and 6 (right). Find every grid that fits. Careful: not every top-left number works. One more beam says the diagonal from top-left to bottom-right totals 5. Which grid is it?
- A scanner measured 12 lines through a hidden 3 by 3 grid: 3 rows, 3 columns, 2 long diagonals, and 4 short rays that each clip one corner. A corner ray crosses one square only, so those four squares are filled in. Find the other five. You will not need every total. Use the spare ones to check your grid.
Row totals on the right, column totals underneath. Diagonals: 15 runs down to the right, 9 down to the left. - Now suppose one reading in question 2 was wrong: the top-left corner ray says 5, not 4. Nothing else changes. Rebuild the grid: top and bottom rows, left and right columns, then the middle row. How many squares differ from question 2, and by how much? Which spare totals now fail?
- In a sentence or two each: why is a scanner that only fired beams along rows and columns not good enough? And why is it useful to take more readings than you strictly need?
Stretch: a pattern the long diagonals miss
Drop the four corner rays from question 2. Keep the other 8 totals. Here is a pattern of changes.
\[\begin{array}{|c|c|c|}\hline +1 & -1 & 0 \\ \hline -1 & 0 & +1 \\ \hline 0 & +1 & -1 \\ \hline\end{array}\]Check that its 8 totals are all 0. Add it, square by square, to your answer to question 2. Why does the new grid have the same 8 totals? Which corner rays would tell the two grids apart?
Answers
- Call the top-left number \(t\). The top row forces top-right to be \(7 - t\), the left column forces bottom-left to be \(4 - t\), and the bottom row forces bottom-right to be \(3 - (4 - t) = t - 1\). Nothing may be below 0, so \(t\) is at least 1 and at most 4. That gives four grids: 1, 6 over 3, 0; then 2, 5 over 2, 1; then 3, 4 over 1, 2; then 4, 3 over 0, 3. Their diagonals total 1, 3, 5 and 7. Only the third has diagonal 5, so the grid is 3, 4 on top and 1, 2 below.
- One way. Top row: \(8 - 4 - 3 = 1\). Bottom row: \(10 - 1 - 6 = 3\). Left column: \(7 - 4 - 1 = 2\). Right column: \(11 - 3 - 6 = 2\). Middle row: \(9 - 2 - 2 = 5\). The grid has rows 4, 1, 3 then 2, 5, 2 then 1, 3, 6. Checks with the spare totals: middle column \(1 + 5 + 3 = 9\), one diagonal \(4 + 5 + 6 = 15\), the other \(3 + 5 + 1 = 9\). All three agree. Each step was forced, so this is the only grid that fits.
- Top row: \(8 - 5 - 3 = 0\). Bottom row: 3, as before. Left column: \(7 - 5 - 1 = 1\). Right column: 2, as before. Middle row: \(9 - 1 - 2 = 6\). The rebuilt grid has rows 5, 0, 3 then 1, 6, 2 then 1, 3, 6. Four squares differ, each by 1: \(+1, -1\) above and \(-1, +1\) below. One reading off by 1 has spread into a hidden swap. The middle column still totals \(0 + 6 + 3 = 9\), because a hidden swap never changes a row or column total. But the long diagonals give \(5 + 6 + 6 = 17\), not 15, and \(3 + 6 + 1 = 10\), not 9. Both diagonal checks fail, so you know a reading is wrong somewhere. No grid fits all twelve of these readings.
- Rows and columns are just two directions, and a hidden swap changes the grid without changing any row or column total. So many different insides would give the same readings (six in the worked example). The right and wrong grids of question 3 share all six row and column totals, and a computer count finds 1,314 grids of whole numbers, each 0 or more, that do. Beams from other angles cross the swapped squares differently and tell the grids apart. Extra readings are a check: in question 3 the spare totals showed that something had gone wrong. Real readings are never perfect, so real scanners take far more than the bare minimum. In a real scan each total is an integral: a sum, along the line, of very many tiny pieces.
Stretch. The pattern's rows total \(1 - 1 + 0\), \(-1 + 0 + 1\) and \(0 + 1 - 1\), all 0. Its columns are the same three sums. Its long diagonals are \(1 + 0 - 1 = 0\) and \(0 + 0 + 0 = 0\). Adding it to the grid from question 2 gives rows 5, 0, 3 then 1, 5, 3 then 1, 4, 5. Each total of the new grid is the old total plus the pattern's total, which is 0, so all 8 stay the same: rows 8, 9, 10, columns 7, 9, 11, diagonals 15 and 9. So rows, columns and both long diagonals are still not enough. The top-left ray (4 or 5) and the bottom-right ray (6 or 5) tell the two grids apart. The other two corners are 3 and 1 in both, so those rays do not. A computer search finds 12 grids, of whole numbers 0 or more, with these 8 totals.