4

Give a method to write the number one as the sum of three fractions, where each fraction the numerator is a one-digit number the denominator is a two-digit number and numbers that can be used are from 1 to 9 without repeating numbers.

enter image description here

Roiner Segura Cubero
  • 3,923

2 Answers2

2

$$1=\frac{5}{34}+\frac{7}{68}+\frac{9}{12}$$

kaine
  • 1,672
  • It would be nice if you mentioned how can this be arrived at without bruteforce.. – Nathaniel Bubis Nov 02 '13 at 00:27
  • sorry but I could only find this by brute force. I didn't try to claim more and tried to work backwards to determine a way to get the answer but failed. – kaine Nov 03 '13 at 19:15
1

We can actually confirm that the answer that was posted first is the only solution since the search space of this problem is relatively small and can be iterated over quickly. There are exactly $$\frac{1}{6} {9\choose 3} {6\choose 3} = 280$$ combinations for the three values to examine. Each of these then produces $6^3$ different combinations of fractions, as each choice of digit triples can represent six fractions.

We code this in Perl. The output of the following Perl program is $$9/12 + 5/34 + 7/68.$$ This program runs extremely fast since it uses an effective algorithm (lexical ordering of the elements of the combinations being examined) to compute only the relevant $280$ combinations, as opposed to iterating over all $9!$ permutations which given the factor of $6^3$ of actual values for the fractions is not feasible.

This is the code:

#! /usr/bin/perl -w

sub threeperms {
    my @l = @{ $_[0] };

    return
      [[$l[0], $l[1], $l[2]],
       [$l[0], $l[2], $l[1]],
       [$l[1], $l[0], $l[2]],
       [$l[1], $l[2], $l[0]],
       [$l[2], $l[0], $l[1]],
       [$l[2], $l[1], $l[0]]];
}

sub compute {
    my ($r, $a, $b, $c) = @_;

    my $n = scalar(@$r);
    if($n==0){
      print STDERR "@$a @$b @$c\n";

      foreach $ap (@{threeperms($a)}){
          my $av = $ap->[0]/(10*$ap->[1]+$ap->[2]);

          foreach $bp (@{threeperms($b)}){
            my $bv = $bp->[0]/(10*$bp->[1]+$bp->[2]);

            foreach $cp (@{threeperms($c)}){
                my $cv = $cp->[0]/(10*$cp->[1]+$cp->[2]);

                print 
                  "$ap->[0]/$ap->[1]$ap->[2] + " .
                  "$bp->[0]/$bp->[1]$bp->[2] + " .
                  "$cp->[0]/$cp->[1]$cp->[2]\n"

                  if abs(-1+$av+$bv+$cv)<1e-6;
            }
          }
      }

      return;
    }

    for(my $pos=0; $pos<$n; $pos++){
      my $el = splice @$r, $pos, 1;

      if($n>6){
          compute($r, [@$a, $el], $b, $c)
            if (scalar(@$a)==0 || 
                $a->[-1]<$el);
      }
      elsif($n>3){
          compute($r, $a, [@$b, $el], $c)
            if (scalar(@$b)==0 || 
                ($a->[0]<$b->[0] && $b->[-1]<$el));
      }
      else{
          compute($r, $a, $b, [@$c, $el])
            if (scalar(@$c)==0 || 
                ($b->[0]<$c->[0] && $c->[-1]<$el));
      }

      splice @$r, $pos, 0, $el;
    }
}


MAIN: {
    my @digits = (1..9);

    compute(\@digits, [], [], []);
}
Marko Riedel
  • 61,317