# Contrastive Chain-of-Thought Prompting

Yew Ken Chia 1,  Guizhen Chen11footnotemark: 1 1, 2
Luu Anh Tuan2 Soujanya Poria Lidong Bing 1
1DAMO Academy, Alibaba Group, Singapore  Singapore University of Technology
and Design
2Nanyang Technological University, Singapore
{yewken_chia<EMAIL_ADDRESS>
{guizhen001<EMAIL_ADDRESS>
{yewken.chia, guizhen.chen<EMAIL_ADDRESS>
Equal contribution. Yew Ken and Guizhen are students under the Joint PhD
Program between Alibaba and their corresponding university.  Corresponding
author.

###### Abstract

Despite the success of chain of thought in enhancing language model reasoning,
the underlying process remains less well understood. Although logically sound
reasoning appears inherently crucial for chain of thought, prior studies
surprisingly reveal minimal impact when using invalid demonstrations instead.
Furthermore, the conventional chain of thought does not inform language models
on what mistakes to avoid, which potentially leads to more errors. Hence,
inspired by how humans can learn from both positive and negative examples, we
propose contrastive chain of thought to enhance language model reasoning.
Compared to the conventional chain of thought, our approach provides both
valid and invalid reasoning demonstrations, to guide the model to reason step-
by-step while reducing reasoning mistakes. To improve generalization, we
introduce an automatic method to construct contrastive demonstrations. Our
experiments on reasoning benchmarks demonstrate that contrastive chain of
thought can serve as a general enhancement of chain-of-thought
prompting.111Our code implementation will be released at
https://github.com/DAMO-NLP-SG/contrastive-cot

Contrastive Chain-of-Thought Prompting

Yew Ken Chia††thanks:  Equal contribution. Yew Ken and Guizhen are students
under the Joint PhD Program between Alibaba and their corresponding
university.  1,  Guizhen Chen11footnotemark: 1 1, 2 Luu Anh Tuan2 Soujanya
Poria Lidong Bing††thanks:  Corresponding author. 1 1DAMO Academy, Alibaba
Group, Singapore  Singapore University of Technology and Design 2Nanyang
Technological University, Singapore {yewken_chia<EMAIL_ADDRESS>{guizhen001<EMAIL_ADDRESS>{yewken.chia, guizhen.chen,
<EMAIL_ADDRESS>

Figure 1: Example of contrastive chain-of-thought which leverages both
positive and negative demonstrations to enhance language model reasoning.

##  1 Introduction

With the trend of large language models (LLMs), massively scaling the model
size has enabled greater generalization Brown et al. (2020) and the emergent
ability to perform new tasks when given suitable prompts Wei et al. (2022a).
However, solely increasing the model size cannot solve complex reasoning tasks
Rae et al. (2022). To this end, chain-of-thought prompting was proposed to
unlock the reasoning ability of LLMs by generating intermediate reasoning
steps Wei et al. (2022b). In practice, most methods based on chain of thought
leverage in-context learning Brown et al. (2020)by prompting the model with
demonstrations of the input, chain-of-thought, and output Chu et al. (2023).

However, despite its success, we lack a thorough understanding of the chain of
thought Cooper et al. (2021). For example, it was shown that even
demonstrations with invalid reasoning can lead to similar performance compared
to valid demonstrations Wang et al. (2023)222Note that while chain-of-thought
can be performed in a zero-shot fashion with prompts, we focus on the few-shot
setting, as it was originally proposed in Wei et al. (2022b).. Hence, it is
not clear how language models learn to reason effectively based on the chain-
of-thought demonstrations. On the other hand, mistakes in the intermediate
steps can compound and derail the reasoning process Ling et al. (2023). Any
potential error in the reasoning process not only affects the accuracy of the
final result but also undermines the trustworthiness of the language model
Turpin et al. (2023). Thus, it is also important to reduce mistakes in
intermediate reasoning steps.

Figure 2: Categorization of invalid chain-of-thought examples, following Wang
et al. (2023).

To address the challenges of chain of thought, we are inspired by how humans
can learn from positive as well as negative examples. For instance, when
solving a complex task where the intermediate steps are not well-defined, it
is useful to learn the correct steps from positive demonstrations, as well as
avoiding faults in negative demonstrations. Hence, we propose contrastive
chain of thought, which provides both positive and negative demonstrations to
enhance the reasoning of language models. Naturally, this raises the question
of how to design effective negative demonstrations, as well as whether they
can be generalized to diverse tasks. Through our analysis of multiple invalid
reasoning types, we design a simple and effective method that can
automatically generate contrastive demonstrations from existing valid
reasoning chains. Furthermore, as contrastive chain-of-thought is task-
agnostic and compatible with methods such as self-consistency Wang et al.
(2022), we believe that it can serve as a general enhancement of chain of
thought.

To measure the effectiveness of contrastive chain of thought, we present
evaluations on a wide range of reasoning benchmarks, and find significant
benefits. Notably, compared to conventional chain of thought, we observe
improvements of 9.8 and 16.0 points for GSM-8K Cobbe et al. (2021) and
Bamboogle Press et al. (2023) respectively when using
GPT-3.5-Turbo333https://platform.openai.com/docs/models, a widely used LLM.
Further analysis of the reasoning chains generated from our method also shows
significant reduction in errors.

In summary, our main contributions include: (1) We analyse various invalid
reasoning types and find that combining positive and negative demonstrations
generally boost the effectiveness of chain-of-thought. (2) Based on the
analysis above, we propose contrastive chain of thought to enhance language
model reasoning. To improve generalization, we also propose an automatic
method to construct contrastive demonstrations. (3) Evaluations on multiple
reasoning benchmarks demonstrate significant improvements compared to
conventional chain of thought.

##  2 Preliminary Study: Effect of Different Types of Contrastive
Demonstrations

While chain of thought (CoT) prompting has enhanced the reasoning of large
language models, it remains less well understood. For instance, while sound
reasoning seems intuitively important to effective chain of thought, previous
work has shown that there is little effect when using invalid demonstrations.
On the other hand, previous works in contrastive learning Khosla et al. (2020)
and alignment Ouyang et al. (2022) have demonstrated how language models can
learn more effectively from both valid and invalid examples. Hence, we conduct
a preliminary study with the following research question: Can invalid
reasoning demonstrations be instead used to enhance chain of thought?
Specifically, we aim to study the effect of providing chain-of-thought
demonstrations in a “contrastive” manner, i.e., demonstrations containing both
valid and invalid rationales.

###  2.1 Components of Chain of Thought

Compared to standard prompting with in-context demonstrations Brown et al.
(2020), chain-of-thought (CoT) prompting Wei et al. (2022b) includes a
rationale for each demonstration example. Each rationale consists of a series
of intermediate reasoning steps, guiding the language model to solve tasks in
a step-by-step manner. Following the formulation of Wang et al. (2023), we
identify two distinct components of each CoT rationale:

  * •

Bridging objects are the symbolic items that the model traverses in order to
reach the final solution. For example, the objects could be numbers and
equations in arithmetic tasks, or the names of entities in factual tasks.

  * •

Language templates are the textual hints that guide the language model to
derive and contextualize the correct bridging objects during the reasoning
process.

###  2.2 What is Invalid Chain of Thought?

Given the distinct components of chain of thought, we are now able to
systematically identify the aspects which lead to invalid rationales.
Concretely there are two main aspects which are applicable to both the
language and object components:

  * •

Coherence refers to the correct ordering of steps in a rationale, and is
necessary for successful chain of thought. Specifically, as chain of thought
is a sequential reasoning process, it is not possible for later steps to be
pre-conditions of earlier steps.

  * •

Relevance refers to whether the rationale contains corresponding information
from the question. For instance, if the question mentions a person named Leah
eating chocolates, it would be irrelevant to discuss a different person
cutting their hair.

In addition, following Wang et al. (2023), we include invalid reasoning as a
category of invalid chain of thought, which is neither incoherent nor
irrelevant, but contains logical mistakes. Hence, we aim to study the five
main categories of invalid chain-of-thought, as shown in Figure 2.

###  2.3 Experimental Setup

To conduct the experiments for the preliminary study, we leverage the GSM8K
Cobbe et al. (2021) and Bamboogle Press et al. (2023) datasets for arithmetic
and factual reasoning respectively. We use the OpenAI Chat Completions
API444https://platform.openai.com/docs/api-reference which is one of the most
popular and well-performing language models with reasonable cost.
Specifically, we use the GPT-3.5-Turbo (0301) version. To study the effect of
contrastive demonstrations under various settings, we evaluate the five main
invalid categories as shown in Figure 2. Note that we use 4-shot prompting for
each dataset, and the chain-of-thought demonstrations are manually constructed
by previous works Wei et al. (2022b); Wang et al. (2023). To standardize the
prompting process, we use a simplified chain-of-thought prompt format, as
shown in Figure 1.

###  2.4 Preliminary Results

Figure 3: Overview of contrastive chain-of-thought (right), with comparison to
common prompting methods.

Prompting Method | GSM8K | Bamboogle | Avg.
---|---|---|---
Standard | 27.4 | 11.2 | 19.3
Chain-of-Thought | 69.2 | 40.8 | 55.0
w/ Invalid Reasoning | 76.0 | 45.6 | 60.8
w/ Incoherent Objects | 79.6 | 53.6 | 66.6
w/ Incoherent Language | 78.8 | 52.8 | 65.8
w/ Irrelevant Objects | 79.8 | 48.8 | 64.3
w/ Irrelevant Language | 80.2 | 49.6 | 64.9

Table 1: Preliminary results on the effect of contrastive demonstrations for
chain of thought.

Prompting Method | Arithmetic Reasoning | Factual QA
---|---|---
GSM8K | AQuA | GSM-Hard | SVAMP | ASDIV | Bamboogle | StrategyQA
Standard | 27.4 | 29.5 | 11.2 | 69.3 | 75.8 | 12.0 | 59.4
CoT | 69.2 | 53.5 | 33.8 | 67.2 | 70.8 | 40.8 | 55.8
Contrastive CoT | 79.0 (+9.8) | 57.5 (+3.9) | 44.2 (+10.4) | 81.6 (+14.4) | 84.4 (+13.6) | 56.8 (+16.0) | 66.2 (+10.4)
Standard-SC | 28.0 | 29.9 | 11.0 | 69.0 | 76.0 | 11.2 | 59.6
CoT-SC | 71.0 | 55.9 | 34.0 | 71.6 | 74.0 | 40.8 | 57.0
Contrastive CoT-SC | 86.2 (+15.2) | 71.7 (+15.7) | 50.0 (+16.0) | 85.2 (+13.6) | 89.6 (+15.6) | 58.4 (+17.6) | 69.6 (+12.6)

Table 2: Main evaluation results for contrastive chain-of-thought on several
reasoning tasks.

Dataset | Type |  $|$Train$|$ |  $|$Test$|$
---|---|---|---
GSM8K | Arithmetic Reasoning | 4 | 500
AQuA | Arithmetic Reasoning | 4 | 254
GSM-Hard | Arithmetic Reasoning | 4 | 500
SVAMP | Arithmetic Reasoning | 4 | 500
ASDIV | Arithmetic Reasoning | 4 | 500
Bamboogle | Factual QA | 4 | 125
StrategyQA | Factual QA | 4 | 500

Table 3: Details of datasets used.

Based on the preliminary results in Table 1, we observe significant gains
across all invalid rationale categories compared to conventional chain-of-
thought. Notably, leveraging chain of thought with contrastive demonstrations
containing incoherent objects yields the highest average performance on GSM8K
and Bamboogle. This suggests that language models are better able to learning
step-by-step reasoning when provided with both valid and invalid rationales.
Hence, we believe that contrastive demonstrations have the potential to
greatly enhance language model reasoning ability.

##  3 Contrastive Chain of Thought

Chain-of-thought (CoT) prompting, as evidenced by prior research, has indeed
elevated the reasoning capabilities of large language models Wei et al.
(2022b). However, a comprehensive understanding of this phenomenon is still
lacking. Although logically sound reasoning appears to be inherently crucial
for chain of thought, prior studies surprisingly reveal minimal impact when
employing invalid demonstrations. To this end, based on our preliminary study
in Section 2, we found that providing both valid and invalid reasoning
demonstrations in a “contrastive” manner greatly improves reasoning
performance. However, this approach may not generalize well to new tasks, as
it requires manual construction of the invalid rationales.

Thus, we propose a general prompting method known as contrastive chain of
thought, which includes automatic construction of contrastive demonstrations.
Figure 3 presents an overview of our approach. Specifically, the language
model is provided with the question, ground truth answer explanation and
incorrect answer explanation. Compared to standard prompting, our method
enables models to perform more complex reasoning by decomposing problems into
intermediate steps. Compared to conventional chain-of-thought prompting, our
method contrasts the valid and invalid answer explanations, guiding the model
to generate more accurate reasoning chains.

Concretely, given a small set of $n$ in-context demonstration examples
$D=\\{E_{1},\ldots,E_{|n|}\\}$, and a query $Q$, the goal of the model is to
generate a suitable answer $A$. For standard prompting, the demonstration
examples consist of just the question and answer, i.e., $E_{j}=(Q_{j},A_{j})$.
On the other hand, chain-of-thought is a more advanced prompting method that
guides the model with intermediate reasoning steps $T$. As shown in the figure
above, the reasoning steps $T$ typically consist of multiple sentences where
each sentence describes one reasoning step. Hence, chain-of-thought prompting
examples consist of the question, reasoning steps, and final answer, i.e.,
$E_{j}=(Q_{j},T_{j},A_{j})$. However, the model does not know what faults to
avoid in conventional chain-of-thought, which could lead to increased mistakes
and error propagation. Hence, our contrastive chain of thought method provides
both the correct and incorrect reasoning steps in the demonstration examples,
i.e., $E_{j}=(Q_{j},T_{j,+},A_{j,+},T_{j,-},A_{j,-})$.

To obtain the correct reasoning steps $T_{+}$ for the demonstration examples,
we use the annotated examples from the previous chain-of-thought works. For
the incorrect reasoning steps $T_{-}$, we automatically construct it from the
correct reasoning steps $T_{+}$, based on the "Incoherent Objects" category in
Section 2. Concretely, we use an existing entity recognition
model555https://spacy.io/models/en#en_core_web_trf to extract the object spans
such as numbers, equations, or persons from a given chain-of-thought
rationale. Consequently, we randomly shuffle the position of the objects
within the rationale, thus constructing a rationale with incoherent bridging
objects. Note that when testing with a new question, only the question and
demonstration examples are provided to the model, and the model must generate
its own reasoning steps before producing the final answer.

##  4 Experiments

###  4.1 Experimental Setup

We focus our study on two main types of reasoning tasks: arithmetic reasoning
and factual question answering (QA). For arithmetic reasoning, we conduct
experiments on a range of datasets including GSM8K Cobbe et al. (2021), AQuA
Ling et al. (2017), GSM-Hard Gao et al. (2023), SVAMP Patel et al. (2021), and
ASDIV Miao et al. (2020). For factual QA, we include two datasets: Bamboogle
Press et al. (2023) and StrategyQA Geva et al. (2021). To maintain a
reasonable computing budget, we limit each dataset to a maximum of 500 test
samples through random sampling. For datasets that contain less than 500 test
samples, we instead use all available test samples. The datasets’ details are
included in Table 3. Regarding model and prompting details, we use the same
experimental setup as for our preliminary study in Section 2.

###  4.2 Main Results

To assess the effectiveness of our method, we evaluate on several reasoning
tasks and report the main results in Table 2. Our main findings are as
follows:

#### Contrastive CoT demonstrates consistent improvements over conventional
CoT.

Contrastive CoT consistently outperforms conventional CoT across the datasets
in both arithmetic and factual reasoning categories. Notably, we observe
substantial gains of more than 10 points on GSM-Hard, SVAMP, ASDIV, Bamboogle
and StrategyQA. Thus, the consistent and significant performance improvements
demonstrate the general effectiveness of our proposed method. As contrastive
chain of thought can be automatically constructed from existing rationales,
the annotation cost is the same as conventional chain of thought. Hence, it
can be viewed as a general enhancement of chain of thought.

#### Contrastive CoT is more effective when applied with self-consistency.

As self-consistency Wang et al. (2022) is a popular decoding strategy to boost
the chain-of-thought performance of large language models, we are interested
to see if contrastive chain of thought can benefit similarly from self-
consistency. In general, we observe that self-consistency further enhances the
performance of contrastive CoT. This enhancement is particularly evident in
the case of the AQuA dataset. While contrastive CoT alone results in a modest
performance improvement of 4.0%, applying self-consistency amplifies this gain
significantly, achieving an additional improvement of 14.2%.

##  5 Related Work

#### Large Language Models

Recent developments in large language models have shown that massively scaling
the size and training data of models can greatly improve generalization Kaplan
et al. (2020). Notably, large language models have been shown to generalize to
new tasks when given suitable prompts and demonstrations Brown et al. (2020).
This has brought about a new paradigm of leveraging language models for tasks
without the need for additional training Liu et al. (2023). However, simply
scaling language models has not been sufficient to attain good performance on
challenging tasks such as arithmetic reasoning and factual question answering
Wei et al. (2022b). Hence, in this work, we focus on enhancing the reasoning
ability of large language models through prompts.

#### Chain of Thought

Chain-of-thought prompting was introduced by Wei et al. (2022b) to enhance
language model reasoning by generating intermediate steps. Notably, this has
inspired numerous works that build upon this direction of step-by-step
reasoning. For instance, automatic chain-of-thought Zhang et al. (2023) was
proposed to address the challenges in manually annotating chain-of-thought
demonstrations. On the other hand, it was shown that specific prompts such as
“Let’s think step-by-step” can enable language models to perform chain-of-
thought in a zero-shot manner, without any demonstrations Kojima et al.
(2022). In addition, challenging problems can be decomposed into multiple sub-
problems Zhou et al. (2023), or even into code programs that can be
automatically executed Gao et al. (2023). Despite the progress in chain-of-
thought on multiple fronts, we still lack a rigorous understanding of the
underlying mechanism Turpin et al. (2023); Feng et al. (2023). In this work,
inspired by the findings of previous works regarding invalid demonstrations,
we propose contrastive chain-of-thought to enhance language model reasoning.
As contrastive chain-of-thought leverages both valid and invalid reasoning
demonstrations, we believe this may encourage other researchers to
fundamentally rethink the chain-of-thought process.

#### Learning from Negative Examples

While chain-of-thought prompting typically involves only valid demonstrations,
it is not clear whether invalid demonstrations can also benefit the reasoning
process Wang et al. (2023). On the other hand, learning from negative or
invalid samples is not new. For instance, contrastive learning is a well-
established deep learning approach that encourages models to distinguish
between “positive” and “negative” samples, thus learning better
representations Khosla et al. (2020). Similarly, reinforcement learning from
human feedback (RLHF) trains a reward model based on positive and negative
samples of human preference data Ouyang et al. (2022); Christiano et al.
(2017). Hence, inspired by the previous approaches, we propose contrastive
chain-of-thought, a general enhancement of chain-of-thought prompting, by
enabling models to learn from both valid and invalid reasoning demonstrations.

##  6 Conclusions

In this work, we have explored the effect of leveraging invalid reasoning
demonstrations for enhancing chain of thought. Through our preliminary study
on different invalid chain-of-thought categories, we found that providing both
valid and invalid demonstrations in a contrastive manner greatly improves
reasoning ability in language models. To overcome the challenge of manually
annotating invalid rationales, we propose contrastive chain of thought, a
general prompting method which can automatically construct contrastive
demonstrations from existing rationales. Through experiments on several
reasoning tasks, we find contrastive chain of thought to be a general
enhancement of chain-of-thought prompting. Further investigation into
alternative forms of chain-of-thought prompting will hopefully inspire future
advancements in language-based reasoning.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017.  Deep reinforcement learning from human preferences.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Chu et al. (2023) Zheng Chu, Jingchang Chen, Qianglong Chen, Weijiang Yu, Tao He, Haotian Wang, Weihua Peng, Ming Liu, Bing Qin, and Ting Liu. 2023.  A survey of chain of thought reasoning: Advances, frontiers and future.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021.  Training verifiers to solve math word problems.  _CoRR_ , abs/2110.14168.
  * Cooper et al. (2021) Nathan Cooper, Carlos Bernal-Cárdenas, Oscar Chaparro, Kevin Moran, and Denys Poshyvanyk. 2021.  It takes two to tango: Combining visual and textual information for detecting duplicate video-based bug reports.  _CoRR_ , abs/2101.09194.
  * Feng et al. (2023) Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2023.  Towards revealing the mystery behind chain of thought: A theoretical perspective.  In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Gao et al. (2023) Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023.  PAL: Program-aided language models.  In _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 10764–10799. PMLR.
  * Geva et al. (2021) Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021.  Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies.  _Transactions of the Association for Computational Linguistics_ , 9:346–361.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. 2020.  Scaling laws for neural language models.  _CoRR_ , abs/2001.08361.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. 2020.  Supervised contrastive learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 18661–18673. Curran Associates, Inc.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  In _Advances in Neural Information Processing Systems_.
  * Ling et al. (2017) Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 2017.  Program induction by rationale generation: Learning to solve and explain algebraic word problems.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 158–167, Vancouver, Canada. Association for Computational Linguistics.
  * Ling et al. (2023) Zhan Ling, Yunhao Fang, Xuanlin Li, Zhiao Huang, Mingu Lee, Roland Memisevic, and Hao Su. 2023.  Deductive verification of chain-of-thought reasoning.  In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Liu et al. (2023) Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2023.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  _ACM Comput. Surv._ , 55(9).
  * Miao et al. (2020) Shen-yun Miao, Chao-Chun Liang, and Keh-Yih Su. 2020.  A diverse corpus for evaluating and developing English math word problem solvers.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 975–984, Online. Association for Computational Linguistics.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022.  Training language models to follow instructions with human feedback.  In _Advances in Neural Information Processing Systems_.
  * Patel et al. (2021) Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021.  Are NLP models really able to solve simple math word problems? In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2080–2094, Online. Association for Computational Linguistics.
  * Press et al. (2023) Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. 2023.  Measuring and narrowing the compositionality gap in language models.
  * Rae et al. (2022) Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew Johnson, Blake Hechtman, Laura Weidinger, Iason Gabriel, William Isaac, Ed Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. 2022.  Scaling language models: Methods, analysis & insights from training gopher.
  * Turpin et al. (2023) Miles Turpin, Julian Michael, Ethan Perez, and Samuel R. Bowman. 2023.  Language models don’t always say what they think: Unfaithful explanations in chain-of-thought prompting.  In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Wang et al. (2023) Boshi Wang, Sewon Min, Xiang Deng, Jiaming Shen, You Wu, Luke Zettlemoyer, and Huan Sun. 2023.  Towards understanding chain-of-thought prompting: An empirical study of what matters.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2717–2739, Toronto, Canada. Association for Computational Linguistics.
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Huai hsin Chi, and Denny Zhou. 2022.  Self-consistency improves chain of thought reasoning in language models.  _ArXiv_ , abs/2203.11171.
  * Wei et al. (2022a) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed Huai hsin Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022a.  Emergent abilities of large language models.  _Trans. Mach. Learn. Res._ , 2022.
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022b.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Zhang et al. (2023) Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2023.  Automatic chain of thought prompting in large language models.  In _The Eleventh International Conference on Learning Representations_.
  * Zhou et al. (2023) Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi. 2023.  Least-to-most prompting enables complex reasoning in large language models.  In _The Eleventh International Conference on Learning Representations_.


# A Graph-Theoretic Model for a Generic Three Jug Puzzle

Suresh Manjanath Hegde National Institute of Technology Karnataka,
Surathkal-575025, India  Shashanka Kulamarva Indian Institute of Science,
Bangalore-560012, India

###### Abstract

In a classic three jug puzzle we have three jugs $A$, $B$, and $C$ with some
fixed capacities. The jug $A$ is fully filled with wine to its capacity. The
goal of the puzzle is to divide the wine into two equal halves by pouring it
from one jug to another without using any other measuring devices. However, we
consider a generic version of the three jug puzzle and present an independent
graph theoretic model to determine whether the puzzle has a solution at first
place. If it has a solution, then the same can be determined using this model.
We also present the sketch of an algorithm to determine the solution of the
puzzle.

Keywords: Three jug puzzle; Generic three jug puzzle; graph theoretic model;
directed graphs

Mathematics Subject Classification: 05C20, 05C90

##  1 Introduction

Mathematics can be used as a tool to solve several puzzles, riddles and open
questions. In most of the cases, mathematical modeling helps in this regard. A
three jug puzzle is one of the ancient and familiar puzzles. A formal
statement of the puzzle goes as follows:

Three Jug Puzzle: There are three jugs $A$, $B$, and $C$ with some fixed
capacities $a$, $b$ and $c$ gallons respectively with $a>b>c$. The jug $A$ is
fully filled with wine to its capacity. Is it possible to divide the wine into
two equal halves only by pouring it from one jug to another any number of
times without using any other measuring devices?

For better understanding of the puzzle, we come up with the following
definition. A pour of wine from jug $X$ to jug $Y$ ($X$ and $Y$ can be any two
jugs out of $A$, $B$ and $C$), is said to be a _measurable pour_ if the
pouring is stopped when the jug $X$ becomes empty or the jug $Y$ becomes full
to its capacity. As the name suggests, a measurable pour keeps track of the
volumes of wine in each of the jugs after pouring. One can easily see that if
we don’t perform a measurable pour and stop the pouring somewhere in between,
since we don’t have other measuring devices, we will loose the information on
the amount of wine in each of the jugs. Since we need to keep track of the
amount of wine in each of the jugs without using any other measuring devices,
every pour should be a measurable pour. Thus we can rewrite the puzzle as
follows:

Three Jug Puzzle(Restated): There are three jugs $A$, $B$, and $C$ with some
fixed capacities $a$, $b$ and $c$ gallons respectively with $a>b>c$. The jug
$A$ is completely filled with wine to its capacity. Is it possible to divide
the wine into two equal halves only by performing a series of measurable
pours?

The origin of this puzzle can be traced back to 16th century [4]. Leon et al.
[2] studied a generic two jug puzzle (no jug C; pouring is only between the
jugs A and B or emptying or filling one of them) and proposed a solution for
the puzzle. Later, Man [3] gave an algorithmic solution for the two jug
puzzle.

McDiarmid and Alfonsin [4] considered the three jug puzzle with a condition
that $a=b+c$ and solved the puzzle. They also proved that a solution to the
puzzle exists if and only if the number $a$ is divisible by $2r$ where
$r=gcd(b,c)$. However, the puzzle becomes more interesting without the
condition $a=b+c$. For a historical review on the three jug puzzle, one can
refer [5]. A study on the solvability of the puzzle was carried out by Boldi
et al. [1].

Ore [6] proposed a model for the three jug puzzle in the framework of graph
theory by using the concept of directed paths in directed graphs. Any
distribution of the wine in the three jugs $A$, $B$, and $C$, can be described
by the quantities $b$ and $c$ of wine in the jugs $B$ and $C$, respectively.
Hence, every possible distribution of wine is denoted by a pair $(b,c)$.

$(0,0)$$(0,1)$$(0,2)$$(0,3)$$(1,0)$$(1,1)$$(1,2)$$(1,3)$$(2,0)$$(2,1)$$(2,2)$$(2,3)$$(3,0)$$(3,1)$$(3,2)$$(3,3)$$(4,0)$$(4,1)$$(4,2)$$(4,3)$$(5,0)$$(5,1)$$(5,2)$$(5,3)$$(6,0)$$(6,1)$$(6,2)$$(6,3)$$(7,0)$$(7,1)$$(7,2)$$(7,3)$
Figure 1: Directed path indicating a solution to the three jug problem 10, 7,
3

Let us consider an example illustration with the three jug problem 10, 7, 3.
Initially all the wine is in the jug $A$ indicating that $b=c=0$ so that the
initial distribution is $(0,0)$. The target distribution to be achieved is
clearly $(5,0)$. The idea is to consider all non-negative integer pairs from
$(0,0)$ to $(b,c)$ as vertices of a graph and to draw an edge wherever it’s
possible to move from one vertex (distribution) to another vertex
(distribution) by a measurable pour of wine between a pair of jugs. This
results in a directed path in the graph which indicates a solution to the
three jug problem as depicted in the Figure 1. A directed $uv$-path means a
directed path from a vertex $u$ to a vertex $v$.

Now, we consider a generic version of the three jug puzzle defined as follows
and propose a graph theoretic solution to the same by coming up with a graph
model where the existence of the edges does not depend on the decision of
whether one can achieve a distribution by pouring in between the jugs or not.
In other words, the graph model proposed in the paper is an independent model.

Generic Three Jug Puzzle: Consider three jugs $A$, $B$, and $C$ having fixed
capacities $a$, $b$ and $c$ gallons respectively with $a>b>c$. Let $d$ gallons
of wine be distributed over these three jugs in the order $a^{\prime}$,
$b^{\prime}$ and $c^{\prime}$ gallons respectively (so that
$a^{\prime}+b^{\prime}+c^{\prime}=d$), satisfying the following conditions:

  * •

$d=2k$ for some positive integer $k$

  * •

$b\geq\frac{d}{2}$

Is it possible to divide the $d$ gallons of wine into two equal halves only by
pouring it from one jug to another any number of times without using any other
measuring devices?

Since the basic condition of keeping track of the amount of wines in each jugs
without using any measuring devices, needs to be satisfied also in the generic
three jug puzzle, every pour has to be a measurable pour. Thus we can restate
the puzzle as follows:

Generic Three Jug Puzzle(Restated): Consider three jugs $A$, $B$, and $C$
having fixed capacities $a$, $b$ and $c$ gallons respectively with $a>b>c$.
Let $d$ gallons of wine be distributed over these three jugs in the order
$a^{\prime}$, $b^{\prime}$ and $c^{\prime}$ gallons respectively (so that
$a^{\prime}+b^{\prime}+c^{\prime}=d$), satisfying the following conditions:

  * •

$d=2k$ for some positive integer $k$

  * •

$b\geq\frac{d}{2}$

Is it possible to divide the $d$ gallons of wine into two equal halves only by
performing a series of measurable pours?

In this paper, we present a directed graph model to check whether the given
generic three jug puzzle is solvable or not. If at all the solution exists for
the puzzle, then it can be determined using the same model. One can see that
the final graph obtained by our model is similar to the graph obtained by Ore
[6]; but there are a couple of significant differences.

Firstly, the puzzle considered here is a generic version. Secondly, our way of
modeling is completely different since unlike the modeling in [6], our
modeling does not require the prior information of whether it is possible to
achieve a target distribution from a source distribution by a valid pour or
not. Moreover, this graph model is completely independent of the puzzle
itself.

##  2 The Graph Model

Let $Q=(a,b,c,d)$ be an ordered quadruple of positive integers with $a>b>c$,
satisfying the following conditions:

  * •

$d=2k$ for some positive integer $k$

  * •

$b\geq\frac{d}{2}$

For the given ordered quadruple $Q=(a,b,c,d)$ of positive integers, let us
consider a corresponding directed graph $G_{Q}$ with the set of vertices being
the set of all ordered pairs $(i,j)$ with $0\leq i\leq b$ and $0\leq j\leq c$,
i.e.,

$V(G_{Q})=\bigcup_{\begin{subarray}{c}0\leq i\leq b\\\ \mathstrut 0\leq j\leq
c\\\ \mathstrut i,j\in\mathbb{Z}\end{subarray}}(i,j)$

There exists a directed edge from a vertex $(i,j)$ to another vertex
$(i^{\prime},j^{\prime})$ in $G_{Q}$ if and only if $0\leq d-i-j\leq a$,
$0\leq d-i^{\prime}-j^{\prime}\leq a$, and one of the following conditions
hold:

  1. $($i$)$.

$j^{\prime}=j$ and $i^{\prime}\in\\{0,b,d-j,d-a-j\\}$

  2. $($ii$)$.

$i^{\prime}=i$ and $j^{\prime}\in\\{0,c,d-i,d-a-i\\}$

  3. $($iii$)$.

$i+j=i^{\prime}+j^{\prime}$ with $i^{\prime}\in\\{0,b\\}$ or
$j^{\prime}\in\\{0,c\\}$

An example illustration of graph $G_{Q}$ generated by the quadruple
$Q=(7,4,2,6)$ is given in Figure 2. Now, consider any generic three jug puzzle
$\mathbb{P}$. One can see that $\mathbb{P}$ clearly generates an ordered
quadruple $P=(a,b,c,d)$ as per the requirement of the model which in turn
results in the generation of the directed graph $G_{P}$.

$(0,0)$$(0,1)$$(0,2)$$(1,0)$$(1,1)$$(1,2)$$(2,0)$$(2,1)$$(2,2)$$(3,0)$$(3,1)$$(3,2)$$(4,0)$$(4,1)$$(4,2)$
Figure 2: Graph $G_{Q}$ corresponding to the quadruple $Q=(7,4,2,6)$

##  3 Main Results

Moving ahead, the idea is to utilize the graph $G_{P}$ and its properties to
look for a solution to the generic three jug puzzle $\mathbb{P}$. In order to
achieve that, we need to prove some results on equivalences that are provided
in the section.

######  Theorem 3.1.

Let $\mathbb{P}$ be a generic three jug puzzle with $a$, $b$ and $c$ being the
capacities of the jugs $A$, $B$, and $C$ respectively and the total quantity
of wine being $d$ gallons. Further, let $G_{P}$ be a graph obtained from the
ordered quadruple $P=(a,b,c,d)$ using the graph model defined in Section 2.
Then there exists a directed edge from a vertex $(i,j)$ to a vertex
$(i^{\prime},j^{\prime})$ in $G_{P}$ if and only if the the corresponding
distribution $(i^{\prime},j^{\prime})$ can be obtained from the distribution
$(i,j)$ in the puzzle $\mathbb{P}$ by a single measurable pour.

###### Proof.

We have the generic three jug puzzle $\mathbb{P}$, the ordered quadruple
$P=(a,b,c,d)$, and the graph $G_{P}$ as in the theorem statement. Since we
need to prove an equivalence, we have to prove both the directions. First,
assume that the distribution $(i^{\prime},j^{\prime})$ can be obtained from
the distribution $(i,j)$ in the puzzle $\mathbb{P}$ by a single measurable
pour from a jug $X$ to another jug $Y$. Since $d-i-j$ and
$d-i^{\prime}-j^{\prime}$ are the levels of wines in the jug $A$ in the
distribution $(i,j)$ and $(i^{\prime},j^{\prime})$ respectively, we clearly
have:

$0\leq d-i-j\leq a\text{\hskip 21.33955pt and \hskip 21.33955pt}0\leq
d-i^{\prime}-j^{\prime}\leq a$

Depending on the choice of jugs $X$ and $Y$, we have the following cases.

######  Case 1.

$X=A$ and $Y=B$

In this case, we pour from jug $A$ to $B$. Since the jug $C$ is untouched, we
have that $j^{\prime}=j$. Since a measurable pour is being performed, we stop
pouring only if the jug $A$ becomes empty or the jug $B$ becomes full.
Depending on the reason for the termination of pouring, we have the following
subcases.

######  Subcase 1.1.

Pouring terminated because the jug $A$ became empty.

In this case, since the jug $A$ is empty, $d$ gallons of wine is distributed
only in the jugs $B$ and $C$ which implies that $i^{\prime}+j^{\prime}=d$.
This together with the fact that $j^{\prime}=j$ imply that $i^{\prime}=d-j$.
Thus we have $i^{\prime}\in\\{0,b,d-j,d-a-j\\}$.

######  Subcase 1.2.

Pouring terminated because the jug $B$ became full.

In this case, since the jug $B$ is full, the amount of wine in the jug $B$ is
equal to its capacity. Hence, we have that $i^{\prime}=b$ indicating that
$i^{\prime}\in\\{0,b,d-j,d-a-j\\}$.

In any subcase, we have $i^{\prime}\in\\{0,b,d-j,d-a-j\\}$. Thus we can
collectively confirm that there exists a directed edge from the vertex $(i,j)$
to the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$, as desired.

######  Case 2.

$X=B$ and $Y=A$

In this case, we pour from jug $B$ to $A$. Since the jug $C$ is untouched, we
have that $j^{\prime}=j$. Since a measurable pour is being performed, we stop
pouring only if the jug $B$ becomes empty or the jug $A$ becomes full. Again,
depending on the reason for the termination of pouring, we have the following
subcases.

######  Subcase 2.1.

Pouring terminated because the jug $B$ became empty.

In this case, since the jug $B$ is empty, the amount of wine in the jug $B$ is
equal $0$. Hence, we have that $i^{\prime}=0$ indicating that
$i^{\prime}\in\\{0,b,d-j,d-a-j\\}$.

######  Subcase 2.2.

Pouring terminated because the jug $A$ became full.

In this case, since the jug $A$ is full, the amount of wine in the jug $A$ is
equal to its capacity and the remaining wine is distributed over the jugs $B$
and $C$ which implies that $a+i^{\prime}+j^{\prime}=d$. Further, substituting
$j^{\prime}=j$, we get $a+i^{\prime}+j=d$. Hence, we have that
$i^{\prime}=d-a-j$ indicating that $i^{\prime}\in\\{0,b,d-j,d-a-j\\}$.

In any subcase, we have $i^{\prime}\in\\{0,b,d-j,d-a-j\\}$. Thus we can
collectively confirm that there exists a directed edge from the vertex $(i,j)$
to the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$, as desired.

######  Case 3.

$X=A$ and $Y=C$

In this case, we pour from jug $A$ to $C$. Since the jug $B$ is untouched, we
have that $i^{\prime}=i$. Since a measurable pour is being performed, we stop
pouring only if the jug $A$ becomes empty or the jug $C$ becomes full.
Depending on the reason for the termination of pouring, we have the following
subcases.

######  Subcase 3.1.

Pouring terminated because the jug $A$ became empty.

In this case, since the jug $A$ is empty, $d$ gallons of wine is distributed
only in the jugs $B$ and $C$ which implies that $i^{\prime}+j^{\prime}=d$.
This together with the fact that $i^{\prime}=i$ imply that $j^{\prime}=d-i$.
Thus we have $j^{\prime}\in\\{0,c,d-i,d-a-i\\}$.

######  Subcase 3.2.

Pouring terminated because the jug $C$ became full.

In this case, since the jug $C$ is full, the amount of wine in the jug $C$ is
equal to its capacity. Hence, we have that $j^{\prime}=c$ indicating that
$j^{\prime}\in\\{0,c,d-i,d-a-i\\}$.

In any subcase, we have $j^{\prime}\in\\{0,c,d-i,d-a-i\\}$. Thus we can
collectively confirm that there exists a directed edge from the vertex $(i,j)$
to the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$, as desired.

######  Case 4.

$X=C$ and $Y=A$

In this case, we pour from jug $C$ to $A$. Since the jug $B$ is untouched, we
have that $i^{\prime}=i$. Since a measurable pour is being performed, we stop
pouring only if the jug $C$ becomes empty or the jug $A$ becomes full. Again,
depending on the reason for the termination of pouring, we have the following
subcases.

######  Subcase 4.1.

Pouring terminated because the jug $C$ became empty.

In this case, since the jug $C$ is empty, the amount of wine in the jug $C$ is
equal $0$. Hence, we have that $j^{\prime}=0$ indicating that
$j^{\prime}\in\\{0,c,d-i,d-a-i\\}$.

######  Subcase 4.2.

Pouring terminated because the jug $A$ became full.

In this case, since the jug $A$ is full, the amount of wine in the jug $A$ is
equal to its capacity and the remaining wine is distributed over the jugs $B$
and $C$ which implies that $a+i^{\prime}+j^{\prime}=d$. Further, substituting
$i^{\prime}=i$, we get $a+i+j^{\prime}=d$. Hence, we have that
$j^{\prime}=d-a-i$ indicating that $j^{\prime}\in\\{0,c,d-i,d-a-i\\}$.

In any subcase, we have $j^{\prime}\in\\{0,c,d-i,d-a-i\\}$. Thus we can
collectively confirm that there exists a directed edge from the vertex $(i,j)$
to the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$, as desired.

######  Case 5.

$X=B$ and $Y=C$

In this case, we pour from jug $B$ to $C$. Since the jug $A$ is untouched, we
have that $i+j=i^{\prime}+j^{\prime}$. Since a measurable pour is being
performed, we stop pouring only if the jug $B$ becomes empty or the jug $C$
becomes full. Depending on the reason for the termination of pouring, we have
the following subcases.

######  Subcase 5.1.

Pouring terminated because the jug $B$ became empty.

In this case, since the jug $B$ is empty, the amount of wine in the jug $B$ is
equal $0$. Hence, we have that $i^{\prime}=0$ indicating that
$i^{\prime}\in\\{0,b\\}$.

######  Subcase 5.2.

Pouring terminated because the jug $C$ became full.

In this case, since the jug $C$ is full, the amount of wine in the jug $C$ is
equal to its capacity. Hence, we have that $j^{\prime}=c$ indicating that
$j^{\prime}\in\\{0,c\\}$.

In any subcase, we have $i^{\prime}\in\\{0,b\\}$ or $j^{\prime}\in\\{0,c\\}$.
Thus we can collectively confirm that there exists a directed edge from the
vertex $(i,j)$ to the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$, as desired.

######  Case 6.

$X=C$ and $Y=B$

In this case, we pour from jug $C$ to $B$. Since the jug $A$ is untouched, we
have that $i+j=i^{\prime}+j^{\prime}$. Since a measurable pour is being
performed, we stop pouring only if the jug $C$ becomes empty or the jug $B$
becomes full. Depending on the reason for the termination of pouring, we have
the following subcases.

######  Subcase 6.1.

Pouring terminated because the jug $C$ became empty.

In this case, since the jug $C$ is empty, the amount of wine in the jug $C$ is
equal $0$. Hence, we have that $j^{\prime}=0$ indicating that
$j^{\prime}\in\\{0,c\\}$.

######  Subcase 6.2.

Pouring terminated because the jug $B$ became full.

In this case, since the jug $B$ is full, the amount of wine in the jug $B$ is
equal to its capacity. Hence, we have that $i^{\prime}=b$ indicating that
$i^{\prime}\in\\{0,b\\}$.

In any subcase, we have $i^{\prime}\in\\{0,b\\}$ or $j^{\prime}\in\\{0,c\\}$.
Thus we can collectively confirm that there exists a directed edge from the
vertex $(i,j)$ to the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$, as desired.

Since the cases are exhaustive and all the cases lead to the desired result,
we can conclude that there exists a directed edge from the vertex $(i,j)$ to
the vertex $(i^{\prime},j^{\prime})$ in $G_{P}$ which completes one direction
of the proof.

Now, conversely, assume that there exists a directed edge from a vertex
$(i,j)$ to a vertex $(i^{\prime},j^{\prime})$ in $G_{P}$. Since $G_{P}$ is a
graph obtained using the model and since there is an edge from $(i,j)$ to
$(i^{\prime},j^{\prime})$, the following conditions must hold:

  1. (1).

$0\leq d-i-j\leq a$

  2. (2).

$0\leq d-i^{\prime}-j^{\prime}\leq a$

Further, the edge is present because one of the three conditions in the model
holds. Suppose the first condition $(i)$ holds, then we have the following:

  1. (3).

$j=j^{\prime}$

  2. (4).

$i^{\prime}\in\\{0,b,d-j,d-a-j\\}$

Since $(i,j)$ and $(i^{\prime},j^{\prime})$ are two different vertices or
distributions, $(3)$ implies that $i\neq i^{\prime}$. Note that the
distribution $(i,j)$ implies that the jugs $A$, $B$ and $C$ are filled with
$d-i-j$, $i$ and $j$ gallons of wine respectively. Similarly, the distribution
$(i^{\prime},j^{\prime})$ implies that the jugs $A$, $B$ and $C$ are filled
with $d-i^{\prime}-j^{\prime}$, $i^{\prime}$ and $j^{\prime}$ gallons of wine
respectively.

Suppose $i^{\prime}=0$. Notice that in order to achieve the distribution
$(0,j^{\prime})$ from $(i,j)$ with $j^{\prime}=j$, we need to pour the entire
wine in jug $B$ to $A$. Since $i^{\prime}=0$, we have $d-j^{\prime}\leq a$ by
$(2)$. But combining this with $(3)$, we obtain $d-j\leq a$, which indicates
that in the distribution $(i,j)$, the jug $A$ has sufficient space for the
entire wine in the jug $B$. Therefore, one can obtain the distribution
$(i^{\prime},j^{\prime})$ from the distribution $(i,j)$ by pouring the wine
from jug $B$ to jug $A$ until the jug $B$ is empty, which is in accordance
with that of a measurable pour.

Otherwise, suppose $i^{\prime}=b$. Notice that in order to achieve the
distribution $(b,j^{\prime})$ from $(i,j)$ with $j^{\prime}=j$, we need to
pour the wine from jug $A$ to $B$ until $B$ is full. Observe that $(2)$ also
implies that $i^{\prime}+j^{\prime}\leq d$. This combined with the fact that
$i^{\prime}=b$ imply that $b+j^{\prime}\leq d$. Further, using $(3)$, we
obtain $b+j\leq d$ which in turn leads to $d-i-j\geq b-i$, indicating that in
the distribution $(i,j)$, the jug $A$ has sufficient wine to fill the jug $B$
to its capacity, i.e., $b$. Therefore, one can obtain the distribution
$(i^{\prime},j^{\prime})$ from the distribution $(i,j)$ by pouring the wine
from jug $A$ to jug $B$ until the jug $B$ is full, which is in accordance with
that of a measurable pour.

Otherwise, suppose $i^{\prime}=d-j$. Notice that in order to achieve the
distribution $(d-j,j^{\prime})$ from $(i,j)$ with $j^{\prime}=j$, we need to
pour the entire wine in jug $A$ to $B$. Since $i^{\prime}$ was picked to be a
non-negative integer inclusively between $0$ and $b$, we have
$i^{\prime}=d-j\leq b$, indicating that in the distribution $(i,j)$, the jug
$B$ has sufficient space for the entire wine in the jug $A$. Therefore, one
can obtain the distribution $(i^{\prime},j^{\prime})$ from the distribution
$(i,j)$ by pouring the wine from jug $A$ to jug $B$ until the jug $A$ is
empty, which is in accordance with that of a measurable pour.

Otherwise, by $(4)$ we have that $i^{\prime}=d-a-j$. Notice that in order to
achieve the distribution $(d-a-j,j^{\prime})$ from $(i,j)$ with
$j^{\prime}=j$, we need to pour the wine from jug $B$ to $A$ until $A$ is
full. From $i^{\prime}=d-a-j$, we can deduce the following inequalities:

$\displaystyle i^{\prime}=d-a-j$ $\displaystyle\implies$ $\displaystyle
d-j=a+i^{\prime}$ $\displaystyle\implies$ $\displaystyle a\leq d-j$
$\displaystyle\implies$ $\displaystyle a+i\leq d+i-j$ $\displaystyle\implies$
$\displaystyle i\geq a-d+i+j$

Thus we have $i\geq a-(d-i-j)$, indicating that in the distribution $(i,j)$,
the jug $B$ has sufficient wine to fill the jug $A$ to its capacity, i.e.,
$a$, since the initial quantity of wine in jug $A$ is $d-i-j$. Therefore, one
can obtain the distribution $(i^{\prime},j^{\prime})$ from the distribution
$(i,j)$ by pouring the wine from jug $B$ to jug $A$ until the jug $A$ is full,
which is in accordance with that of a measurable pour.

Thus in any case, if the first condition $(i)$ holds, then the distribution
$(i^{\prime},j^{\prime})$ can be obtained from the distribution $(i,j)$ by a
single valid pour of wine from one jug to another.

Otherwise, suppose the second condition $(ii)$ holds, then we have the
following:

  1. (3).

$i=i^{\prime}$

  2. (4).

$j^{\prime}\in\\{0,c,d-i,d-a-i\\}$

Since $(i,j)$ and $(i^{\prime},j^{\prime})$ are two different vertices or
distributions, $(3)$ implies that $j\neq j^{\prime}$. Suppose $j^{\prime}=0$.
Notice that in order to achieve the distribution $(i^{\prime},0)$ from $(i,j)$
with $i^{\prime}=i$, we need to pour the entire wine in jug $C$ to $A$. Since
$j^{\prime}=0$, we have $d-i^{\prime}\leq a$ by $(2)$. But combining this with
$(3)$, we obtain $d-i\leq a$, which indicates that in the distribution
$(i,j)$, the jug $A$ has sufficient space for the entire wine in the jug $C$.
Therefore, one can obtain the distribution $(i^{\prime},j^{\prime})$ from the
distribution $(i,j)$ by pouring the wine from jug $C$ to jug $A$ until the jug
$C$ is empty, which is in accordance with that of a measurable pour.

Otherwise, suppose $j^{\prime}=c$. Notice that in order to achieve the
distribution $(i^{\prime},c)$ from $(i,j)$ with $i^{\prime}=i$, we need to
pour the wine from jug $A$ to $C$ until $C$ is full. Observe that $(2)$ also
implies $i^{\prime}+j^{\prime}\leq d$. This combined with the fact that
$j^{\prime}=c$ imply that $i^{\prime}+c\leq d$. Further, using $(3)$, we
obtain $i+c\leq d$ which in turn leads to $d-i-j\geq c-j$, indicating that in
the distribution $(i,j)$, the jug $A$ has sufficient wine to fill the jug $C$
to its capacity, i.e., $c$. Therefore, one can obtain the distribution
$(i^{\prime},j^{\prime})$ from the distribution $(i,j)$ by pouring the wine
from jug $A$ to jug $C$ until the jug $C$ is full, which is in accordance with
that of a measurable pour.

Otherwise, suppose $j^{\prime}=d-i$. Notice that in order to achieve the
distribution $(i^{\prime},d-i)$ from $(i,j)$ with $i^{\prime}=i$, we need to
pour the entire wine in jug $A$ to $C$. Since $j^{\prime}$ was picked to be a
non-negative integer inclusively between $0$ and $c$, we have
$j^{\prime}=d-i\leq c$, indicating that in the distribution $(i,j)$, the jug
$C$ has sufficient space for the entire wine in the jug $A$. Therefore, one
can obtain the distribution $(i^{\prime},j^{\prime})$ from the distribution
$(i,j)$ by pouring the wine from jug $A$ to jug $C$ until the jug $A$ is
empty, which is in accordance with that of a measurable pour.

Otherwise, by $(4)$ we have that $j^{\prime}=d-a-i$. Notice that in order to
achieve the distribution $(i^{\prime},d-a-i)$ from $(i,j)$ with
$i^{\prime}=i$, we need to pour the wine from jug $C$ to $A$ until $A$ is
full. From $j^{\prime}=d-a-i$, we can deduce the following inequalities:

$\displaystyle j^{\prime}=d-a-i$ $\displaystyle\implies$ $\displaystyle
d-i=a+j^{\prime}$ $\displaystyle\implies$ $\displaystyle a\leq d-i$
$\displaystyle\implies$ $\displaystyle a+j\leq d-i+j$ $\displaystyle\implies$
$\displaystyle j\geq a-d+i+j$

Thus we have $j\geq a-(d-i-j)$, indicating that in the distribution $(i,j)$,
the jug $C$ has sufficient wine to fill the jug $A$ to its capacity, i.e.,
$a$, since the initial quantity of wine in jug $A$ is $d-i-j$. Therefore, one
can obtain the distribution $(i^{\prime},j^{\prime})$ from the distribution
$(i,j)$ by pouring the wine from jug $C$ to jug $A$ until the jug $A$ is full,
which is in accordance with that of a measurable pour.

Thus in any case, if the second condition $(ii)$ holds, then the distribution
$(i^{\prime},j^{\prime})$ can be obtained from the distribution $(i,j)$ by a
single valid pour of wine from one jug to another.

Otherwise, if the conditions $(i)$ and $(ii)$ do not hold, then we are sure
that the third condition $(iii)$ holds. Thus we have the following:

  1. (3).

$i+j=i^{\prime}+j^{\prime}$

  2. (4).

$i^{\prime}\in\\{0,b\\}$ or $j^{\prime}\in\\{0,c\\}$

Suppose $i^{\prime}=0$. Notice that in order to achieve the distribution
$(0,j^{\prime})$ from $(i,j)$ satisfying $(3)$, we need to pour the entire
wine in jug $B$ to $C$. Since $i^{\prime}=0$, we have $i+j=j^{\prime}$ by
$(3)$. Therefore, since $j^{\prime}$ was picked to be a non-negative integer
inclusively between $0$ and $c$, we have $c\geq j^{\prime}=i+j$ which in turn
implies that $c-j\geq i$, indicating that in the distribution $(i,j)$, the jug
$C$ has sufficient space for the entire wine in the jug $B$. Therefore, one
can obtain the distribution $(i^{\prime},j^{\prime})$ from the distribution
$(i,j)$ by pouring the wine from jug $B$ to jug $C$ until the jug $B$ is
empty, which is in accordance with that of a measurable pour.

Otherwise, suppose $i^{\prime}=b$. Notice that in order to achieve the
distribution $(b,j^{\prime})$ from $(i,j)$ satisfying $(3)$, we need to pour
the wine from jug $C$ to $B$ until $B$ is full. Making use of $(3)$ and the
fact that $i^{\prime}=b$, we obtain the following inequality:

$b=i^{\prime}\leq i^{\prime}+j^{\prime}=i+j$

Thus we get $j\geq b-i$, indicating that in the distribution $(i,j)$, the jug
$C$ has sufficient wine to fill the jug $B$ to its capacity, i.e., $b$.
Therefore, one can obtain the distribution $(i^{\prime},j^{\prime})$ from the
distribution $(i,j)$ by pouring the wine from jug $C$ to jug $B$ until the jug
$B$ is full, which is in accordance with that of a measurable pour.

Otherwise, suppose $j^{\prime}=0$. Notice that in order to achieve the
distribution $(i^{\prime},0)$ from $(i,j)$ satisfying $(3)$, we need to pour
the entire wine in jug $C$ to $B$. Since $j^{\prime}=0$, we have
$i+j=i^{\prime}$ by $(3)$. Therefore, since $i^{\prime}$ was picked to be a
non-negative integer inclusively between $0$ and $b$, we have $b\geq
i^{\prime}=i+j$ which in turn implies that $b-i\geq j$ indicates that in the
distribution $(i,j)$, the jug $B$ has sufficient space for the entire wine in
the jug $C$. Therefore, one can obtain the distribution
$(i^{\prime},j^{\prime})$ from the distribution $(i,j)$ by pouring the wine
from jug $C$ to jug $B$ until the jug $C$ is empty, which is in accordance
with that of a measurable pour.

Otherwise, if $i^{\prime}\notin\\{0,b\\}$ and $j^{\prime}\neq 0$, then by
$(4)$, we are sure that $j^{\prime}=c$. Notice that in order to achieve the
distribution $(i^{\prime},c)$ from $(i,j)$ satisfying $(3)$, we need to pour
the wine from jug $B$ to $C$ until $C$ is full. Making use of $(3)$ and the
fact that $j^{\prime}=c$, we obtain the following inequality:

$c=j^{\prime}\leq i^{\prime}+j^{\prime}=i+j$

Thus we get $i\geq c-j$, indicating that in the distribution $(i,j)$, the jug
$B$ has sufficient wine to fill the jug $C$ to its capacity, i.e., $c$.
Therefore, one can obtain the distribution $(i^{\prime},j^{\prime})$ from the
distribution $(i,j)$ by pouring the wine from jug $B$ to jug $C$ until the jug
$C$ is full, which is in accordance with that of a measurable pour.

Hence, collectively, if any one of the three conditions in the model holds,
then the distribution $(i^{\prime},j^{\prime})$ can be obtained from the
distribution $(i,j)$ by a single valid pour of wine from one jug to another.
Since there is a directed edge from the vertex $(i,j)$ to the vertex
$(i^{\prime},j^{\prime})$, one of the three conditions in the model definitely
holds which marks the completion of the proof. ∎

Once we have Theorem 3.1, the following corollary follows from the same. This
corollary gives an equivalent condition for the three jug puzzle to have a
solution, by making use of the model defined in Section 2.

######  Corollary 3.2.

Let $\mathbb{P}$ be a generic three jug puzzle with $a$, $b$ and $c$ being the
capacities of the jugs $A$, $B$, and $C$ respectively and the total quantity
of wine being $d$ gallons (distributed in the three jugs as $a^{\prime}$,
$b^{\prime}$ and $c^{\prime}$ respectively). Further, let $G_{P}$ be a graph
obtained from the ordered quadruple $P=(a,b,c,d)$ using the model in Section
2. Then the puzzle $\mathbb{P}$ has a solution if and only if there exists a
directed path from the vertex $(b^{\prime},c^{\prime})$ to the vertex
$(\frac{d}{2},0)$ in $G_{P}$.

###### Proof.

First, assume that the puzzle $\mathbb{P}$ has a solution. Then clearly, one
can reach the distribution $(\frac{d}{2},0)$ from the distribution
$(b^{\prime},c^{\prime})$ through a sequence of intermediate distributions
obtained exactly by the sequence of measurable pours performed along the
process. For every single change of distribution in this sequence of pouring,
we have a directed edge between the corresponding vertices, by Theorem 3.1. By
taking the union of all these directed edges corresponding to the entire
sequence that is used to reach the distribution $(\frac{d}{2},0)$ from the
distribution $(b^{\prime},c^{\prime})$, we can obtain a directed path from the
vertex $(b^{\prime},c^{\prime})$ to the vertex $(\frac{d}{2},0)$ in $G_{P}$,
as desired. This completes one direction of the proof.

Conversely, assume that there exists a directed path from the vertex
$(b^{\prime},c^{\prime})$ to the vertex $(\frac{d}{2},0)$ in $G_{P}$. But a
directed path is nothing but a sequence of directed edges. For each edge in
this sequence, by Theorem 3.1, we can obtain the corresponding ordered pair of
distributions such that the latter can be obtained from the first by a single
valid pour of the wine from one jug to another. This sequence of ordered pairs
starting from $(b^{\prime},c^{\prime})$ ending at $(\frac{d}{2},0)$, generates
the sequential order of pouring of wine between the jugs which gives us the
desired solution to the puzzle $\mathbb{P}$. This completes the proof of the
corollary. ∎

##  4 Sketch of an Algorithm

Now, if we are provided with a generic three jug puzzle, one can just extract
an ordered quadruple out of it and obtain the graph model presented in Section
2. Once that is done, it all boils down to determining whether the puzzle has
a solution or equivalently whether the graph has the corresponding directed
path. In other words, by Corollary 3.2, we can leave aside the puzzle and just
look at the fairly simple graph model and look at its structural properties
and infer whether the original generic three jug puzzle had a solution or not;
if it had a solution we can determine the same using the graph model.

Once we are sure that the puzzle has a solution, then one can think of the
problem of minimizing the number of measurable pours, i.e., to determine the
minimum number of measurable pours that is necessary to obtain a solution.
Again, by using Corollary 3.2, this boils down to determining the shortest
directed path in the graph model. Observe that whenever a directed path exists
in a graph, a shortest directed path also exists in the graph. Alternatively,
whenever a solution exists for the puzzle, a solution with the minimum number
of measurable pours also exists for the puzzle. Therefore, the model can also
be used to obtain the optimum solution, if it exists.

As a result of the previous discussions, we are sure that given a generic
three jug puzzle $\mathbb{P}$, one can use the following steps to obtain a
solution. These steps can be treated as the skeleton of an algorithm.

  1. 1.

Obtain an ordered quadruple $Q=(a,b,c,d)$ where $a,b,c$ are the capacities of
the jugs $A,B,C$ respectively and $d$ is the total quantity of wine available
in the puzzle $\mathbb{P}$.

  2. 2.

Obtain a directed graph $G_{Q}$ corresponding to $Q$ using the model in
Section 2.

  3. 3.

Check whether there exists a directed path from the vertex
$s=(b^{\prime},c^{\prime})$ (In the puzzle $\mathbb{P}$, $d$ gallons of wine
is distributed in the jugs $A,B,C$ as $a^{\prime},b^{\prime},c^{\prime}$
gallons) to the vertex $t=(\frac{d}{2},0)$ in $G_{Q}$.

  4. 4.

If there exists a directed $st$-path in $G_{Q}$, then the vertex sequence in
the same order as a shortest directed $st$-path will be a solution to the
puzzle $\mathbb{P}$.

  5. 5.

Otherwise, when there is no directed $st$-path in $G_{Q}$, the puzzle
$\mathbb{P}$ has no solution.

##  5 Conclusion

As mentioned earlier, people have been studying the variants of the jug puzzle
since 16th century [4]. Determining whether these kind of puzzles have a
solution or not is an interesting research problem to be tackled. Several
variants of the puzzle have been shown to be solvable using various methods
and algorithms. In view of this paper, a generic version of the three jug
puzzle is considered and an independent directed graph model is proposed such
that the solvability of the puzzle can be determined by using the model. If a
solution exists, then the same can be determined by using the same model. It
is important to note that the graph model as such do not depend on the puzzle
in any way.

In future, one can consider a different variant of the puzzle or a completely
different puzzle and try to determine the solvability of the same by using a
similar technique or the idea of the model presented in the paper. Our motive
was to utilize graph theory as a tool to tackle the generic three jug puzzle.
In future, researchers may utilize some other field of mathematics to tackle
this puzzle and try to come up with a simpler model or a better technique.

## References

  * Boldi et al. [2002] Paolo Boldi, Massimo Santini, and Sebastiano Vigna.  Measuring with jugs.  _Theoretical Computer Science_ , 282(2):259–270, 2002.
  * Leon et al. [2005] Florin Leon, Mihai Horia Zaharia, and Dan Gâlea.  A heuristic for solving the generalized water jugs problem.  _Bulletin of the Polytechnic Institute of Iasi, tome LI (LV), section Automatic Control and Computer Science, fasc._ , (1-4):95–102, 2005.
  * Man [2015] Yiu Kwong Man.  Solving the general two water jugs problem via an algorithmic approach.  In _Proceedings of the International MultiConference of Engineers and Computer Scientists, IMECS 2015, March 18-20, 2015, Hong Kong_ , volume I, 2015.
  * McDiarmid and Alfonsin [1994] Colin J. H. McDiarmid and Jorge Ramirez Alfonsin.  Sharing jugs of wine.  _Discrete Mathematics_ , 125(1-3):279–287, 1994\.
  * O’Beirne [1965] T. H. O’Beirne.  _Puzzles and Paradoxes: Fascinating Excursions in Recreational Mathematics_.  Oxford University Press, 1965.
  * Ore [1990] Oystein Ore.  _Graphs and Their Uses_ , volume 34 of _Anneli Lax New Mathematical Library_.  The Mathematical Association of America, Washington, D.C., 1990.