****Two mice and three cheeses (represented by isosceles triangles) are connected by cotton wires (edges) in such a way that each mouse has a unique (one and only one) cycle, called ‘mouse cycle’, which includes that mouse only, and a set of cheeses.
Such Mice cycles have the following properties:
- Uniqueness: for each mouse, there is exactly one ‘mouse cycle’ made by that mouse only, and a set cheeses.
- The cheeses within each ‘mouse cycle’ are defined and cannot be changed.
- The relative position of mouse and cheeses within each ‘mouse cycle’ does not matter (the order of mice/cheeses may be changed).
- The relative orientation of mouse and cheeses within ‘mice cycles’ must be preserved. Mice/cheeses orientation is given by the isosceles triangle representation: the base of the triangle represents mouse’s tail/cheese’s base, whereas the opposite vertex represents mice’s head/cheese’s tip (see top of attached picture).
Using the following notation:
- Mice b: light blue mouse B: dark blue mouse.
- Cheese Y: yellow cheese, R: red cheese, O: orange cheese
- Angle bracket: mouse head/cheese tip.
With this notation, mouse cycles can be represented, for example, as:
- Light blue mouse cycle: b>, Y>
- Dark blue mouse cycle: B>, <O, Y>
Which indeed defines cheese content and relative orientation of mice/cheeses for the two mouse cycles (the order of cheeses/mice within each cycle does not matter as already stated).
See one possible visual representation of the above definition in Figure 1 in the attached picture.
Note that:
- A cheese may be shared between mices, in which case the ‘mice cycles’ intersect.
- Cheeses may not be part of any of ‘mice cycles’.
——In the visual representation, mice/cheeses connections can be re-arranged in any way as long as properties 1-4 above are preserved.
This means that the following transformations are valid ones:
a) The order of cheeses/mice may be changed. See example in Figure 2a.
b) The two cycles may be drawn such that they share edges. See example in Figure 2b.
c) One end of an isolated cheese (if present) may be connected to mice cycles’s edges. See example in Figure 2c.
—— Problem statement: Given an initial configuration ‘A’ for the two mice cycles, and a final configuration ‘B’ for the two mice cycles, what is the minimum possible number of ‘cuts’ and ‘links’ required to turn the initial configuration ‘A’ into the final one ‘B’, considering all possible equivalent arrangements of mice and cheeses connections obtained using the transformation properties a, b, c above?
See a specific example in Figure 3.
I guess what I am asking is: is it possible to find a formula or algorithm that takes initial and final configurations as inputs and gives minimum possible number of cuts&links as the output?
Or at least to make general conclusions, i.e. conclusions based on patterns on mice cycles configurations?
This problem, invented from scratch, has eluded me for a while, I have thought of it long but I’m still not sure how to approach it\how to start.
Is there any known way of tackling such a problem?
Has this problem been solved before, or is it somehow tractable? Any ideas?
