Seven Bridges of Königsberg (Unsolvable Puzzle in Computer Science))

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side).



Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges

Data Structure Can be Used to Represent The Puzzle: Graph

Solution. (Unsolvable Puzzle in Computer Science)

Reason: Its application of Graph Data Structure (Idea Comes In Mind as Studied The Puzzle Carefully). so we have to traverse each bridge one & only once & returned back to source vertex if we draw the graph of this problem we found that each vertex has odd degree so its not possible to satisfy the puzzle solution. in 17's Euler already proved it unsolvable problem of computer science & said we can solve this if we have each vertex of even degree.

See This Graph Representation

Fell Free to Comment & Suggest your Approach

Sum & Product Puzzle

X and Y are two different integers, greater than 1, with sum less than 100. S and P are two mathematicians; S knows the sum X+Y, P knows the product X*Y, and both know the information in these two sentences. The following conversation occurs.

* P says "I cannot find these numbers."
* S says "I was sure that you could not find them."
* P says "Then, I found these numbers."
* S says "If you could find them, then I also found them."





What are these numbers?
Solution

The solution has X and Y as 4 and 13 (or vice versa), with P initially knowing the product is 52 and S knowing the sum is 17.

Initially P does not know the solution, since

52 = 4 × 13 = 2 × 26

and S knows that P does not know the solution since all the possible sums to 17 within the constraints produce similarly ambiguous products. However, each can work out the solution by eliminating other possibilities following the other's statements and that is enough for the reader to find the solution given the constraints.

Water,Glass, Electricity

Suppose there are three cottages on a plane (or sphere) and each needs to be connected to the gas, water, and electric companies. Using a third dimension or sending any of the connections through another company or cottage are disallowed. Is there a way to make all nine connections without any of the lines crossing each other?

Solution

The answer is no; It is impossible to connect the three cottages with the three different utilities without at least one of the connections crossing another.

As You Can The Possible Graph Made to fulfill All the Condition is Like This




The problem is part of the mathematical field of topological graph theory which studies the embedding of graphs on surfaces. In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph K3,3 is planar. This graph is often referred to as the utility graph in reference to the problem.[1] The graph is equivalent to the circulant graph Ci6(1,3). Kazimierz Kuratowski proved in 1930 that K3,3 is nonplanar, and thus that the problem has no solution.

One proof of the impossibility of finding a planar embedding of K3,3 uses a case analysis involving the Jordan curve theorem, in which one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding. Alternatively, it is possible to show that any bridgeless bipartite planar graph with n vertices and m edges has m ≤ 2n − 4 by combining the Euler formula n - m + f = 2 (where f is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (because each face has at least four edges and each edge belongs to exactly two faces). In the utility graph, m = 9 and 2n − 4 = 8, violating this inequality, so the utility graph cannot be planar.

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor the complete graph K5 as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor K5 as a minor, encompass this result.

Tumblers on a Rotating Table- 3 Glass & 4 Glass

The three cups problem is a mathematical puzzle. Starting with three cups place one upside down and two right side up. The objective is to eventually turn all cups right side up in six moves. You must turn exactly two cups over each turn.
[edit] Solution

The puzzle is impossible. An even number of cups are facing up and you are allowed to turn two over at a time. Since an even plus an even is an even, not an odd, no number of even flips will ever get all the three cups face up. You need an odd number of cups facing up, so the problem is impossible. The possible version of this puzzle is to start with two cups facing down and one cup facing upward. This is possible. Turn up an even number (two) of cups, and all the cups are facing up; an odd plus an even is an odd (1+2 = 3).






Tumblers on a Rotating Table Puzzle :

A blind gnome and an evil goblin take turns to play a game. Four tumblers are placed at the corners of a square table. The initial configuration of the tumblers (facing up or facing down) is chosen by the evil goblin. When the blind gnome gets his turn, he is allowed to specify a subset of the four tumblers and flip them simultaneously. To be precise, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him, and flip them simultaneously. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues and the evil goblin is allowed to rotate the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?

Solution :


If there were only two cards, then “flip both” — “flip one” — “flip both” would ensure a victory for the blind gnome. For the case of four cards, let F denote “all four cards”, A denote “two adjacent cards”, D denote “two diagonally opposite cards”, O denote “one card”. Then the following 15-step sequence ensures victory for the blind gnome: F, D, F, A, F, D, F, O, F, D, F, A, F, D, F. The procedure can be generalized to 2^n cards. This problem is studied in detail by Ehrenborg and Skinner (see bibliography below); they call it “The Blind Bartender’s Problem”.
A variant of the above problem allows the blind gnome to first “touch” any t out of n tumblers on a polygonal table with n sides. Touching allows the gnome to deduce which of the t tumblers he touched are upright, and then to decide which of these t tumblers to flip. It was this variant that was originally published in Martin Gardner’s article in Feb 1979. For four tumblers, the blind gnome can win in five moves, as Gardner showed in his subsequent article in Mar 1979. The problem generated quite some interest. Two pairs of mathematicians independently proved that the blind gnome can win with a deterministic strategy if and only if t ≥ n(p-1)/p where p is the largest prime factor of n (Lewis and Willard in 1980; Laaser and Ramshaw 1981). These proofs are quite involved