Skip to main content
added 1 character in body
Source Link
Lawrence
  • 7.9k
  • 2
  • 22
  • 56

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, $v$ is equal to the upper bound in $\eqref{1}$, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.

Efficiency

The number of containers used is given by $nv \leq cx$ from the upper bound to $\eqref{1}$, so we will need at most $c = \lceil \frac{nv}{x} \rceil$ containers, with $n$ determined as follows.

The error will be within acceptable limits when $\epsilon_n \leq \epsilon$, so the number of iterations will be at most $n = \lceil \frac{x}{2\epsilon} \rceil$.

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, $v$ is equal to the upper bound in $\eqref{1}$, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, $v$ is equal to the upper bound in $\eqref{1}$, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.

Efficiency

The number of containers used is given by $nv \leq cx$ from the upper bound to $\eqref{1}$, so we will need at most $c = \lceil \frac{nv}{x} \rceil$ containers, with $n$ determined as follows.

The error will be within acceptable limits when $\epsilon_n \leq \epsilon$, so the number of iterations will be at most $n = \lceil \frac{x}{2\epsilon} \rceil$.

added 1 character in body
Source Link
Lawrence
  • 7.9k
  • 2
  • 22
  • 56

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, $v$ is equal to the upper bound in $\eqref{1}$ is an equality, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, the upper bound in $\eqref{1}$ is an equality, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, $v$ is equal to the upper bound in $\eqref{1}$, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.

Source Link
Lawrence
  • 7.9k
  • 2
  • 22
  • 56

Given: unlimited containers, each of volume $x$; volume $v$ of liquid; unlimited additional liquid. In this answer, $x$ is unconstrained - it can be smaller, equal to, or even bigger than $v$.

Assumptions: you can accurately and repeatedly draw out volume $v$ of liquid from the additional supply; you will accept an answer of $v \pm \epsilon$ for some predetermined error margin $\epsilon$. If $v$ is not a rational number, then $\epsilon$ must be non-zero but can otherwise be as small as you like.

You can get an acceptable value of $v$ by repeating the following two steps until the error margin is satisfied. In the analysis that follows, let $c$ be the total number of containers used after $n$ iterations. Note that the last container used may be only partially filled.

  1. Draw out $v$ of liquid from the additional supply.
  2. Fill as many containers as possible from the liquid drawn in step 1, including topping up the partially filled container from the previous iteration.

Error bound

Without making any assumptions about being able to measure partly filled containers, all we can say after $n$ iterations is that the volume is between $c-1$ and $c$ full containers.

We have $(c-1)x < nv \leq cx$, that is, $$v \in (\frac{(c-1)x}{n}, \frac{cx}{n}] \tag{1}\label{1}$$ with the interval open at the bottom and closed at the top. Let $2\epsilon_n$ be the range of the interval, so $2\epsilon_n = \frac{x}{n}$. Rewrite $\eqref{1}$ to get the following. $$v = \frac{(c-0.5)x}{n} \pm \epsilon_n \tag{2}\label{2}$$

Volume calculation

At any iteration, if the last container used is full, the upper bound in $\eqref{1}$ is an equality, so $v = \frac{cx}{n}$ and you're done.

Otherwise, the error is acceptable when $\epsilon_n \leq \epsilon$. Since $\epsilon_n$ decreases as the iteration count $n$ increases, the process is guaranteed to terminate with an answer of $v \approx \frac{(c-0.5)x}{n}$ from $\eqref{2}$.