Here's an another proof based on the idea of dependencies. A dependency is a square you cannot fill until you've filled one or more other squares. If you maximize the dependencies, you minimize the number of starting pieces.
- If you have an NxN grid, you can remove the top row and right column completely, removing (N + (N-1)) (or 2N-1) pieces. This will always work because you have N-1 pieces in every direction, thus allowing you to refill all them with no dependencies.
- You can have up to 1 dependent piece in the right column, so you can remove a piece not in a diagonal on the second row. This makes the second piece down in the right column dependent on all the other pieces. (This also locks in the 3rd and subsequent rows to being N-1.) This brings us up to N pieces removed.
- You can have up to 1 dependent piece in the upperleft/bottomright diagonal, so you can remove the piece in the second row correspdonding to that diagonal. (Remember, you cannot touch the 3rd and subsequent rows.) This brings us to 2N+1.
- This leaves 2 pieces that end up being dependent in the top row. But, since they were already removed, we can't count them.
My criteria for good software:
- Does it work?
- Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|
