Logic Puzzles

[Simon]

More cute graph theory.

Let G be an undirected graph with n ≥ 2 nodes, with only simple edges, i.e., no multiple edges. Prove the following statement or construct a counterexample: There exist two nodes in G that have exactly the same number of touching kittens edges.

Example: In the picture, both A and B have two edges each.

Example: if G contains only n = 2 nodes, they're either connected (and both have 1 edge) or not (and both have 0 edges); in either case, G contains two nodes with the same number of edges. Thus, the statement is true at least for two-node graphs.

-- Simon

[Armani]

Assume no two nodes have exactly the same number of edges.
Then the number of edges of every nods = {0,1,2, ... , n-1}
but this is impossible
contradiction!

[Simon]

Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.

Your proof was the first that I found, too. Here is a second proof that I found today:

Spoiler (click to show/hide)

Induction base case n = 2: I've shown this as an example in the problem statement.

Induction hypothesis: All graphs with fewer than n nodes contain two nodes with identical edge counts.

Induction step: Let G have exactly n nodes. Consider a connected component X of G with the maximum possible number of nodes.

• If X has exactly 1 node, then G contains no edges at all. Since n > 2, pick any two nodes; they'll have an identical edge count of 0.
• If X has 1 < x < n nodes, then X, considered a graph by itself, contains two nodes with identical edge counts by the induction hypothesis.
• If X has n nodes, the n nodes each have an edge count of 1, 2, ..., n − 1; none have an edge count of 0 because X is connected. The function that maps the n nodes of X into those n − 1 possible edge counts fails to be injective due to the pidgeonhole principle. Thus, there are two nodes in X with equal edge count.
  

All three cases satisfly the claim, thus the claim is true for n.

-- Simon

[Armani]

Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.

0 means there's a nod which is connected to no other nods
n-1 means there's a nod which is connected to all other nods
They can't both be true simultaneously

[geoo]

Here's a Lix-related logic puzzle (which I haven't solved yet):

You're building a N-player level where each player has M hatches.

The hatches are arranged into a grid of M rows and N columns. But the player order is wrong!
You need that in each column, all hatches belong to the same player, and in each row, the hatches spawn lixes at the same time.
You don't want to move the hatches around (error-prone), but you can fix this by changing the priority of a few of them.
How many hatches do you have to click to be guaranteed to be able to sort this out, regardless of the initial arrangement?

About priorities: If my hatches are ordered 1, 2, 3, 4, 5, and I decrease the priority of #4 down to 2, the priority of #2 and #3 gets increased by 1 each, giving 1, 3, 4, 2, 5.
If the players are A, B, C and the hatches per player are A1, A2, A3, then the hatches are ordered
A1, B1, C1, A2, B2, C2, A3, B3, C3
1   2   3   4   5   6   7   8   9

Example: N=2, M=2.
A2 B1    3 2
B2 A1 or 4 1
If I increase the priority of A1 to A2, I get
B1 A1    2 1
B2 A2 or 4 3
So clicking one hatch is sufficient. Is one hatch sufficient for every starting configuration for N=2, M=2?

Remark: This is from a real example where I was trying to build a level, and clicking hatches was expensive as they were buried under eraser terrain, which had to be removed first to access the hatch.

[Dominator_101]

So I was thinking of a different approach to the graph problem, but I kept hitting snags in my logic so I might think that over longer.

For Geoo's issue, I'm not sure if I 100% understand the priority orders you laid out. I think I figured out your initial example and was just conceptualizing it differently. I'm still unclear on the second example. You first say that the hatches would go A1, B1, A2, C2 as 1,2,3,4 respectively, but in the side by side examples it looks like A1 is 1 and B2 is 2? I also don't really follow how the rearrangement happens there. Not sure if I'm just missing something.

Here's some thoughts, based on my assumption of how the ordering works:

Spoiler (click to show/hide)

Okay, so my initial read on this is it's simply doing a bubble sort, you can move one item at a time and bubble it up or down to change the priorities. If that's the case, our worst case complexity is the same as bubble sort, which would be n-1 moves, or (p*h)-1 where p = num players and h = num hatches.

However, there are a couple different interpretations here that still fulfill the criteria of the problem, and it has to do with how strict we want the ordering. There's two variables we can tweak that give us slightly different scenarios:

Strict player orders: Do we care that player A always comes before player B?
Strict hatch order: Do we care what order the hatches release as long as they are synced for all players?

For example, this arrangement fulfills the original reqs if we don't need strict ordering for either:
B2 A2
B3 A3
B1 A1

I'm assuming here that we probably want non-strict player order (player order doesn't really have meaning since player order is random on level start) but strict hatch ordering (we want the level to spawn from top-down). Given that, we have a bit more control over the bubble sort. The worst case is still an inverted list, like so:
B2, A2, B1, A1
However, since we don't care about player order, we don't actually need to reorder B2 and A2, so instead of a worst case of 3 our worst case is only 2, to move B1 and A1 to the front (or B2 and A2 to the back, if you'd prefer )

Best as I can tell, the worst case complexity for this scenario is equal to p(h-1). No matter the original sort order, we can always ignore one group of hatches and use their player order for the other hatches as we move them around.

Now, in the very non-strict case where we don't care about player order OR hatch order, our worst case changes yet again. Now an inverted case isn't strictly worst because we don't care about the hatch order, we just need to group the same hatches with the same player order, so I think worst case becomes hatches grouped by player (A1, A2, A3, B1, B2, B3). To me, this seems like the most complex to try and find the formula for. because it's weird to think of scenarios, but I think that it ends up being (p-1)(h-1).

That also makes me assume if you wanted to keep player strict but hatch non-strict, it would be (p-1)h, but I honestly haven't checked that at all and am just assuming based on the other formulas I came up with.

Hopefully my interpretation is correct here? I think that no matter how you slice it it should be reducible to a list so I assume it should be a valid line of reasoning.

You could make this even more complicated if you consider that it's easier to change the priority in the text file directly, which allows you to move adjacent hatches up/down at the same time with copy/paste. My gut says worst case would still be arranged in a way where you're moving single items at once, but I haven't thought much about it.

[Simon]

geoo's hatch distribution is still open.


What is the minimum number of knights to put on an 8x8 chessboard such that the knights attack every vacant square?

Example with 16 knights (click to show/hide)

. . . . . . . .
. . . . . . . .
. N N . . N N .
. N N . . N N .
. N N . . N N .
. N N . . N N .
. . . . . . . .
. . . . . . . .

All vacant squares are attacked. In addition, all knights themselves are attacked by other knights, even though that isn't required by the problem statement.

The solution is a local minimum, in the sense that you can't remove any of the knights without redistributing the other 15.

Can you do better than this? I don't even have intuition whether optimal solutions will be symmetrical or asymmetrical.

Downsides with this kind of puzzle: It's not pure logic, it's optimization, thus borderline off-topic for the thread of pure logic puzzles. And I don't know the solution; I believe that optimiality is hard to prove. Although -- we did a good job on the lights in the wagons: We proved that O(n) is optimal, even though that wasn't part of the initial puzzle.

Thus, feel free to just skip the knights and post another puzzle.

-- Simon

[Armani]

Every coloured square can only be covered by unique different knights which means you can't cover the whole board with less than 12knights.

And it's possible to cover the whole chessboard with 12knights. Here's an example:



So the answer is 12.

[Simon]

Excellent solution with proof of minimality, nice!

-- Simon

[DireKrow]

I've been getting into Nikoli-style logic puzzles recently, solving a few when I have the time, but I also went ahead and created some of my own puzzles. They're nothing too fancy, but I'm pretty happy with them for a first attempt. They use a ruleset which combines Simple Loops with Nonograms. I dub it, the Nonoloop.


Rules

- Draw a single non-intersecting loop through the centers of all cells. The loop may only move horizontally or vertically and may only make 90-degree turns.
- Clues outside the grid represent the lengths of the blocks of consecutive turns that the loop makes in the corresponding row or column, in order.

E.g. "2" means the loop turns in two consecutive cells in that column, while "1 1" means the loop turns in one cell and then another non-consecutively.

Example (click to show/hide)

Play online: https://tinyurl.com/2cy6qf8q

Puzzles

Nonoloop 1 (click to show/hide)

Play online: https://tinyurl.com/22j3q3er

Nonoloop 2 (click to show/hide)

Play online: https://tinyurl.com/248kr96k

Nonoloop 3 (click to show/hide)

Play online: https://tinyurl.com/2yfy2gut

Nonoloop 4 (click to show/hide)

Play online: https://tinyurl.com/2y85nto4

And attached is a single pdf with the rules and all puzzles, if that's preferred

[Simon]

The four puzzles are of satisfying quality: solvable with sensible contemplation, but without far-fetched guesswork. Thanks! Attached are my solutions. I printed the PDF and solved with pen and paper.

I knew Nonogram, but didn't know Simple Loop. I discovered several emergent patterns that the Nonoloop solutions must satisfy, and in hindsight, they should apply to Simple Loop, too. Nonetheless -- congrats on designing something with such emergence from only a few given rules! Formalizing the patterns in my mind helped with the later puzzles.

Rule clarifications that I took for granted: When a row contains clues, not only these clues denote the lengths of the blocks of consecutive turns, in order, but also:

• Any two blocks of the row are separated by one or more straight-loop squares.
  
• The clues cover all the blocks of the row, i.e., there are no more turns in that row other than those denoted by the clues.
  

-- Simon

[mobius]

I started messing around with Chat GPT 4 recently. I gave it this puzzle:
https://www.lemmingsforums.net/index.php?topic=1389.msg39003#msg39003

It gave the correct answer; its description of the process was pretty thorough as well; more detailed than mine and used two tables. Of course this was a while ago and I can't remember exactly how I solved it myself except what I wrote there, but my description was much shorter than chat GTP's.

Next I gave it this puzzle;

https://www.lemmingsforums.net/index.php?topic=1389.msg96371#msg96371

This was the answer:

The minimum number of knights required to put on an 8x8 chessboard such that they attack every vacant square is 32. Here's one possible arrangement that achieves this:

mathematica

N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .

In this arrangement, the knights are placed on every other square of the board, such that they attack all the remaining squares. It's important to note that the knights only attack squares that are not occupied by other knights, so we can't simply place 64 knights on the board to cover every square.

Also, this is the minimum number of knights required to cover all the vacant squares on the board, but it doesn't necessarily mean that it's the only solution. There may be other valid arrangements that achieve the same result.

I then asked if it could do it with "all knights themselves are attacked by other knights" and the answer was; no none can be placed and then I realized why it got it wrong but I don't know how to word this correctly.

I was confused at first as well until I realized the question is... well as I said I don't know how to phrase the question correctly, but it is missing a bit of information imo, in the statement of the problem. Chat GPT is solving it as if each square can only be taken in one 'instance'.

also an oddity: why it "forgot" the last column on the chessboard? I'll ask it that later.

I've been getting into Nikoli-style logic puzzles recently, solving a few when I have the time, but I also went ahead and created some of my own puzzles. They're nothing too fancy, but I'm pretty happy with them for a first attempt. They use a ruleset which combines Simple Loops with Nonograms. I dub it, the Nonoloop.

Next I might try the loop puzzles and nonograms and other puzzles but idk if drawing and images is possible with this version I'm using.

Btw; those puzzles are fun but tough! I started trying one myself at work today

[mobius]

well this was interesting; I rephrased the question to "what if the theoretical attacks of the knights can overlap?"

It then answered with "If we allow the theoretical attacks of the knights to overlap, then the minimum number of knights needed to cover every square on an 8x8 chessboard reduces to 14."

but the diagram it gave was identical to the first; trying again different yielded the same diagram. So it got closer to the minimal answer (pretty close) but seem to fail at drawing this for some reason. As such I can't be certain if it's really still understanding the problem correctly.

In any case I just realized I'm using Chat GPT 3 not 4, which is supposedly shockingly better than 3. 4 must be paid for it looks like. 3 is still pretty impressive for what it can do and how it does it.

[chaos_defrost]

If you like pencil and paper style puzzles, I highly recommend Instructionless Grid:
https://ig.logicpuzzle.app

It's.... as the name suggests, there's 100 puzzles, I think I got about 30 or so on my own but I believe the dev intended to have them solved as teams.