28

Mark some cells on the following Bingo board, so that all statements in marked cells are true AND all statements in unmarked cells are false.

A Bingo here is a set of five marked cells in a row, column, or diagonal. There are two diagonals: forward (A1-E5) and backward (A5-E1).

A B C D E
1 The backward
diagonal is
not a Bingo		 This cell is
not part of
a Bingo		 The forward
diagonal is
a Bingo		 D4 is marked This cell is
part of a Bingo
2 A4 is not marked There exist at least
one row Bingo,
column Bingo, and
diagonal Bingo		 This statement
is true		 17 or fewer cells
are marked		 An even number of
cells are
part of a Bingo
3 This cell is
part of a Bingo		 5 or more cells
are marked but not
part of a Bingo		 This cell is
not marked, OR
this cell is
part of a Bingo		 Two or more
vertical Bingos
exist		 10 or more cells
are not
part of a Bingo
4 A2 is not marked Row 2 or Column D
is a Bingo		 Column C has
3 or fewer
marked cells		 D1 is marked At least one
diagonal Bingo
exists
5 E5 is marked This board has
two or more
solutions		 This cell
is marked		 Three or more
Bingos exist		 A5 is marked

Source: Baekjoon Online Judge #17106 "Bingo", part of April Fools Contest ("Ghudegy Cup") 2018, posting with permission from the original author.

Bubbler
  • 13,734
  • 1
  • 23
  • 89
  • Is the middle statement equivalent to "This cell is neither marked nor part of a Bingo.", or is it equivalent to "Either this cell is not marked, or this cell is part of a Bingo."? – oAlt Nov 30 '22 at 06:15
  • 1
    @oAlt The latter. I meant to elaborate on the sentence but forgot. Fixed now. – Bubbler Nov 30 '22 at 06:16
  • I think I've found an answer. But I am refraining from posting it because I had to guess some cells. Is there a pure logical approach? Also I want to clarify some ambiguities : Is 'solutions' in B5 refers to 'bingos'? – ACB Nov 30 '22 at 08:50
  • @ACB About the solving path: I think I did use some small backtracking, but will check again. A solution refers to a completed bingo board according to the rules. – Bubbler Nov 30 '22 at 09:02

2 Answers2

14

To start off with:

1 and B are clearly not bingos, due to B1 (thus, B1 is marked). Similarly, C is not due to C4 and A is not due to A2 and A4 being mutually exclusive. enter image description here Notation: Marked cells have a rectangle. Cells which have been 'fulfilled' (either they're true, or they can't be true anymore for unmarked cells) have a sort of checkmark. Non-bingo rows/columns/diagonals have an X, bingo rows/columns/diagonals have an arrow.

Then,

C3 must be marked. If it isn't, the first statement is true and the second false, so due to the OR it must be marked. Hence, contradiction.enter image description here

The next step is a bit harder.

Looking at D3 - if it's marked, both D and E are bingos. That also implies B4 and A5. We have 13 cells part of a bingo now, so we need at least one more, which will be a row. E2 means we will need at least 16 bingo cells - which rules out E3. Thus, D3 can't be marked.enter image description here

C3 must be part of a bingo. If this is the forward diagonal, that means we have A1, C1, and D4 implies D1 as well. B2 implies E1 as well (due to the column bingo), which makes row 1 a bingo (which can't be). Thus, it must be the back diagonal. That implies E4, and rules out A1 and in turn C1. A5 also implies E5enter image description here

Now we get some easier deductions:

B4 implies row 2 is a bingo, then B2 implies E is a bingo. A4 is also ruled out. We can also mark D5. enter image description here

We can then look at C4 - if it's not marked, it must be true, so hence a contradiction. So C4 must be marked, C5 can't be. Also, A3 can be ruled out - there's no bingos it can be part of. enter image description here

Last steps:

We have 15 marked cells. D1/D4 would imply B3 as well, so they can't be marked (because that would violate D2). E3 will be satisfied for sure, as will D2. Now, we have 3 cells marked but not part of a bingo. If B3 is marked, then so does B5 need to be marked to satisfy B3. But that violates B1. Thus, B3 is false. B5 can be both marked and unmarked for a solution - so it must be true? But that collapses it to just one solution, making it false... enter image description here

Falco
  • 2,201
  • 12
  • 14
Lolgast
  • 3,845
  • 16
  • 39
  • Correct and well done! The last cell can probably be better explained as: rot13(Gur gehgu inyhr bs O5 zhfg or pbafvfgrag bire nyy fbyhgvbaf, ohg fvapr nyy gur bgure pryyf ner nyernql fbyirq, gurer pna or bayl bar fbyhgvba rvgure jnl. Guvf va ghea vzcyvrf gung O5 vf snyfr.) – Bubbler Nov 30 '22 at 23:00
  • 1
    Why can't rot13(p3 or cneg bs n sbejneq qvntbany ovatb)? – Jacob Raihle Dec 01 '22 at 10:49
  • 2
    Hmm I think I missed some steps there (solved it earlier but didn't keep track of my steps well enough, so this was a recreation). I'll add some explanation – Lolgast Dec 01 '22 at 12:28
  • 1
    @JacobRaihle because then rot13(svefg ebj n jbhyq or n ovatb naq ivbyngr o1) – Falco Dec 01 '22 at 15:51
  • @Lolgast, I think I disagree with your forward/backward bingo definitions. This is a forward slash: /. I guess because it is leaning forward if it is "on the ground". This does not change which rows/columns/diagonals are bingos, just a few other cells. – Poisson Fish Dec 01 '22 at 22:38
  • @Bubbler, I suppose I should tag you too to clarify the forward/backward definitions. – Poisson Fish Dec 01 '22 at 22:40
  • 1
    @PoissonFish I define those in the problem statement: "There are two diagonals: forward (A1-E5) and backward (A5-E1)." Sorry for the confusion related to slashes, but I can't change it now. – Bubbler Dec 01 '22 at 22:46
  • @Bubbler, completely missed that, thanks! – Poisson Fish Dec 01 '22 at 23:48
5

Note: Please don't upvote this answer post. Instead, upvote Lolgast's answer post, which has the same final answer as this one but with (a) a more coherent exposition and (b) no mistakes (unlike mine, which had a mistake that Lolgast later fixed).

B1 must be marked, else it's empty but part of a bingo. Then column B is not a bingo. Column A is not, either, since precisely one of A2 and A4 is filled in. The internal logic of C4 implies column C is not a bingo. The internal logic of C3 implies it's part of a bingo.

Consider the case that column D is a bingo. Then D3 is marked, so column E is also a bingo. C3's part of a bingo, so we have 13 squares already part of a bingo. By the statement in D2, the statement in B3 must then be false, so A3 is also unmarked. By the statement in E4, there's at least one diagonal bingo; by the statement in A1, there's at most one. Since we know the statements in A5 and B4 to be true, the backward diagonal is the bingo, and A1 and C1 are unmarked; thus B1 is marked. Since C1 is unmarked, if C4 is also then it's true; so C4 is marked; thus, precisely one of C2 and C5 is marked. By E2 there must be another bingo; the only remaining possible ones are rows, so B2 is marked. So we have a row bingo: which row? We've already eliminated rows 1 and 3. If row 4 or 5 is a bingo, then the other must be also, to satisfy the statement in E2. Otherwise, row 2 is a bingo. Either way, B5 is true.

Otherwise, column D is not a bingo. We already know B5 is true, since column D could be a bingo. And D3 is false. A3 is unmarked because D3 is. Now consider the statement in B4. If it's true, then row 2 is a bingo, so B2 is marked, as is D5, and column E is a bingo. E5 implies A5 is marked, completing the backward diagonal bingo, so A1 is unmarked, and thus C1 is too. If B3 is marked, then B1 can't be, but then it must be marked; so B3 is unmarked. B2 is then not part of any bingo, so is marked. If C4 is unmarked, it's true, so it must be marked. Then C5 cannot be, which will yield four marked cells not part of a bingo; because B3 is unmarked, then, D1 and D4 cannot be.
That was assuming B4 is true; otherwise, it's false and row 2 is not a bingo. Then A1 is true. If B2 is true, there's a column bingo, which must be column E, and E2 then implies row 2 is a bingo. The statement in D2 will then prevent any further markingsand C4 will be a contradiction. So B2 is false, C1, E4 and D5 are false, and there's no bingo at all, contradicting C3. So B4 must be true.

Edit, thanks to Lolgast:

In the case column D is a bingo, we wind up with >17 marked cells, violating D2. Therefore, column D is not a bingo, and B4 is true (as noted above), and B5 is false.

msh210
  • 12,844
  • 2
  • 49
  • 120
  • This is the answer I got as well. But I am not sure about E1. Rot13(Gur fgngrzrag vf "guvf pryy vf cneg bs n ovatb", juvyr vg vf cneg bs gjb ovatbf). Ambiguous :/ – ACB Nov 30 '22 at 10:09
  • If I'm not mistaken, rot13(jura lbh znex gur Q pbyhza, gur shegure fbyhgvbaf lbh trg unir zber guna 17 pryyf znexrq, ivbyngvat Q2) – Lolgast Nov 30 '22 at 10:28
  • @Lolgast ooooh, I believe you're correct. – msh210 Nov 30 '22 at 11:33