digits...

shocamefromebay · 2007-06-02 07:15:50

ok. i get this question every year at like every math tourney. and its always the same exact problem but with different letters. and i never understood how to get it. so i need someone to help explain it to me.

it says taht each of these letteres represents a digit and V is not 0. and it wants me to find the value of each digit.

O N E
O N E
T W O
T W O
T H R E E
+ T H R E E
E L E V E N

so can anyone help explain this to me???

mathsyperson · 2007-06-02 07:33:46

The starting point with almost all of these (and this one is no exception) is that the total has more digits than all the things you're adding up, and so the first digit of the total has to be a 1.
And that's all I've got so far. I'll take a closer look later though, unless someone else gets it first.

shocamefromebay · 2007-06-02 09:56:27

but wouldnt it be possible taht the numbers towards the right add up to be relly large numbers and carry on digits as u move ot the rite where the first digit of the total mite be more than one???

mathsyperson · 2007-06-02 10:13:03

Ah, true. I should've checked that more carefully. On closer inspection though, it is definitely a one.

Assuming that E=2, then the maximum value that the sum can take is something along the lines of

752
752
947
947
98622
+98622
---------
200642

However, the total must also have its third digit as a 2, so the maximum total isn't high enough.
Therefore, E=1.

I've also just seen something else that might be useful. In the tens column, we see everything twice, which means their sum must be even. However, they add up to 1 (or 11, or 21 etc.) which means that a 1 must have been carried from the units column. It can't be more than 1 because the units sum is 2*O +4.

So that means that 2O + 4 = N+10 --> 2O = N+6.

shocamefromebay · 2007-06-02 12:17:00

hmmm
O N E
O N E
T W O
T W O
T H R E E
+ T H R E E
E L E V E N

ok so the only one that we no what the real value is is E
O = (N+6)/2
W=2(O) - 5
but how do we find the other values??alll we no for the other digits are expressions which we cant find the values for because they use each variable in each expression

Last edited by shocamefromebay (2007-06-02 12:18:21)

Ricky · 2007-06-02 13:14:23

4E + 2O = 10*k + N

N must be even.

And there is a much easier way to tell that...

Ricky · 2007-06-02 17:03:08

#include <iostream>
#include <vector>
#include <string>
#include <fstream>

using namespace std;

ofstream out("out.txt");

vector<char> make_vector(string input) {
  vector<char> result;
  int i;
  for (i = 0; i < input.length(); i++) {
    result.push_back(input[i]);
  }
  return result;
}

vector<char> make_letters(vector<char> letters, string input) {
  int i,j;
  for (i = 0; i < input.length(); i++) {
    for (j = 0; j < letters.size(); j++) {
      if (letters[j] == input[i]) break;
    }
    if (j == letters.size()) {
      letters.push_back(input[i]);
    }
  }
  return letters;
}

bool check_addition(vector<vector<int> > v) {
  int i, j;
  int max_cols = 0;
  for (i = 0; i < v.size(); i++) {
    if (v[i].size() > max_cols) {
      max_cols = v[i].size();
    }
  }
  
  int sum = 0;
  for (i = 1; i <= max_cols; i++) {
    for (j = 0; j < v.size(); j++) {
      if (j != v.size()-1) {
        if (v[j].size() < i) continue;
        sum += v[j][v[j].size()-i];
      }
      else {
        if (sum % 10 != v[j][v[j].size()-i]) return false;
        sum -= sum%10;
        sum /= 10;
      }
    }
  }
  return true;
}

bool contains(vector<int> v, int k) {
  int i;
  for (i = 0; i < v.size(); i++) {
    if (k == v[i]) break;
  }
  return i != v.size();
}

vector<int> increment_values(vector<int> values) {
  int n = values.size();
  int i, j, k;
  while (values.size() > 0) {
    for (i = values[values.size()-1]+1; i < 10; i++) {
      if (!contains(values, i)) {
        values[values.size()-1] = i;
        break;
      }
    }
    if (i != 10) break;
    values.pop_back();
  }
  if (values.size() == 0) return values;
  
  i = 0;
  while (values.size() != n) {
    if (!contains(values, i)) values.push_back(i);
    i++;
  }
  return values;
}



void solve(vector<vector<char> > v, vector<char> letters) {
  vector<int> values;
  int i, j, k, l;
  for (i = 0; i < letters.size(); i++) {
    values.push_back(i);
  }
  do {
    vector<vector<int> > w;
    for (j = 0; j < v.size(); j++) {
      vector<int> temp;
      for (k = 0; k < v[j].size(); k++) {
        for (l = 0; l < letters.size(); l++) {
          if (letters[l] == v[j][k]) {
            temp.push_back(values[l]);
            break;
          }
        }
      }
      w.push_back(temp);
    }

    if (check_addition(w)) {
      out << "Found it!" << endl;
      for (k = 0; k < w.size(); k++) {
        for (l = 0; l < w[k].size(); l++) {
          out << w[k][l] << " ";
        }
        out << endl;
      }
    }

    values = increment_values(values);
  } while (values.size() > 0);
}


int main() {
  vector<vector<char> > v;
  vector<char> letters;
  int i = 1;
  string input;
  do {
    cout << "Enter line " << i << ": ";
    cin >> input;
    if (input != "done") {
      v.push_back(make_vector(input));
      letters = make_letters(letters, input);
    }
    i++;
  } while (input != "done");
  
  solve(v, letters);

  return 0;
}

Found it!
2 4 0
2 4 0
3 1 2
3 1 2
3 9 7 0 0
3 9 7 0 0
0 8 0 5 0 4
Found it!
4 8 0
4 8 0
2 7 4
2 7 4
2 9 3 0 0
2 9 3 0 0
0 6 0 1 0 8

Ricky · 2007-06-02 17:29:13

K represents the carry from any previous addition.

Assume E = 0. Then N = 2*O. Now assume that the remainder from this column is 1 (it obviously can't be greater than 1). Then 2*N + 2*W + 1 = 0, keeping in mind that 0 just means multiples of 10s. This is impossible since one side is odd. So 2*O < 10.

O is 1, 2, 3, or 4.

N = 2, 4, 6, or 8

E = 0

2*N + 2*W is a multiple of 10, so N and W aren't 5.

T = 1, 2, 3, or 4.

L = 2, 4, 6, or 8

2*O + 2*T + 2*R is at most 25, so the remainder carrying over to the column to the left is at most 3.

2*O + 2*T + 2*R > 10, so H can't be 5.

If L = 2, then 2*T + K = L with no remainder, so 2*T + K = 2, so K = 0 and T = 1. Then 2*H = 0, so L can't be 2.

If L = 4, then 2*T + K = 4, so it must be that T = 1 and K = 2. 2H + K = 20, so H = 9. Now since N = 2, 4, or 6, and we know that O can't be 1 or 2 (N can't be 4 since L is), so N = 6 and O = 3. 10 divides 12 + 2W, and W can't be 9, so W must be 4. But L = 4. Contradiction, L can't be 4.

Possible values:

O 1 2 3 4
N 2 4 6 8
T 1 2 3 4
W 1 2 3 4 6 7 8 9
H 1 2 3 4 6 7 8 9
R 1 2 3 4 5 6 7 8 9
L 6 8
V 1 2 3 4 5 6 7 8 9

assume L = 6:

So 2T + k = 6, but we know that 2H + k is divisible by 10, in the 2T + k = 6, it must be k is not 0. Also, since L is 6, it's not 1 or 3. So k = 2 and thus, T = 2. That means that 2H + k = 20. But then it must be that H is 9. If N = 4, then O = 2. But T = 2. So N = 8 (only other choice). Now 10 divides 16 + 2W, so either W is 2 or 7. But it can't be 2 (already taken), so W = 7. Now 3 (the carry) + 4 + 4 + 2 + 2 + 2R = V, or rather 15 + 2R = V. So R can't be 1 or 5 obviously. If R = 7, then V = 9. So R can't be 7. This only leaves 3. And so V = 1. That's all of them.

Someone else do L = 8, please....

mathsyperson · 2007-06-02 19:38:21

If there doesn't exist an answer where the sum has 6 digits, then the question is mean and counter-intuitive.

Ricky · 2007-06-03 04:25:18

At least I don't have to waste my time on any more of these... my program will solve any in about 2 hours.

shocamefromebay · 2007-06-03 06:03:51

well how do u solve it in like lets say 45 mins?? cuz taht usualy how long im given to do one of these problems. is there a program taht can do taht??

Ricky · 2007-06-03 06:39:57

You have to use logic. Typically, none are this hard. This was a really hard one because of the number of letters and the number of lines.

Ricky · 2007-06-03 07:32:29

Wow, I'm quite amazed at both my inability to estimate time and how much compiler options can speed up a program. In debug (slow) mode, the program takes 36.8 minutes. In release (fast) mode, it took 66 seconds.

Also, note that the complexity of this problem goes up exponentially with the number of different digits. The maximum run time should be somewhere around 6 minutes. But as soon as you lose one digit, it will drop to around 60 seconds. Lose another, and you're down to 6 seconds. One more and you're under 1 second.

shocamefromebay · 2007-06-03 07:57:30

so where can i get a copy of this program on a calulator???like a Ti-83 or Ti-84??

Last edited by shocamefromebay (2007-06-03 07:59:28)

Ricky · 2007-06-03 09:19:19

On a Ti-83, it would take about a week.

shocamefromebay · 2007-06-03 14:43:00

aww bananas. i hate that. what aobut an 84 or and 89? tho i doubt taht will make much of a difference...hmmm this problem is very tricky. expecially when they expect us to do oone of thses in about an ohur or so. i hate that.

Ricky · 2007-06-03 17:06:02

Like I said, use logic.

Math Is Fun Forum

#1 2007-06-02 07:15:50

digits...

#2 2007-06-02 07:33:46

Re: digits...

#3 2007-06-02 09:56:27

Re: digits...

#4 2007-06-02 10:13:03

Re: digits...

#5 2007-06-02 12:17:00

Re: digits...

#6 2007-06-02 13:14:23

Re: digits...

#7 2007-06-02 17:03:08

Re: digits...

#8 2007-06-02 17:29:13

Re: digits...

#9 2007-06-02 19:38:21

Re: digits...

#10 2007-06-03 04:25:18

Re: digits...

#11 2007-06-03 06:03:51

Re: digits...

#12 2007-06-03 06:39:57

Re: digits...

#13 2007-06-03 07:32:29

Re: digits...

#14 2007-06-03 07:57:30

Re: digits...

#15 2007-06-03 09:19:19

Re: digits...

#16 2007-06-03 14:43:00

Re: digits...

#17 2007-06-03 17:06:02

Re: digits...

Board footer