Letters on a board

Letters on a board

Postby Guest » Sun Mar 12, 2017 9:25 am

In each of the cells of a 7x8 board (7 rows, 8 columns) we write one of the letters A, B or C, with the following restrictions:
In each row, number of As >= of number of Bs and number of As is >= of number of Cs.
In each column, number of Bs is >= of number of As and number of Bs is >= of number of Cs.
What is the minimum and maximum number of Cs in the board?





Guest
 

Re: Letters in a board

Postby Guest » Sun Mar 12, 2017 9:37 am

Let me show what I have tried so far...

By the way, I am not a student (although I wish I were!) - I am 62 and trying to find ways to creatively spend my free time :)
Starting by the rows, I've written down all possible combinations of A, B and C which are 45 in total (9+8+7+...+1). Of those, we keep only the arrangements that meet the required restrictions, i.e. A>=B and A>=C (I mean, number of As, Bs and Cs).
These are the following 17:
3 2 3
3 3 2
4 0 4
4 1 3
4 2 2
4 3 1
4 4 0
5 0 3
5 1 2
5 2 1
5 3 0
6 0 2
6 1 1
6 2 0
7 0 1
7 1 0
8 0 0

We then do the same with the columns, where we keep only the 13 arrangements.
0 4 3
0 5 2
0 6 1
0 7 0
1 3 3
1 4 2
1 5 1
1 6 0
2 3 2
2 4 1
2 5 0
3 3 1
3 4 0

I don't know what to do next. We can see, for example, that in the rows, we have a minimum of 0 and maximum 4 Cs - but we can't simply say that the total minimum / maximum for the entire board is 0 and 4*7=28, right? Same also with the columns (0 - 3*8=24).

Guest
 

Re: Letters in a board

Postby Guest » Sun Mar 12, 2017 2:44 pm

Spoiler: show
Consider the statement "In each row the number of As >= number of Bs".
This implies "Total number of As on the board >= total number of Bs on the board".


Spoiler: show
Similarly the statement "In each column the number of Bs >= number of As" gives us
"Total number of Bs >= total number of As".


Spoiler: show
These two implications ("total As >= total Bs" and "total Bs >= total As") imply that "total As = total Bs".


Spoiler: show
We can go further and actually deduce that in each row the number of As = number of Bs. To see why...


Spoiler: show
...consider the quantity(/definition):
[tex]r_i[/tex] = "number of As in row i - number of Bs in row i".
We know from the problem specification that [tex]r_i[/tex] >= 0 for all i,
and furthermore it isn't hard to see that the sum of the [tex]r_i[/tex] is the same as
(sum of number of As in each row) - (sum of number Bs in each row)
= total number of As - total number of Bs
= 0 (as we concluded earlier that the total number of As = total number of Bs).
So we are in the situation where the sum of non-negative [tex]r_i[/tex] equal 0...


Spoiler: show
...the only way this could happen is if all the [tex]r_i[/tex] are 0, i.e.
the number of As in row i = number of Bs in row i.


Spoiler: show
Similarly we can deduce the number of As in column j is the same as the number of Bs in column j.


Spoiler: show
Now the problem is severely constricted, from the lists you've constructed it is clear the number of A, B, Cs in a row has to be either 4,4,0, or 3,3,2,


Spoiler: show
and the number of A, B, Cs in a column can only be 3,3,1.


Spoiler: show
So every column has to have precisely one C, so the total number of Cs must be 8 (this the maximum and minimum, there is no wiggle room).


Spoiler: show
The only thing left to do is prove that there is a solution with exactly 8 Cs (there may be no solutions, all I've done is shown that *if* there are solutions they all have 8 Cs). I leave that as an exercise for you to do, it is not hard, given the restrictions we've shown a solution must follow.


Hope this helped,

R. Baber.

Guest
 

Re: Letters in a board

Postby Guest » Sun Mar 12, 2017 4:01 pm

A B A B C B A C
B A B A B C C A
C C A B A B A B
B A C C B A B A
A B A B A B A B
B A B A B A B A
A B B A A A B B


R. Baber, you are such a genius!!!

Guest
 


Return to Math Riddles



Who is online

Users browsing this forum: No registered users and 1 guest