The generalized double pouring problem: Analysis, bounds and algorithms.
Saved in:
| Title: | The generalized double pouring problem: Analysis, bounds and algorithms. |
|---|---|
| Authors: | Jäger, Gerold1 (AUTHOR) gerold.jager@umu.se, Lehtilä, Tuomo2 (AUTHOR) tualeh@utu.fi |
| Source: | Discrete Applied Mathematics. Jul2026, Vol. 388, p201-221. 21p. |
| Subjects: | Algorithms, Question (Logic), Mathematical optimization |
| Abstract: | We consider a logical puzzle which we call the double pouring problem, which was originally defined for k = 3 vessels. We generalize this definition to k ≥ 2 as follows. Each of the k vessels contains an integer amount of water, called its value, where the values are a i for i = 1 , 2 , ... , k and the sum of values is n. A pouring step means pouring water from one vessel with value a i to another vessel with value a j , where 1 ≤ i ≠ j ≤ k and a j ≤ a i . After this pouring step the first vessel has value 2 a i and the second one value a j − a i . Now the pouring problem is to find as few pourings steps as possible to empty at least one vessel, or to show that such an emptying is not possible (which is possible only in the case k = 2). For k = 2 each pouring step is unique. We give a necessary and sufficient condition, when for a given (a 1 , a 2) with a 1 + a 2 = n the pouring problem is solvable. For k = 3 we improve the upper bound of the pouring problem for some special cases. For k ≥ 4 we extend the known lower bound for k = 3 and improve the known upper bound O ( (log n) 2) for k = 3 to O (log n log log n). Finally, for k ≥ 3 , we investigate values and bounds for some functions related to the pouring problem. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 193310429 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: The generalized double pouring problem: Analysis, bounds and algorithms. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Jäger%2C+Gerold%22">Jäger, Gerold</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> gerold.jager@umu.se</i><br /><searchLink fieldCode="AR" term="%22Lehtilä%2C+Tuomo%22">Lehtilä, Tuomo</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> tualeh@utu.fi</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Jul2026, Vol. 388, p201-221. 21p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Question+%28Logic%29%22">Question (Logic)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We consider a logical puzzle which we call the double pouring problem, which was originally defined for k = 3 vessels. We generalize this definition to k ≥ 2 as follows. Each of the k vessels contains an integer amount of water, called its value, where the values are a i for i = 1 , 2 , ... , k and the sum of values is n. A pouring step means pouring water from one vessel with value a i to another vessel with value a j , where 1 ≤ i ≠ j ≤ k and a j ≤ a i . After this pouring step the first vessel has value 2 a i and the second one value a j − a i . Now the pouring problem is to find as few pourings steps as possible to empty at least one vessel, or to show that such an emptying is not possible (which is possible only in the case k = 2). For k = 2 each pouring step is unique. We give a necessary and sufficient condition, when for a given (a 1 , a 2) with a 1 + a 2 = n the pouring problem is solvable. For k = 3 we improve the upper bound of the pouring problem for some special cases. For k ≥ 4 we extend the known lower bound for k = 3 and improve the known upper bound O ( (log n) 2) for k = 3 to O (log n log log n). Finally, for k ≥ 3 , we investigate values and bounds for some functions related to the pouring problem. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=193310429 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.dam.2026.03.035 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 21 StartPage: 201 Subjects: – SubjectFull: Algorithms Type: general – SubjectFull: Question (Logic) Type: general – SubjectFull: Mathematical optimization Type: general Titles: – TitleFull: The generalized double pouring problem: Analysis, bounds and algorithms. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Jäger, Gerold – PersonEntity: Name: NameFull: Lehtilä, Tuomo IsPartOfRelationships: – BibEntity: Dates: – D: 31 M: 07 Text: Jul2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 0166218X Numbering: – Type: volume Value: 388 Titles: – TitleFull: Discrete Applied Mathematics Type: main |
| ResultId | 1 |
