Shepherd College Shepherdstown, WV 25443

skunyosy@shepherd.wvnet.edu

Solving any challenging problem often requires putting oneself in the right position to gain some crucial insight. To be an effective problem solver, one needs to consider alternatives, to experiment, to conjecture, to test, and to analyze the results. In short, an exploratory attitude is an essential ingredient of problem solving skills.

Computer Algebra Systems encourage the exploratory attitude in students by providing easy to use graphical and numerical capabilities, as well as symbolic capabilities. Shifting the burden of tedious computation to a machine allows the students more time to concentrate on how to approach a problem, to delineate sub-problems, to consider alternatives, and to experiment. This paper is intended to provide some examples of how Maple, a Computer Algebra System that provides a mathematical problem solving and programming environment, can be used to challenge our students with conceptual understanding, problem solving, and explorations, using problems and concepts from topics in discrete mathematics.

In Maple, a set is represented by a list of objects separated by commas, and enclosed between a pair of curly brackets, the same way we do in Mathematics. Unlike a tuple or a finite sequence of numbers, a set is a list that is un-ordered and has no repetitions. To distinguish between a set and a tuple, or ordered list, Maple uses the square brackets to represent the latter. For example {a,b,c,d} is a set of four elements. But [a,b,c,d] is a 4-tuple.

Basis:0 is in EInduction: If n is in E, then n + 2 is in EClosure:Nothing else are in E.

> evennum :=proc(n) options remember; > if n = 1 then 0 else evennum(n-1)+2 fi: end;The function evennum(k) returns the kth non-negative even number. For example, evennum(3) returns 4.

If we want to print out a list of non-negative even integers, we can use a simple for-loop:

> for i from 1 to N do print(evennum(N)); od:

(assuming N has been previously assigned a value.)

To form a set of (a finite number, 50 say) of non-negative integers, we use the following code.

> evenset := NULL: for i from 1 to 50 do

> evenset := evenset, evennum(i) od:

> print(evenset);

(a) Set of the Fibonacci numbers.

(b) Set of positive odd integers.

(c) Set of negative even integers.

(d) Set of even integers.

(e) Set of composite numbers between 2 and 100.

- Use MAPLE nested for-loop to print out the truth values of the expression for all combinations of truth values of p and q.
- Compute the truth-value for each combination and storethe result in a set. This method will return {true} if the expression is a tautology and {false} otherwise.

> with(logic):

> S := [true, false];

> for p in S do

> for q in S do

> print(p,q, bequal((not q)&implies(not p) ,(p &implies q)):

> od: od:

true, true, true true, false,true false, true, true false, false,true

> with(logic):

> s := {}: # initialize the set s

> S := [true,false]:

> for p in S do for q in S do

> s:= {op(s), bequal((not q)&implies(not p) ,(p &implies q))}:

> od: od :

> print(s);

Output: {true}

- Construct the matrix representing a multi-graph with 3 vertices and 4 edges. There are two edges between the first vertex and the third vertex, and one each between the second and the third, and the second and the first. (Call the first vertex A, the second B and the third C.)
- Draw the graph represented by the matrix above.
- How many paths of length 2 are there from vertex A to vertex B? Of length 3?
- Enter the matrix in Maple and call it M. Compute M*M and M*M*M. What does the (i,j)entry of M*M represent? Of M*M*M?
- Repeat (2) and (3) using a different graph .
- Make a conjecture as to what the (i,j) entry of M^n represent. Prove your conjecture.

On the lighter note, the entertaining aspect of graph theory lies in its usefulness for analyzing certain kinds of games and puzzles. The following problem is based on the "Instant Insanity" puzzle in Chatrands' *Graphs as Mathematical Models*. [3]

Graphs for the four cubes are entered in MAPLE as follows.

> cube1 := graph([B,G,R,W], {{R,R},{B,W},{G,R}} ):

> cube2 := graph([B,G,R,W],{{B,R}, {R,W},{G,W} })

> cube3 := graph([B,G,R,W],{{B,W},{G,R},{G,W} })

> cube4 := graph([B,G,R,W],{{B,R},{B,W},{G,G}}):

If we superimpose the four graphs together a multi-graph, G, is formed. The problem will be solved if we can find two disjoint subgraphs of G, each of order 4 ,one for front-back and the other for left-right configurations. The two subgraphs must not share edges since a given edge cannot represent both front-back and side-side at the same time. And each subgraph must contain exactly one edge from each cube.

Instead of using the diagram of G to extract two required sub-graphs, a task mostly done by trials and error, we can write Maple code to form the union of the graphs of the four cubes and extract a simple subgraph H, using Maple's gsimp() function. If it is possible to extract two order-4 edge-disjoint subgraphs of H then the problem is solved. By examining the adjacency matrix of H, we can also determine whether the puzzle is solvable or not.

We now examine the adjacency matrices of G and its maximal subgraph H together with the lists of edges in G, H, and the four cubes.

One possible solution for the above problem is : FRONT BACK LEFT RIGHT Cube 1 B W G R Cube 2 W G R B Cube 3 G R W G Cube 4 R B B WFor MAPLE worksheet example, send e-mail to

**Baxter, Nancy, Dubinsky, Ed, & Levin, Gary**,*Learning Discrete Mathematics with ISETL*, Springer-Verlag, New York, 1988.-
**Book, David L**.*Problems for Puzzlebusters*, Enigmatics Press, Washington DC. -
**Chatrand, Gary**,*Graphs as Mathematical Models*, Wadsworth International Group, Belmont, California, 1977. -
**Jackson, Bradley W. & Thoro, Dmitri**,*Applied Combinatorics with Problem Solving**, Addison-Wesley Publishing Company, New York 1990.* **Small, Donald B. & Hosack, John M**.,*Explorations in Calculus with a computer Algebra System*, McGraw-Hill, New York 1991.