Excel Deleting Problem
 

Suppose you have a block of cell's in a "triangle" you want to "delete". You can delete them by selecting a rectangle.

For example:

Here is a triangle of length 6.

XOOOOO
XXOOOO
XXXOOO
XXXXOO
XXXXXO
XXXXXX

And you want to delete the X's.

OOOOO
OOOO
OOO
OO
O



So one deletion could be:
OOOOO
XOOOO
XXOOO
XXXOO
XXXXO
XXXXX, since I can delete a rectangle of cells in the first column. I can delete multiple rows and columns, but must delete an entire rectangle.

So the question:
For a triangle of size n, what is the least number of deletions to get rid of all of the X's?

What is the algorithm for it?

This question may be interesting or extremely trivial, and I don't know the answer either.

Re: Excel Deleting Problem
 

I think it's pretty trivial. I'll be astonished if the answer is not n. It's clear it takes no more than n, so the "hard" part would be showing you can't do it in fewer. I'm pretty sure you can do this inductively easily.

Re: Excel Deleting Problem
 

Actually, proving it is bound by n as a lower bound is easy. Every cell on the diagonal needs to be deleted, and can only be deleted if you have it in the corner of a deletion. There are n notches, therefore you must do at least n deletions.

Boo.

Re: Excel Deleting Problem
 

Just do a multi-select on all the X's, select delete, and then shift cells left. One deletion.


aloiz

Re: Excel Deleting Problem
 

Uhh, that deletes O's or you aren't explaining yourself very well.

Re: Excel Deleting Problem
 

Technically, you can do it all in 1 deletion by holding down CTRL and single clicking every cell, then hitting delete..once.