Happy Valentine's Day, once again

Comrade Vladimir is getting some flowers for Nadezhda, his Valentine. Being of a precise analytical mind, he plans to spend exactly 100 rubles on exactly 100 flowers. At the flower market, they sell daisies at a rate of 5 for 3 rubles, tulips at a rate of 7 for 5 rubles, carnations at a rate of 9 for 7 rubles, and roses at a rate of 3 for 9 rubles.

To qualify for these special rates, one needs to buy daisies in bunches of 5, tulips in bunches of 7, etc. In how many different ways can Vladimir select a bunch of 100 flowers that will contain some flowers of all four kinds while still qualifying for these special rates?


The answer is 6.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Otto Bretscher
Feb 14, 2016

As Brian explains, we have the two equations (for quantity and price)

5 d + 7 t + 9 c + 3 r = 100 5d+7t+9c+3r=100

3 d + 5 t + 7 c + 9 r = 100 3d+5t+7c+9r=100

The reduced row-echelon form of this system comes out to be

d = c + 12 r 50 d=c+12r-50 and t = 50 2 c 9 r t=50-2c-9r

To end up with a some daisies and tulips in the bunch, we need c + 12 r > 50 c+12r>50 and 2 c + 9 r < 50 2c+9r<50

The "final filtering" isn't so tedious now, since we deal with only two variables and there are no additional divisibility conditions to satisfy.

The second inequality gives r 5 r\leq 5 .

If r = 5 r=5 then 2 c < 50 45 2c<50-45 so c 2 c\leq 2 , which gives two solutions.

If r = 4 r=4 then 2 < c < 7 2<c<7 , which gives four solutions.

If r 3 r\leq 3 , then there are no solutions.

Thus we have 6 \boxed{6} solutions overall.

Nice. That does simplify the process considerably. :)

Brian Charlesworth - 5 years, 4 months ago

Let d , t , c , r d,t,c,r be the respective number of bunches of daisies, tulips, carnations and roses.

The "quantity equation" is then 5 d + 7 t + 9 c + 3 r = 100 5d + 7t + 9c + 3r = 100 , and the "price equation" is 3 d + 5 t + 7 c + 9 r = 100 3d + 5t + 7c + 9r = 100 .

Subtracting the former from the latter yields the equation

2 d 2 t 2 c + 6 r = 0 3 r = d + t + c . -2d - 2t - 2c + 6r = 0 \Longrightarrow 3r = d + t + c.

Substituting this result back into the quantity equation yields

6 d + 8 t + 10 c = 100 3 d + 4 t + 5 c = 50 6d + 8t + 10c = 100 \Longrightarrow 3d + 4t + 5c = 50 ,

where d , t , c d,t,c must be positive integers and their sum must be divisible by 3 3 in order for r r to be a positive integer as well. So now the tedious part, working our way down from c = 8 c = 8 , (clearly c = 10 , 9 c = 10,9 will not yield solutions), to c = 1 c = 1 , checking for suitable values for d , t d,t and then the divisibility condition. This leads to the solution quadruples, where r = d + t + c 3 r = \frac{d + t + c}{3} ,

( d , t , c , r ) = ( 4 , 2 , 6 , 4 ) , ( 3 , 4 , 5 , 4 ) , ( 2 , 6 , 4 , 4 ) , ( 1 , 8 , 3 , 4 ) , ( 12 , 1 , 2 , 5 ) (d,t,c,r) = (4,2,6,4), (3,4,5,4), (2,6,4,4), (1,8,3,4), (12,1,2,5) and ( 11 , 3 , 1 , 5 ) (11,3,1,5) ,

i.e., a total of 6 \boxed{6} different ways.

@Otto Bretscher I suppose that you were more interested in creative ways to make the final filtering process less tedious. In this case the brute force approach only took a few minutes, but I'm curious what a more streamlined approach might look like.

Brian Charlesworth - 5 years, 4 months ago

Yes, a nice complete solution... I'm sorry that you had to work your way through the "tedious part". Thanks! (+1) I usually do these problems with Gaussian elimination... I will post a solution when I find the time. It gets a bit less tedious that way since we can reduce the problem to two ("free") variables.

I always like to point out a typo just to show that I have read the solution carefully: In the fifth row you should have 6 r 6r in the first equation.

Otto Bretscher - 5 years, 4 months ago

Log in to reply

Haha Thanks for catching that. :)

Brian Charlesworth - 5 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...