Author Topic: Logic Puzzles  (Read 58813 times)

0 Members and 1 Guest are viewing this topic.

Offline Simon

  • Administrator
  • Posts: 3551
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #195 on: April 02, 2022, 11:12:25 AM »


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 counter-exeample: There exist two nodes in G that have exactly the same number of 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

« Last Edit: April 02, 2022, 11:23:41 AM by Simon »

Offline Armani

  • Posts: 486
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #196 on: April 02, 2022, 11:46:38 AM »
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!
Armani's Blog: https://www.lemmingsforums.net/index.php?topic=4994.0

My NL level pack:
  Lemmings Uncharted[Medium~Extreme]: https://www.lemmingsforums.net/index.php?topic=5702
  Xmas Lemmings 2021[Easy~Very Hard]: https://www.lemmingsforums.net/index.php?topic=5876.0

Offline Simon

  • Administrator
  • Posts: 3551
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #197 on: April 02, 2022, 02:12:08 PM »
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)

-- Simon

Offline Armani

  • Posts: 486
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #198 on: April 02, 2022, 02:22:52 PM »
Quote
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 8-)
Armani's Blog: https://www.lemmingsforums.net/index.php?topic=4994.0

My NL level pack:
  Lemmings Uncharted[Medium~Extreme]: https://www.lemmingsforums.net/index.php?topic=5702
  Xmas Lemmings 2021[Easy~Very Hard]: https://www.lemmingsforums.net/index.php?topic=5876.0

Offline geoo

  • Administrator
  • Posts: 1450
    • View Profile
Re: Logic Puzzles
« Reply #199 on: April 04, 2022, 10:20:13 AM »
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.
« Last Edit: April 05, 2022, 09:08:19 PM by geoo »

Offline Dominator_101

  • Posts: 13
    • View Profile
Re: Logic Puzzles
« Reply #200 on: April 05, 2022, 05:20:56 PM »
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)

Offline Simon

  • Administrator
  • Posts: 3551
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #201 on: June 14, 2022, 08:19:30 AM »
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)

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. :8():

-- Simon
« Last Edit: June 14, 2022, 08:30:10 AM by Simon »

Offline Armani

  • Posts: 486
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #202 on: June 14, 2022, 09:15:56 AM »

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.
Armani's Blog: https://www.lemmingsforums.net/index.php?topic=4994.0

My NL level pack:
  Lemmings Uncharted[Medium~Extreme]: https://www.lemmingsforums.net/index.php?topic=5702
  Xmas Lemmings 2021[Easy~Very Hard]: https://www.lemmingsforums.net/index.php?topic=5876.0

Offline Simon

  • Administrator
  • Posts: 3551
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #203 on: June 14, 2022, 07:26:21 PM »
Excellent solution with proof of minimality, nice!

-- Simon

Offline DireKrow

  • Noisy Crow
  • Posts: 113
    • View Profile
Re: Logic Puzzles
« Reply #204 on: June 18, 2022, 07:49:15 PM »
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)


Puzzles

Nonoloop 1 (click to show/hide)

Nonoloop 2 (click to show/hide)

Nonoloop 3 (click to show/hide)

Nonoloop 4 (click to show/hide)


And attached is a single pdf with the rules and all puzzles, if that's preferred
LOTY 2020 Winner
My NeoLemmix Levels: The Krow Files (File A v1.2 released 21-Feb-2020)

Offline Simon

  • Administrator
  • Posts: 3551
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #205 on: June 20, 2022, 10:47:26 PM »
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
« Last Edit: September 11, 2022, 01:44:42 PM by Simon »