superprismatic Posted April 1, 2011 Report Share Posted April 1, 2011 Consider an American N by M crossword grid containing precisely B black squares. What is the largest number of words that this crossword can contain? (For those who don't know: Every letter in an American crossword is in an across word as well as in a down word. The number of words is equal to the number of clues in the crossword puzzle, so words that just happen to be imbedded in clued words do not count.) Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 1, 2011 Report Share Posted April 1, 2011 (edited) Initial thoughts Take a 5x5 grid. It would contain 10 words, 5 across, 5 down. Place a black square in the corner and it has no effect. Place it on the edge of the horizontal and away from the vertical edge and now we can do 2 words on that horizontal, still one on the vertical. Place it away from both edges and we can now do two words each on the horizontal and vertical. So long as we add another black square and do not let it be adjacent to an existing black square or an edge we can squeeze two more words out of the grid. Therefore, my initial answer is N+M+2B Edited April 1, 2011 by maurice Quote Link to comment Share on other sites More sharing options...
0 curr3nt Posted April 1, 2011 Report Share Posted April 1, 2011 Initial thoughts Take a 5x5 grid. It would contain 10 words, 5 across, 5 down. Place a black square in the corner and it has no effect. Place it on the edge of the horizontal and away from the vertical edge and now we can do 2 words on that horizontal, still one on the vertical. Place it away from both edges and we can now do two words each on the horizontal and vertical. So long as we add another black square and do not let it be adjacent to an existing black square or an edge we can squeeze two more words out of the grid. Therefore, my initial answer is N+M+2B your example shows that the position of the black square matters. Corner squares are not equal to edge squares which are not equal to inner black squares. So there can be no simple equation using B. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 1, 2011 Report Share Posted April 1, 2011 Ha! curr, you put your response in my quote so now I can't quote you but... There is no simple equation for a general number of words...the problem asked for the maximum number of words however. Quote Link to comment Share on other sites More sharing options...
0 curr3nt Posted April 1, 2011 Report Share Posted April 1, 2011 Ha! curr, you put your response in my quote so now I can't quote you but... There is no simple equation for a general number of words...the problem asked for the maximum number of words however. I like doing this.. Anyways... would a bunch of one letter words count or do all the words have to connect to each other? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 1, 2011 Report Share Posted April 1, 2011 (edited) Ha! curr, you put your response in my quote so now I can't quote you but... There is no simple equation for a general number of words...the problem asked for the maximum number of words however. I like doing this.. Anyways... would a bunch of one letter words count or do all the words have to connect to each other? Why wouldn't one letter words count? Edited April 1, 2011 by maurice Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 1, 2011 Report Share Posted April 1, 2011 N+M+2*B because each black square can cut up to two words in half. Quote Link to comment Share on other sites More sharing options...
0 curr3nt Posted April 1, 2011 Report Share Posted April 1, 2011 The most a 5x5 square could have is 26 words? OXOXO XOXOX OXOXO XOXOX OXOXO Where O are blanks and X are the black squares. 13 O so that would be 13 across and 13 down. But...5+5+2*12=34 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 1, 2011 Report Share Posted April 1, 2011 The most a 5x5 square could have is 26 words? OXOXO XOXOX OXOXO XOXOX OXOXO Where O are blanks and X are the black squares. 13 O so that would be 13 across and 13 down. But...5+5+2*12=34 Ok so lets put some limit on B that keeps them from being forced to the edge. The largest number that an NxM crossword with BI interior black squares and BE exterior squares is N+M+2BI + BE - assuming no black squares are adjacent to one another... Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted April 2, 2011 Report Share Posted April 2, 2011 (edited) Ok so lets put some limit on B that keeps them from being forced to the edge. The largest number that an NxM crossword with BI interior black squares and BE exterior squares is N+M+2BI + BE - assuming no black squares are adjacent to one another... I think it is important to remember that we are limited to the availability of english words and the corresponding idiosyncratic distribution of word length. For instance, Suppose that we take N = M = 15, and B = 0. The equation above gives the maximum number of clues to be (N+M+2BI + BE) = 30. I think anyone will be hard-pressed to find fifteen 15-letter words that, when written vertically down the columns of a 15x15 box, will produce another fifteen 15-letters words when read horizontally. On the other hand, it may be possible to create 3x3 or 4x4 boxes that have precisely 6 or 8 clues. Then we can use those components as building blocks to fill in larger grids. Seems hard to prove optimality in that case though. Edited April 2, 2011 by bushindo Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted April 2, 2011 Author Report Share Posted April 2, 2011 I think it is important to remember that we are limited to the availability of english words and the corresponding idiosyncratic distribution of word length. For instance, Suppose that we take N = M = 15, and B = 0. The equation above gives the maximum number of clues to be (N+M+2BI + BE) = 30. I think anyone will be hard-pressed to find fifteen 15-letter words that, when written vertically down the columns of a 15x15 box, will produce another fifteen 15-letters words when read horizontally. On the other hand, it may be possible to create 3x3 or 4x4 boxes that have precisely 6 or 8 clues. Then we can use those components as building blocks to fill in larger grids. Seems hard to prove optimality in that case though. You could possibly make a 15 by 15 with no black squares, similar to what I did Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 2, 2011 Report Share Posted April 2, 2011 Consider an American N by M crossword grid containing precisely B black squares. What is the largest number of words that this crossword can contain? (For those who don't know: Every letter in an American crossword is in an across word as well as in a down word. The number of words is equal to the number of clues in the crossword puzzle, so words that just happen to be imbedded in clued words do not count.) assuming N is greater than M, if the opposite is true, switch M with N length of largest word = N - [b(mod(N(M-1)))*floor(B/(N(M-1)))] floor is the function that returns the largest whole number less than the parameter passed to it, example, floor(2.1234) = 2, floor(pi) =3, floor(-1.823) = -2, floor(6) = 6 etc.. mod is the remainder left when 2 numbers are divided. example, 3mod2 = 1 5mod2 = 1 10mod7=3, 3mod5 = 3, 5mod5=0 etc../spoiler] Quote Link to comment Share on other sites More sharing options...
0 Guest Posted April 3, 2011 Report Share Posted April 3, 2011 (edited) sorry about the spoiler of the last answer. here is a simpler one largest word = N - [ B(mod(N))*floor(B/(N(M-1))) ] same conditions as the previous answer Edited April 3, 2011 by hussein Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted April 3, 2011 Author Report Share Posted April 3, 2011 sorry about the spoiler of the last answer. here is a simpler one largest word = N - [ B(mod(N))*floor(B/(N(M-1))) ] same conditions as the previous answer I'm afraid you misread the OP. I was asking for the largest number of words. Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
Consider an American N by M crossword
grid containing precisely B black
squares. What is the largest number of
words that this crossword can contain?
(For those who don't know: Every letter
in an American crossword is in an across
word as well as in a down word. The
number of words is equal to the number
of clues in the crossword puzzle, so
words that just happen to be imbedded
in clued words do not count.)
Link to comment
Share on other sites
13 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.