Olympiadeoppgave(12th grade)

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

La n* være tallet man får etter å ha tatt et heltall n, og flyttet tallets siste siffer til første posisjon (f.eks , 7491* = 1749). Bestem en n>0 slik at 7n* = 2n .
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Dette ser ut som et problem som skal kunne løses ganske greit med brute-force :P
Litt kode i C#:

Kode: Velg alt

public static void Main()
{
	int i,j;
	i = 0;
	while(true)
	{
		i++;
		
		j = Stjerne(i);
		
		int VS = 7*j;
		int HS = 2*i;
		
		if (VS == HS)
		{
			Console.WriteLine(i+" er en løsning.");
		}
	}
}
public static int Stjerne(int n)
{
	string s = n.ToString();
	char sistesiffer = s[s.Length-1];
	string s2 = s.Remove(s.Length-1);
	string s3 = sistesiffer + s2;
	return int.Parse(s3);
}
Gir, etter ett sekund:

"538461 er en løsning."

Det kan sjekkes:

538461* = 153846

7*153846 = 1076922
2*538461 = 1076922

Venter i spenning på flere løsninger eller en litt penere, matematisk metode :)
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Den der måtte jo komme..
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Kunne man dratt en sånn på olympiaden da? Eller får man ikke bruke PC?
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Samme hjelpemidler som i abelkonkurransen ; )
Solar Plexsus
Over-Guru
Over-Guru
Innlegg: 1685
Registrert: 03/10-2005 12:09

Denne oppgaven kan løses ved regning. La [tex]m[/tex] være antall siffer i [tex]n[/tex]. La [tex]x[/tex] være tallet (som har m-1 sifre) som blir igjen når vi fjerner siste siffer [tex]y[/tex] i [tex]n[/tex]. Da er

(1) n = 10x + y

og

(2) n[sup]*[/sup] = 10[sup]m-1[/sup]y + x.

Likningen 7n[sup]*[/sup] = 2n gir

[tex](3) \;\;\; y \;=\; \frac{13x}{7 \cdot 10^{m-1} \:-\: 2}[/tex]

I.o.m. at x har m-1 sifre, må x < 10[sup]m-1[/sup]. Dermed får vi vha. (3) at

[tex]y \;<\; \frac{13 \cdot 10^{m-1} }{7 \cdot 10^{m-1} \:-\: 2} \; < \; 2[/tex]

Herav følger at y = 1, som innsatt i (3) gir

[tex](4) \;\;\; x \;=\; \frac{7 \cdot 10^{m-1} \:-\: 2}{13}[/tex]

Ergo må [tex]7 \cdot 10^{m-1} \:-\: 2[/tex] være delelig med 13. Herav følger at m er delelig med 6, dvs. at m = 6k for et naturlig tall k. Dette i kombinasjon med (3) medfører at

[tex]n \;=\; 10x \:+\: y \;=\; 10 \, \cdot \, \frac{7 \cdot 10^{6k-1} \:-\: 2}{13} \:+\: 1 \;=\; \frac{7}{13} \, (10^{6k} \:-\: 1) \:=\: n(k).[/tex]

Altså blir n(1) = 538461. Et interessant poeng her er at n(2) = 538461538461, altså 538461 skrevet to ganger etter hverandre. Dette gjelder generelt: n(k) blir tallet bestående at 538461 skrevet k ganger etter hverandre. Forklaringen på dette fenomenet ligger i identiteten

[tex]\overbrace{n(1)n(1) \cdots n(1)}^{\mbox{k ganger}} \;=\; 538461 (10^{6(k-1)} \:+\: 10^{6(k-2)} \:+\: \ldots \:+\: 1) \;=\; \frac{7}{13}(10^6 \:-\: 1) \, \cdot \, \frac{10^{6k} \:-\: 1}{10^6 \:-\: 1} \;=\; n(k).[/tex]
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Veldig fint arbeid. Spesielt den generelle formelen.
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Legger med en oppgave til. Disse oppgavene ble gitt av en post.doc på NTNU ved et matteseminar forrige uke. Problemene er offisielt fra en kanadisk olympiade.

Anta [tex]E \subseteq \{1,2,3,\ldots,30\}[/tex] består av 8 elementer. Vis at det eksisterer ikke-tomme disjunkte delmengder av E som er slik at summen av elementene er like.
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Solar Plexsus skrev:Ergo må [tex]7 \cdot 10^{m-1} \:-\: 2[/tex] være delelig med 13. Herav følger at m er delelig med 6
hvorfor det?
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Hvorfor den må være delelig på 13 eller m være delelig med 6 ?
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

sEirik skrev:
Solar Plexsus skrev:Ergo må [tex]7 \cdot 10^{m-1} \:-\: 2[/tex] være delelig med 13. Herav følger at m er delelig med 6
hvorfor det?
Vi har at [tex]7 \cdot 10^{m-1} \equiv 2 \ \pmod {13}[/tex]

2 er invers til 7 modulo 13

[tex]10^{m-1} \equiv 2 \cdot 2 \pmod {13}[/tex]

Fra faktum at 13 er prim, og multiplikasjon modulo 13 derfor former en gruppe, at [tex]10^5 \equiv 4 \pmod{13}[/tex] og [tex]10^6 \equiv 1 \pmod{13}[/tex], følger:

[tex]10^{m-1} \equiv 4 \equiv 10^{5 + 6k} \pmod{13}[/tex]

[tex]m-1 = 5 + 6k \\ m =6(k+1)[/tex]

Og dermed ser vi at m må være delelig med 6.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

Magnus skrev:Legger med en oppgave til. Disse oppgavene ble gitt av en post.doc på NTNU ved et matteseminar forrige uke. Problemene er offisielt fra en kanadisk olympiade.

Anta [tex]E \subseteq \{1,2,3,\ldots,30\}[/tex] består av 8 elementer. Vis at det eksisterer ikke-tomme disjunkte delmengder av E som er slik at summen av elementene er like.
Enten har jeg oversett noe vitalt, eller så kan vi løse denne med nokså elementær "pigeonhole"-ing.

Størst mulig sum av en delmengde av E er 23 + 24 + ... + 30 = 212. Minst mulig er 0. (Summen av elementene i nullsettet.)

Dette betyr at det finnes maksimalt 212 + 1 = 213 ulike summer delmengdene kan ta.

Antall distinkte delmengder av E er 2^8 = 256.

Siden det finnes 256 delmengder, men kun 213 ulike summer, betyr dette at det må finnes minst 2 delmengder av E med samme sum. {Pigonhole principle.} Kall disse to delmengdene A og B.

Dersom A og B er disjunkte, er vi ferdige. Dersom A og B ikke er disjunkte, fjern deres felles elementer. Vi står nå igjen med to disjunkte delmengder med samme sum. At vi telte distinke delmengder betyr at A og B var ikke-tomme, og av umuligheten av to elementer med samme verdi, følger at A og B har 2 eller flere elementer. Vi har dermed bevist eksistens av delmengdene etter de gitte kriteriene.


Forresten, finnes det et godt norsk begrep for "pigeonhole principle"?
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

Kan ikke bidra med noe her. Men var innom pigeonhole begrepet i diskret matematikk for noen år sida. Tror det rett og slett ble oversatt med duebox prinsippet (problemet ).
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Svar