1
$\begingroup$

Suppose 3 containers have sizes 10 pints, 7 pints and 4 pints respectively. Initially the 10 pint container is empty and the other two are full. This can be represented as (0,7,4) Contents can be poured from one container to another. I've made an example of a graph to represent this problem:

I want to work out either the number of distinct nodes in this problem or upper/lower bounds for it.

A node can have at most 6 children and at least 2. Perhaps this could be used to work out bounds.

$\endgroup$
4
  • $\begingroup$ For reference, according to my program, there are $21$ states and $78$ edges, as listed here: pastebin.com/K9T6WDUh However, I am sure you want a numerical/analytical proof. $\endgroup$
    – Gareth Ma
    Commented Apr 5, 2020 at 8:28
  • $\begingroup$ Also a graph photo, with the vertexes removed and relabeled, unfortunately: graphonline.ru/tmp/saved/Kt/KtFyDbHFASLiWuOe.png $\endgroup$
    – Gareth Ma
    Commented Apr 5, 2020 at 8:34
  • $\begingroup$ @GarethMa I think you should write that as an answer. $\endgroup$ Commented Apr 5, 2020 at 8:36
  • $\begingroup$ Oh erh ok. I thought you would want some analysis and not just code bruteforce, haha $\endgroup$
    – Gareth Ma
    Commented Apr 5, 2020 at 8:40

1 Answer 1

0
$\begingroup$

I wrote a python code that quickly replicated the scenario, searching through each node and find all the possible scenarios. Source here

Results I found: $21$ nodes and $78$ edges. I have listed them below:

(0, 7, 4) {(7, 0, 4), (4, 7, 0)}
(1, 6, 4) {(0, 7, 4), (7, 0, 4), (5, 6, 0), (1, 7, 3)}
(1, 7, 3) {(0, 7, 4), (8, 0, 3), (1, 6, 4), (4, 7, 0)}
(2, 5, 4) {(0, 7, 4), (7, 0, 4), (6, 5, 0), (2, 7, 2)}
(2, 7, 2) {(0, 7, 4), (9, 0, 2), (2, 5, 4), (4, 7, 0)}
(3, 4, 4) {(0, 7, 4), (7, 0, 4), (7, 4, 0), (3, 7, 1)}
(3, 7, 1) {(0, 7, 4), (10, 0, 1), (3, 4, 4), (4, 7, 0)}
(4, 3, 4) {(0, 7, 4), (7, 0, 4), (8, 3, 0), (4, 7, 0)}
(4, 7, 0) {(0, 7, 4), (10, 1, 0), (4, 3, 4)}
(5, 2, 4) {(0, 7, 4), (7, 0, 4), (9, 2, 0), (5, 6, 0)}
(5, 6, 0) {(4, 7, 0), (1, 6, 4), (10, 1, 0), (5, 2, 4)}
(6, 1, 4) {(0, 7, 4), (7, 0, 4), (10, 1, 0), (6, 5, 0)}
(6, 5, 0) {(4, 7, 0), (2, 5, 4), (10, 1, 0), (6, 1, 4)}
(7, 0, 4) {(0, 7, 4), (10, 0, 1), (7, 4, 0)}
(7, 4, 0) {(4, 7, 0), (3, 4, 4), (10, 1, 0), (7, 0, 4)}
(8, 0, 3) {(1, 7, 3), (7, 0, 4), (10, 0, 1), (8, 3, 0)}
(8, 3, 0) {(4, 7, 0), (4, 3, 4), (10, 1, 0), (8, 0, 3)}
(9, 0, 2) {(2, 7, 2), (7, 0, 4), (10, 0, 1), (9, 2, 0)}
(9, 2, 0) {(4, 7, 0), (5, 2, 4), (10, 1, 0), (9, 0, 2)}
(10, 0, 1) {(3, 7, 1), (7, 0, 4), (10, 1, 0)}
(10, 1, 0) {(4, 7, 0), (6, 1, 4), (10, 0, 1)}
Number of states: 21
Number of edges: 78

And here's a visual representation of it. (The nodes are relabeled)

If you want to do the same for different starting configurations, bucket sizes or other stuff, it's really easy to change the code and do so, so feel free to ask below :)

Cheers! This is fun to code as well haha.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .